Pre-Requisite Information -- Combinatorial and Graph Algorithms, SoC, NUS

CS5234 - Combinatorial and Graph Algoritms
School of Computing, National University of Singapore
Semester 2, 2006/2007 (Spring 2007)

Pre-Requisite Information

CS5234 is aimed at both beginning graduate students and advanced undergraduate students (fourth year).

Pre-Requisites for the Course...

The pre-requisite for CS5234 is CS3230: Design and Analysis of Algorithms. We expect students to have gone through this course!

Because there will graduate students from elsewhere (non-SoC students). I will state a more general pre-requisite for the module; in terms of the actual topics assumed:

  • It is meant for students who already have good background in algorithms design and analysis.

  • To give you an idea of what this may mean, I assume that you
    • know analysis of algorithm; i.e. knows O-notation very well and have used it to analyze the worst-case behaviour of algorithms and data structures.
    • have studied, programmed, and analyzed many data structures including stacks,queues, lists, binary search trees, AVL-like trees, heaps, priority queues
    • have studied and analyzed many sorting and searching algorithms (including Quicksort and Heapsort)
    • have studied and analyzed graph algorithms (DFS, BFS, Dijkstra's algorithm, MST algorithms)
    • have experience with standard algorithmic paradigms (greedy algorithms, divide-and-conquer, dynamic programming, etc)
    • are able to derive the running time of most of the above data structures and algorithms.

  • For a rough gauge of the above, you should be already know the material (including the analysis of the algorithms therein) in the following chapters of the text [CLRS01]:
    • Chapter 2 -- Basics
    • Chapters 3-5 -- Mathematical Foundations
    • Chapters 6-13 -- Sorting and Basic Data Structures
    • Chapters 15-16 -- Dynamic Programming and Greedy Algorithms
    • Chapters 22-24 -- Graph Algorithms

  • Yet another way to test yourself is to quickly do Homework Set 0. If you can't solve the problems there fairly easily, then you probably should be taking CS3230 instead of CS5234.

    • About the Course...
  • This course covers advanced algorithms.
    (It is NOT a course to teach you basic algorithms.)

  • It is meant for students who already have good background in algorithms design and analysis.

  • You will find the going very tough if you have weak or no algorithmic background at all. (To find out check the Pre-Req section).

  • DO NOT take this course just because you have to fill up your course quota for your degree.
    You will live to regret it.

  • This course is known to be a heavy module. Homeworks are known to be difficult and take a lot of time to solve. I expect students to learn most of the material from doing the homeworks and assignments.

  • If you are serious about learning algorithm design and analysis (for your own research work or for rigourous research preparation), then welcome aboard.

  • To get maximum benefit out of this course, first read and absorb the spirit of the Cattywampus article.

    • Un-Official Registration Information

  • CS5234 is a course for advanced undergraduates and beginning graduate students.

  • CS5234 is ideal for students (advanced undergraduate or beginning graduate) who are (or aim to be) doing research in algorithms.

  • CS5234 is less suitable for MSc-by-Coursework students, especially those without a strong background in analysis of algorithms. (See above discussion on the Course.)

    • CS5234 Combinatorial and Graph Algorithms
    Leong Hon Wai's Homepage