## EECS 336 - Design and Analysis of Algorithms

EECS 336 - Design and Analysis of Algorithms

Winter 2008

**Required Text:** Kleinberg and Tardos, Algorithm Design, Addison-Wesley, 2005. [order from amazon.com] **Reference Text:** Cormen, Leiserson, Rivest, and Stein *Introduction to Algorithms* (a.k.a. CLRS) **Lectures:** Tuesday and Thursday 9:30-10:50 in Tech LG66. **Instructor:** Jason D. Hartline. **Office Hours:** Wednesday 2:00-3:00, Thursday 11:00-12:00, and by appointment; Ford 3-329.

**Teaching Assistant:** Jing Xin, `j-xin [at] northwestern.edu` **Office Hours:** Monday and Friday, 2:00-3:00; Tech L444.

**Announcements:**

- Mar 18: The final is on 3/19/08 from noon to 2pm. The final is closed book. You may bring one handwritten sheet of notes with you to the test.
- Feb 5: The midterm is on 2/12/08. The midterm is closed book. You may bring one handwritten sheet of notes with you to the test.
- Feb 5: Students are highly recommended to attend Luis von Ahn's talk "Human Computation", Thursday, Feb 7th, at 4pm in Ford ITW. This talk is part of the Technology and Social Behavior Speaker Series.
- Jan 29: An integral part of giving an algorithm is proving its correctness and efficiency. All algorithms you define in homework assignments should be accompanied by these proofs.

**Overview.** Algorithm design and analysis is fundamental to all areas of computer science and gives a rigorous framework for the study optimization other disciplines. This course provides an introduction to algorithm design through a survey of the common algorithm design paradigms of greedy optimization, divide and conquer, dynamic programming, network flows, and randomized algorithms. Important themes that will be developed in the course include algorithmic abstraction-design-analysis process and computational tractability (e.g., NP-completeness).

**Prerequisites.** EECS 310 (Mathematical Foundations of Computer Science) and EECS 311 (Data Structures and Data Management) which cover abstract data types such as stacks, queues, and binary search trees; and discrete mathematics such as recurrence relations, sets, and graphs.

**Grading.** 60% Problem sets, 10% Midterm, 30% Final, (Bonus 3% classroom participation).

**Homework Policy.** Homeworks may be done in pairs. Both students must contribute to the solution of all problems. One copy of the assignment should be turned in with the names of both students on it. Both students will receive the same grade. Homeworks are assigned in class on Tuesday. Homeworks are due the following Tuesday at the beginning of class (or as noted). Homeworks turned in up to two days late will lose 25% per day they are late. Solutions will be distributed the class after homeworks are due. Homeworks will contain reading assignments.

**Tentative Schedule:**

- Jan. 8: Course overview, algorithmic abstraction-design-analysis paradigm, and the stable matching problem. (Chapter 1)
- Jan. 10: Review of runtime analysis, graphs, and basic graph algorithms. (Chapters 2 and 3)
- Jan. 15: Greedy algorithms: interval scheduling, shortest paths. (Chapter 4)
- Jan. 17: Greedy algorithms: caching. (Chapter 4)
- Jan. 22: Greedy algorithms: shortest paths, minimum spanning trees. (Chapter 4)
- Jan. 24: Divide and conquer: merge sort, recurrence relations, public key cryptography, repeated squaring (Chapter 5)
- Jan. 29: Divide and conquer: integer multiply, convolution, fast Fourier transform (Chapter 5)
- Jan. 31: Dynamic programming: memoization, weighted interval scheduling, integer knapsack (Chapter 6)
- Feb. 5: Dynamic programming: all pairs shortest paths (Chapter 6)
- Feb. 7: Network flow. (Chapter 7)
- Feb. 12: MIDTERM (on material through dynamic programming)
- Feb. 15: Applications of Network flow. (Chapter 7)
- Feb. 19: NP and intractability: NP, polynomial time reductions decision problems (Chapter 8)
- Feb. 21: NP and intractability: NP, circuit sat, 3-sat (Chapter 8)
- Feb. 26: NP and intractability: circuit sat, 3-sat, independent set (Chapter 8)
- Feb. 28: Approximation algorithms: TSP, metric TSP, knapsack (Chapter 11)
- Mar. 4: Approximation algorithms: pseudo polynomial time, PTAS, knapsack (Chapter 11)
- Mar. 6: Randomized algorithms: max-3-sat. (Chapter 13)
- Mar. 11: Randomized algorithms: global min cut (Chapter 13)
- Mar. 13: Online algorithms: ski-renter, "lost on a line", secretary.