CS6013/AI5005: Advanced Data Structures and Algorithms, Fall 2019

Recommended Textbook(s)

• [CLRS]: Introduction to Algorithms, 3rd Edition. By Cormen, Leiserson, Rivest, Stein. (This will be the primary reference for the course)
• [KT]: Algorithm Design. By Kleinberg and Tardos.

Lecture Schedule and Reading

1. 30/07: Lecture 1: Divide and Conquer: Merge Sort, Maximum Subarray. Reading: CLRS Chapter 4.1.
2. 31/07: Lecture 2: Solving Recurrences, Proofs using induction. Reading: CLRS 4.3, 4.4.
3. 02/08: Lecture 3: Master Theorem (without proof), Strassen's Algorithm. Reading: CLRS 4.5. For strassen's algorithm: 4.2 in CLRS, but we used different matrices (see, for e.g. Wikipedia).
4. 06/08: Lecture 4: Divide and Conquer: Closest Pair of Points in 2-D. (CLRS 33.4)
5. 07/08: Lecture 5: Closest Pair of Points in 2-D cont'd. Probability Basics: Random Variables, Expectation, Linearity of Expectation.
6. 09/08: No Class due to Instructor Travel. Make-up classes to be scheduled later.
7. 13/08: Lecture 6 (1.5 hours): Probability continued. Online Secretary Hiring with random arrivals. (CLRS Chapter 5: Sec 5.1, 5.2). Quicksort: Deterministic algorithm description.
8. 14/08: Lecture 7: Quicksort: Randomized Pivoting. (CLRS Chapter 7)
9. 16/08: Lecture 8: Finishing Quicksort analysis. Selection in Expected Linear time. (CLRS Chapter 9: Sec 9.2).
10. 20/08: Lecture 9: Finishing Selection in Expected Linear time. Beginning Hashing.
11. 21/08: Lecture 10: Hashing: Chaining and Universal Hashing. (For this and subsequent lectures on Hashing, refer to CLRS Chapter 11).
12. 23/08: Lecture 11: Hashing: Open Addressing.
13. 27/08: Lecture 12: Hashing: Examples, Analysis of Open Addressing assuming uniform hashing.
14. 28/08: Lecture 13: Skip Lists: Introduction. (Notes and References will be posted after Lecture 14).