### Description:

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)

### Syllabus:

- Growth of Functions
- Recurrent Algorithm and Analysis
- Randomized Algorithms and Analysis
- Dynamic Programming
- Greedy Algorithms
- Graph-based Algorithms
- Linear Programming
- Hashing
- Binary Search Trees
- Amortized Analysis
- NP Completeness
- Approximate Algorithms
- Monte Carlo Algorithms