Pre-Requisite Information -- CS6204 Combinatorial and Graph Algorithms, Fall 1999, NUS

CS6204 - Combinatorial and Graph Algoritms
School of Computing, National University of Singapore
Semester 1, 1999/2000 (Fall 1999)

Pre-Requisite Information

Pre-Requisites for the Course...

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

As this is a level 6000 module, there may be a small number of post-graduate students from elsewhere (non-SoC students). Therefore, let me state a 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 [CLR90]:
    • Chapters 2-6 -- Mathematical Foundations
    • Chapters 8-14 -- Sorting and Basic Data Structures
    • Chapters 23-25 -- 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 CS6204.

    • About the Course...
  • This course teaches 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.

    • Official Registration Information

  • My own interpretation (which is unofficial) is that 6000-level modules are more research-based courses, while 5000-level modules are more suited for MSc-by-Coursework.

  • Officially, CS6204 is a graduate course that can be taken by Honours Year students, and all post-graduate students.

  • Unofficially, for me, CS6204 is meant for students who are doing or aim to be doing research work in algorithms -- whether undergraduate, Honours, or post-graduate.

  • CS6204 is less suitable for MSc-by-Coursework students. (See above discussion on the Course.)

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