Lectures: Tuesdays and Thursdays 9:30-11am in Klaus 1443
Instructor: Eric Vigoda, Klaus 2222
Office hours: Mondays and Wednesdays 9:30-10:30am (Eric’s office)
TA office hours (held in open area in front of Klaus 2138)
- Kevin Lai Mondays 5:30-6:30 and Thursdays 4-5pm
- Tiancheng Gong Tuesdays 11am-noon and Fridays 2-3pm (gongtiancheng2012 gmail.com)
- Tung Mai Wednesdays 5-7pm
Grading:
- HW: 5%
- Programming projects (2): 20%
- Midterm exams (3): 50%
- Final: 25%.
Homework policy: You may work with other people on the homework, but you must each write up your solutions separately (without any notes from your group discussion). If you work with other people, indicate who you worked with on your solution. Avoid looking up solutions online or in references.
The required textbook is Algorithms by S. Dasgupta, C. Papadimitriou, and U. Vazirani.
The textbook Algorithm Design by J. Kleinberg and E. Tardos is an excellent reference that you might consider looking at as well.
Course overview:
- Dynamic programming
- Divide and conquer, including FFT
- RSA cryptosystem
- Randomized algorithms, including:
- Bloom filters
- PageRank
- Karger’s min-cut algorithm
- Graph algorithms, including:
- Strongly connected components
- Minimum spanning tree
- Max-flow algorithms
- Linear programming: basics and duality
- NP-completeness
