Course info
Lectures
Homeworks
Contact
UW CS
Theory Group

Announcements
 Next few lectures: 11/9, 11/11, 11/16, 11/23, 11/25, 11/30, 12/02.
 10/29. Shuchi will hold office hours from 12:30 to 2:00p.m. tomorrow (Oct. 30th).
 10/13. Solutions to HW1 are available now. Please see below.
 10/11. HW2 is available now. See below.
 10/06. Shuchi will hold office hours tomorrow (Oct 7) from 10 am to 11 am.
 10/05. HW1.5 is available here. Different tasks are due on different dates.
 09/21. Lecture notes on LP duality are up now. Please see here. Also, please note that a few minor erros in lecture 5 notes have now been fixed.
 09/20. HW1 is now up. Please scroll down. Also, please see this for additional guidelines.
 09/04. Please email a picture of yours to Keith (langston AT cs) for our picture board (wisc.edu access only). This will help us associate your names with your faces.
 09/04. Please note the change in both Shuchi's and Keith's office hours.
 08/21. Our first lecture will be on Sept. 2, and the second on Sept. 4.
 08/14. Welcome! Please check this space frequently for announcements. More information about the syllabus, instructor, course work, etc. can be found here.
Course Description
Algorithm design and analysis is a fundamental and important part of computer science. This course introduces students to advanced techniques for the design and analysis of algorithms, and explores a variety of applications. Read more ...
Lecture notes & readings
Lecture notes will be posted here over time (the morning of every lecture). Please check frequently.
The books referenced below are Borodin & ElYaniv (B&EY), Kleinberg & Tardos (K&T), Motwani & Raghavan (M&R), and Vazirani (Vaz.). All are available at the Wendt library.
Lecture # & Date 
Topic 
Suggested readings 
Lecture notes 

1 (09/02), 2 (09/04) 
1: Intro & greedy algorithms 
(K&T §2, §4) 
PDF 
2 (09/04) 
2: Divide & Conquer algorithms 
(K&T §5) 
PDF 
3 (09/09), 4 (09/14) 
3: Dynamic Programming 
(K&T §6) 
PDF 
4 (09/14), 5 (09/16) 
4: Network Flow: Algorithms 
(K&T §7) 
PDF 
6 (09/18), 7(09/21) 
5: Network Flow applications & Linear Programming 
(K&T §7) 
PDF, PDF2 

8 (09/23), 9 (09/25) 
6: Randomized Algorithms, Karger's mincut algorithm 
(K&T §13) 
PDF 
9 (09/25), 10(9/28) 
7: Randomized load balancing and hashing 
(K&T §13.10,
§13.6, M&R §8.4, §8.5) 
PDF 
10 (09/28), 11 (09/30) 
8: NPCompleteness 
(K&T §8) 
PDF 
12 (10/02) 
9: Approximation Algorithms 
(Vaz §1, §3.2) 
PDF 
13 (10/05) 
10: LP relaxation, rounding 
(Vaz §14) 
PDF 

14 (10/12), 15 (10/14), 16 (10/19) 
11: Randomized rounding, concentration bounds 
(M&R §3.2, §4.1, §4.2) 
PDF 
16 (10/19), 17 (10/21), 18 (10/26) 
12: LP Duality, PrimalDual algorithms 
(Vaz §12, §15, §22) 
PDF 
18 (10/26), 19 (10/30) 
13: Semidefinite Programming 
(Vaz §26) 
PDF (DRAFT) 
20 (11/2), 21 (11/9) 
14: Online algorithms 
(B&EY §1, §3) 
PDF 
22 (11/11), 23 (11/16) 
15: Random walks and Markov chains 
(M&R §6) 
PDF 

24 (11/23) 
Student presentations 

PDF1, PDF2, PDF3 
25 (11/25) 
Student presentations 

PDF4, PDF5, PDF6 
26 (11/30) 
Student presentations 

PDF7, PDF8, PDF9 
27 (12/02) 
16: Wrapup 


Homeworks
(Note: Homeworks and solutions are no longer available here.)
Misc material
Project ideas are available here.
