EECS 336: Design & Analysis of Algorithms

Kleinberg & Tardos, Algorithm Design

Required Textbook: Kleinberg and Tardos, Algorithm Design, 2005.

Current Term: Fall 2017.
Previous Terms: Spring 2017, Fall 2015.

Synopsis:
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 212 (Mathematical Foundations of Computer Science) and EECS 214 (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.

Tentative Schedule:

Week 1:

  • Course overview: computing Fibonacci numbers. (Chapter 1)
  • Review of runtime analysis, graphs, and basic graph algorithms. (Chapters 2 and 3)

Week 2:

  • Greedy algorithms: interval scheduling. (Chapter 4)
  • Greedy algorithms: minimum spanning trees, matroids. (Chapter 4)

Week 3:

  • Greedy algorithms: greedy by value, matroids (Chapter 4)
  • Dynamic Greedy:¬†shortest paths, MSTs (Chapter 4)

Week 4:

  • Divide and conquer: merge sort, recurrence relations, public key cryptography, repeated squaring (Chapter 5)
  • Divide and conquer: integer multiply, convolution, fast Fourier transform (Chapter 5)

Week 5:

  • Dynamic programming: memoization, weighted interval scheduling (Chapter 6)
  • Dynamic programming: integer knapsack, uniform pricing (cf. Chapter 6).

Week 6:

  • MIDTERM.
  • Dynamic Programming: Shortest Paths (with negative edge weights; Chapter 6)

Week 7:

  • Reductions, Network flow, Bipartite Matching (Chapter 7)
  • Network flow. (Chapter 7)

Week 8:

  • NP and intractability: NP, polynomial time reductions decision problems. (Chapter 8)
  • NP and intractability: NP, 3-SAT, Hamiltonian Cycle¬†(Chapter 8)

Week 9:

  • NP and intractability: Independent set (Chapter 8)
  • NP and intractability: NP, CIRCUIT-SAT, 3-SAT (Chapter 8)

Week 10:

  • Approximation algorithms: TSP, metric TSP, knapsack (Chapter 11)
  • Approximation algorithms: pseudo polynomial time, PTAS, knapsack (Chapter 11)