Semester 2, 2017/2018
YaleNUS 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, blackred trees, augmenting data structures and an accesstime analysis called amortized analysis. This course will be exciting, since we will see many elegant and beautiful algorithms/analysis.
The following schedule will not be strictly followed.
Date   

January 15 
1. INTRODUCTION
Reading:
 Lecture 1 
January 18 
2. ASYMPTOTIC ANALYSIS
Reading:
 
January 22 
3. RECURSIVE ALGORITHMS AND ANALYSIS: SUBSTITUTION METHOD
Reading:
 Lecture 3 
January 25 
Class Cancelled
 
January 29 
Class Cancelled
 
February 1 
4. RECURRENCE ANALYSIS: TREE + MASTER METHODS
Reading:
 Lecture 4 
February 5 
5. RANDOMIZED ALGORITHMS AND ANALYSIS
Reading:

Lecture 5
Assignment 1 
February 8 
6. RANDOMIZED QUICKSORT (Part 1)
Reading:
 Lecture 6 
February 12 
7. RANDOMIZED QUICKSORT (Part 2)
 
February 15 
8. SORTING IN LINEAR TIME
Reading:
 Lecture 8 
February 19 
9. HASHING: INTRODUCTION
Reading:
 
February 22 
10. QUIZ 1
 
RECESS WEEK  
March 5 
11. UNIVERSAL HASHING
Reading:
 Lecture 11 
March 8 
12: UNIVERSAL HASHING 2
 
March 12 
13. PERFECT HASHING AND CLOSED HASHING
Reading:
 Lecture 13 
March 15 
14. AMORTIZED ANALYSIS
Reading:
 Lecture 14 
March 19 
15. AMORTIZED ANALYSIS: ACCOUNTING METHOD + DISCUSSION
Reading:
 
March 21 
16. AMORTIZED ANALYSIS: POTENTIAL METHOD
Reading:
 
March 22 
17. LINEAR PROGRAMMING
 
March 29 
18. SHORTEST PATHS AND LINEAR PROGRAMS
 
April 2 
19. MAX FLOW AND LINEAR PROGRAMS
 
April 5 
20. NPCOMPLETENESS
 
April 9 
21. APPROXIMATION ALGORITHMS
 
April 12 
22. RANDOMIZED ALGORITHMS 1
 
April 16 
23. RANDOMIZED ALGORITHMS 2
 
April 19 
24. REVIEW + QA SESSION
