Design and Analysis of Algorithms I. About the Course In this course you will learn several fundamental principles of algorithm design.
You'll learn the divide-and-conquer design paradigm, with applications to fast sorting, searching, and multiplication. You'll learn several blazingly fast primitives for computing on graphs, such as how to compute connectivity information and shortest paths. Onsite Lectures: CS 161 DAA. Course Description Course Overview: Introduction to fundamental techniques for designing and analyzing algorithms, including asymptotic analysis; divide-and-conquer algorithms and recurrences; greedy algorithms; data structures; dynamic programming; graph algorithms; and randomized algorithms.
Required textbook: Kleinberg and Tardos, Algorithm Design, 2005. We will be covering most of Chapters 4–6, some parts of Chapter 13, and a couple of topics not in the book. Prerequisites: Introduction to proofs, and discrete mathematics and probability (e.g., CS 103 and Stat116). If you have not taken a probability course, you should expect to do some independent reading during the course on topics including random variables, expectation, conditioning, and basic combinatorics. Design and Analysis of Algorithms I.