# EECS 336 Design and Analysis of Algorithms

#### Time & Place

TTh 930-1050 TECH LG76

#### Instructor

Prof. Hai Zhou
haizhou AT northwestern.edu
L461 Tech Institute
(847)491-4155
Office Hours: Th 11am-1pm or by appointment

#### TA

Mr. Debasish Das
dda902 AT eecs.northwestern.edu
M314 Tech Institute
(847)491-9925
Office Hours: M 2-5 or by appointment

#### Overview

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.

#### Prerequisites

EECS 310 and EECS 311.

#### Required Text

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

#### Reference Book

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

#### Policies

Grading: 40% Homework     30% Take-home exam     30% Final exam
Late policy: -40% per day

#### Homeworks

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

#### Lecture schedule

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