Home

EECS 336 -- Design and Analysis of Algorithms -- Winter 2011

Share/Save/Bookmark

Required Text: Kleinberg and Tardos, Algorithm Design, Addison-Wesley, 2005. [order from amazon.com]alt
Lectures: Tuesday and Thursday 2:00-3:20 in Tech LR2.
Instructor: Jason D. Hartline.
Office Hours: Wednesday 2:00-3:00, or by appointment; Ford 3-329.

Teaching Assistant:Nima Haghpanah
Problem Session: Monday, 5-6pm; location Tech LR5.
Office Hours: Tuesday 1-2pm; Ford 3-340.

Overview. Algorithm design and analysis is fundamental to all areas of computer science and gives a rigorous framework for the study optimization. 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, reductions, and randomized algorithms. Important themes that will be developed in the course include the 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, 15% Midterm, 25% Final, 3% classroom participation (bonus).

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. You may consult your text book and course notes when answering homework questions; you must not consult the Internet. Homeworks are assigned in class and due on Thursday the week after (or as noted). Late homework will be accepted until Monday 5pm (in section) and will be marked down by 25% of the grade received.

Tentative Schedule:

  • Jan. 4: Course overview: computing Fibonacci numbers. (Chapter 1)
  • Jan. 6: Review of runtime analysis, graphs, and basic graph algorithms. (Chapters 2 and 3)
  • Jan. 11: Greedy algorithms: interval scheduling. (Chapter 4)
  • Jan. 13: Greedy algorithms: minimum spanning trees, matroids. (Chapter 4, Matroid Notes)
  • Jan. 18: Greedy algorithms: shortest paths, MSTs. (Chapter 4)
  • Jan. 20: Divide and conquer: merge sort, recurrence relations, public key cryptography, repeated squaring (Chapter 5)
  • Jan. 25: Divide and conquer: integer multiply, convolution, fast Fourier transform (Chapter 5)
  • Jan. 27: Dynamic programming: memoization, weighted interval scheduling, integer knapsack (Chapter 6)
  • Feb. 1: Dynamic programming: all pairs shortest paths (Chapter 6)
  • Feb. 3: Reductions, Network flow, Bipartite Matching (Chapter 7)
  • Feb. 8: MIDTERM.
  • Feb. 10: Network flow. (Chapter 7)
  • Feb. 15: NP and intractability: NP, polynomial time reductions decision problems. (Chapter 8)
  • Feb. 18: NP and intractability: NP, circuit sat (Chapter 8)
  • Feb. 22: NP and intractability: circuit sat, 3-sat (Chapter 8)
  • Feb. 24: NP and intractability: independent set, vertex cover, hamiltonian cycle, TSP.
  • Mar. 1: Approximation algorithms: TSP, metric TSP, knapsack (Chapter 11)
  • Mar. 3: Approximation algorithms: pseudo polynomial time, PTAS, knapsack (Chapter 11)
  • Mar. 8: Online algorithms: ski-renter, secretary
  • Mar. 10: FINAL (cumulative).

[cover]

 

Search subsets