Planned Syllabus

I. Introduction (Types of analysis, course goals): Preface

II. Dynamic programming: Chapter 6.3, 6.5-6.10

III. Network Flow: Chapter 7

IV. Hard Problems: Chapter: 8 and a little of 9 and 10

V. Approximation Algorithms: Chapter 11

VI. Probabilistic analysis and randomized algorithms: Chapter 13

VII. Local Search: Chapter 12

VIII. String algorithms: Suffix Trees (handout) if time allows

Other Advanced Topics may be covered depending on class interest.

Notes on the text: Material in chapters 1-5, should already be familiar to students in this class (except for starred sections of those chapters). Everyone should also be familiar with basic data structures and balanced binary search tree such as Red-black trees (or AVL trees or 2-3 trees). The topics of chapters 4-6 (Dynamic programming, greedy algorithms, divide-conquer/recurrence relations ) should be familiar, but perhaps not allthe examples in the text. Similarly, NP-completeness and approximation algorithms (chaps. 8, 11) should be somewhat familiar, though again, not the details of those sections. The text will be the main source of information, but there will also be some handouts to supplement the text.