TTh 930-1050 TECH LG76

Prof. Hai Zhou

haizhou AT northwestern.edu

L461 Tech Institute

(847)491-4155

Office Hours: Th 11am-1pm or by appointment

Mr. Debasish Das

dda902 AT eecs.northwestern.edu

M314 Tech Institute

(847)491-9925

Office Hours: M 2-5 or by appointment

This course will cover the theoretical aspects of algorithm design and analysis. Topics include correctness proofs and performance analysis; number-theory algorithms (cryptography and hashing); divide-and-conquer; greedy algorithms; dynamic programming; linear programming and duality; graph algorithms; NP-completeness and reductions; and quantum algorithms. Besides a deep understanding of useful algorithms, a main goal of this course is to improve the problem solving abilities of the students. Therefore, if possible, we will study together how an efficient algorithm is designed.

EECS 310 and EECS 311.

- S. Dasgupta, C. Papadimitriou, U. Vazirani, Algorithms, McGraw Hill, 2006.

- J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 2005.
- E. W. Dijkstra, A Discipline of Programming, Prentice-Hall, 1975.

Grading: 40% Homework 30% Take-home exam 30% Final exam

Late policy: -40% per day

Homework 0: bio and background

Homework 1 (1/9 out, 1/16 due): algorithm correctness and analysis

Homework 2 (1/16 out, 1/23 due): arithmic and cryptography algorithms

Homework 3 (1/23 out, 1/30 due): divide-and-conquer and graphs

Homework 4 (1/30 out, 2/6 due): divide-and-conquer and path algorithms

Homework 5 (2/6 out, 2/13 due): greedy algorithms

Homework 6 (2/13 out, 2/20 due): greedy algorithms and dynamic programming

Take home exam (2/20 out, 2/27 due): pdf

Homework 7 (2/27 out, 3/6 due): max flow and linear programming

Homework 8 (3/6 out, 3/8 due): NP-completeness and approximation

Week 1:Algorithm design, correctness proofs, and performance analysis. READING: chapters 0,1

Week 2:Primality and cryptography. READING: chapter 1

Week 3:Divide-and-conquer algorithms. READING: chapter 2

Week 4:Graph algorithms. READING: chapters 3,4

Week 5:Greedy algorithms. READING: chapter 5

Week 6:Dynamic programming. READING: chapter 6

Week 7:Linear programming and duality. READING: chapter 7

Week 8:NP-completeness and reductions. READING: chapter 8

Week 9:Approximation and heuristic algorithms. READING: chapter 9

Week 10:Quantum algorithms. READING: chapter 10

Please check back often to this page (www.ece.nwu.edu/~haizhou/336) for updates and course material down-loading.