EECS 336 Design and Analysis of Algorithms

Course news group

Time & Place

TTh 930-1050 TECH LG76

Instructor

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

TA

Mr. Debasish Das
ddas AT 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

Reference Book

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 Solutions
Homework 2 (1/16 out, 1/23 due): arithmic and cryptography algorithms Solutions
Homework 3 (1/23 out, 1/30 due): divide-and-conquer and graphs Solutions
Homework 4 (1/30 out, 2/6 due): divide-and-conquer and path algorithms Solutions
Homework 5 (2/6 out, 2/13 due): greedy algorithms Solutions
Homework 6 (2/13 out, 2/20 due): greedy algorithm and dynamic programming Solutions
Take home exam (2/20 out, 2/27 due): pdf
Homework 7 (2/27 out, 3/5 due): max flow and linear programming Solutions
Homework 8 (3/5 out, 3/12 due):

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

Please check back often to the main page located at Professor (Professor Hai Zhou's website) for updates and course material down-loading.