Computer Science 282

Design and Analysis of Efficient Algorithms

Fall 2007

Textbooks:

• Algorithms, S. Dasgupta, C. Papadimitriou, U. Vazirani (a draft is available online), 2006.
  
• Introduction to Algorithms (2nd edition), T. Cormen, C. Leiserson, R. Rivest, and C. Stein, 2001.

Other resources/recommended reading:

• Algorithm Design, J. Kleinberg and E. Tardos, 2005.
• The Design and Analysis of Algorithms, D. Kozen, 1991.
• The Design and Analysis of Computer Algorithms, A. Aho, J. Hopcroft, J. Ulman, 1974.
• Probability and Computing: Randomized Algorithms and Probabilistic Analysis, M. Mitzenmacher, E. Upfal, 2005.
• Randomized Algorithms, R. Motwani, P. Raghavan, 1995.
• Approximation Algorithms, V. Vazirani, 2004.

Schedule

Sep. 4 Tu - Quiz #0, homework 1

TOPIC: Number Theory/Cryptography

reading: DPV Chapter 1, homework 2

Sep. 6 Th - Why is number theory interesting (RSA)? Basic operations (addition, multiplication, division) (slides)
Sep. 11 Tu - GCD. Euclid's algorithm. Modular arithmetic. Extended Euclid's algorithm.
Sep. 13 Th - Primality testing. (slides)
Sep. 18 Tu QUIZ #1 homework 3


TOPIC: Divide and Conquer Algorithms

reading: DPV Chapter 2, homework 4

Sep. 20 Th - recurrences, Karatsuba-Offman (slides) (handout)
Sep. 25 Tu - deterministic linear-time k-select algorithm, basics of probability (slides)
Sep. 27 Th - Basics of probability, randomized k-select (slides)
Oct. 2 Tu - Fourier transform (slides)
Oct. 4 Th - QUIZ #2 homework 5


TOPIC: Graph algorithms

reading: DPV Chapter 3,4, homework 6

Oct. 9 Tu - Finding connected components, DFS, testing whether graph is strongly connected.
Oct. 11 Th - Linearization (topological sorting). Strongly connected components.
Oct. 16 Tu - BFS, Shortest paths - Dijkstra.
Oct. 18 Th - Dealing with negative edge weights(Bellman Ford). Floyd-Warshal.
Oct. 23 Tu - Maximum matchings in bipartite graphs.
Oct. 25 Th QUIZ #3


TOPIC: Greedy algorithms/Dynamic programming

reading: DPV Chapters 5,6, homework 7

Oct. 30 Tu - When does greedy algorithm for the coin change problem work?
Nov. 1 Th - Dynamic programming for the coin change problem. Knapsack (integer weights).
Nov. 6 Tu - Knapsack revisited (integer values). Longest increasing subsequence.
Nov. 8 Th - Edit distance. Chain matrix multiplication.
Nov. 13 Tu - QUIZ #4


TOPIC: Linear programming

reading: DPV Chapter 7, homework 8

Nov. 15 Th - Solving systems of equations, Rank of a matrix, Gaussian elimination.
Nov. 20 Tu - Linear programming, duality, zero-sum games.
Nov. 22 Th (thanksgiving)
Nov. 27 Tu - Solving linear programs - simplex algorithm.
Nov. 29 Th QUIZ #5


TOPIC: Hardness/Coping with hardness

reading: DPV Chapters 8,9, homework 9

Dec. 4 Tu - NP completness, reductions.
Dec. 6 Th - Approximation algorithms: vertex cover, clustering.
Dec. 11 Tu - Approximation algorithms: metric TSP, knapsack.
Dec. 13 Th QUIZ #6


Comprehensive final exam

Dec. 16 Sunday FINAL EXAM (7:15pm, CSB 601)

Grading

• Homeworks: 15%.
• Quizzes: 60%.
• Final: 25%.

Homework Rules

• Homework is collected on the due date, before class.
• No late homework will be accepted without instructor's permission (a permission must be requested at least 24 hours before the due date).
• In the final evaluation everybody's two lowest homework scores will be dropped.
• Each problem must be written on a separate letter-size paper.
• You may work with one other person on homeworks, but you must each write up your solutions separately (without any written aid). If you work with another person, indicate who you worked with on your solution (thus you should each indicate each other).

Test Rules

• All tests are closed book. No text or notes, no scratch paper allowed.
• There will be 6 quizzes. There will be no make-up quizzes.
• In the final evaluation everybody's one lowest quiz score will be dropped.