YSC3203 Advanced Algorithms and Data Structures

Semester 2, 2017/2018
Yale-NUS College


The goal of designing an algorithm is to generate correct outputs with an efficient running time. To measure the efficiency requires running time analyses, or rate of growth analysis, which is basically to assess whether the running time of an algorithms is either linear or quadratic or exponential with respect to the size of the input data. We will discuss this running time analysis throughout the course. Besides, we also study some algorithms that are widely used, such as, randomized algorithms, divide and conquer, dynamic programming, greedy algorithms, graph algorithms, linear programming, parallel programming, etc. We also discuss a few types of data structures, particularly dynamic data structures and their access time analysis: hashing, randomized binary search trees, black-red trees, augmenting data structures and an access-time analysis called amortized analysis. This course will be exciting, since we will see many elegant and beautiful algorithms/analysis.

Prerequisite: Fundamentals of Programming
Textbook: Cormen et al, ''Introduction to Algorithms'', third edition, MIT press (its ebook version is accessible through NUS library)
Instructor: Robby T. Tan (robby.tan [att] yale-nus.edu.sg)