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

CS4234/CS5234 - Combinatorial and Graph Algoritms
School of Computing, National University of Singapore
Semester 1, 2001/2002 (Fall 2001)

Pre-Requisite Information

Pre-Requisites for the Course...

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

As the module is also cross-listed as CS5234, there may be a small number of graduate students from elsewhere (non-SoC students). Therefore, let me 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 [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 CS4234.

    • 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.

    • Official Registration Information

  • CS4234 is an Honours-level module.
    It is also cross-listed as a 5000-level graduate module.

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

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

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