Syllabus
This page is an elaboration of the learning outcome of course plan
Specifically we will cover the following topics and sections of the book (for a CLRS4 reading guide see the individual lecture pages):
| Topic | CLRS3 Textbook |
|---|---|
| Reminder, growth of functions, big-Oh notation, recurrences and divide and conquer. | Chapters 1-4, except Section *4.6 |
| Dynamic Programming | Chapter 15 |
| Reminder Elementary Graph Algorithms | Chapter 22 Except 22.4 |
| Greedy Algorithms | Chapter 16, except Sections *16.4 and *16.5 |
| Minimum Spanning Trees (MST) | Chapter 23 (we only study Prim’s algorithm) |
| Single-Source Shortest Paths | Chapter 24: pages 643-650 and Section 24.3 |
| (we only study Dijkstra’s algorithm) | |
| Maximum Flow | Chapter 26, except Sections *26.4 and *26.5 |
| Disjoint Sets/Union Find | These notes or Chapter 21 |
| Strings Matching | Chapter 32, except Sections 32.3 and *32.4 |
| P versus NP | Chapter 34 |
In Lectures you can find a more detailed lecture plan with links to additional resources. The timing of the assignments has been done quite carefully. By the time you are to start the each assignment we should have covered the material in the assignments.