Computer Science 282
Design and Analysis of Efficient
Algorithms
Fall 2012
Instructor:
Daniel Stefankovic Class: Tuesday,
Thursday 11:05am12:20pm, CSB 209.
Instructor office hours (CSB 620): Tuesday 12:30pm1:30pm, Thursday 12:30pm1:30pm
TAs: Tivadar Papai, Ian Perera, Julian Lunger
TA office hours: Tivadar Papai (CSB 725) Wednesday 4pm5pm, Ian Perera (CSB 607) Monday 3pm4pm.
Textbooks (all on a 2 hour reserve in the library):
 required: [DPV] = Algorithms, S. Dasgupta, C. Papadimitriou, U.
Vazirani (a
draft is available online), 2006.
 recommended: [CLRS] = Introduction to Algorithms (3rd edition),
T. Cormen, C. Leiserson, R. Rivest, and C. Stein, 2009.
Other resources/recommended reading (all on a 2 hour reserve in the library):

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.
 Algorithms
Algorithms, R. Johnsonbaugh, M. Schaefer, 2003.
 How to Think About Algorithms
Algorithms, J. Edmonds, 2008.

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.
Prerequisites: CSC162 or CSC172 or MTH172.
Schedule
Aug. 30 Th  Introduction
TOPIC: Greedy algorithms/Dynamic programming
Sep. 4 Tu  When does greedy algorithm for the coin change problem work?
Sep. 6 Th  Dynamic programming for the coin change problem. Knapsack (integer weights).
Sep. 11 Tu  Knapsack revisited (integer values). Longest increasing subsequence.
Sep. 13 Th  Edit distance. Chain matrix multiplication.
Sep. 18 Tu  More dynamic programming problems.
Sep. 20 Th  EXAM #1
TOPIC: Graph algorithms
Sep. 25 Tu  Finding connected components, DFS, testing whether graph is strongly connected.
Sep. 27 Th  Linearization (topological sorting). Strongly connected components.
Oct. 2 Tu  BFS, Shortest paths (Dijkstra)
Oct. 4 Th  Dealing with negative edge weights(Bellman Ford). FloydWarshal.
Oct. 9 Tu  no class (fall break)
Oct. 11 Th  Matchings.
Oct. 16 Tu  Minimum spanning trees.
Oct. 18 Th  Flows I.
Oct. 23 Tu  Flows II.
Oct. 25 Th  EXAM #2
TOPIC: Linear programming
Oct. 30 Tu  Modeling with linear programs I (classical problems).
Nov. 1 Th  Solving systems of equations (Gaussian elimination), solving systems on inequalities (FourierMotzkin elimination)
Nov. 6 Tu  Duality, Modeling with linear programs II (zerosum games).
Nov. 8 Th  Linear programming for approximation (relaxation, rounding).
Nov. 13 Tu  EXAM #3
TOPIC: String matching
Nov. 15 Th  Suffix trees I.
Nov. 20 Tu  Suffix trees II.
Nov. 22 Th  no class (thanksgiving)
Nov. 27 Tu  Convolution, string matching with don't cares.
Nov. 29 Th  Fast Fourier Transform
Dec. 4 Tu  EXAM #4
TOPIC: NP
reading: [DPV] Chapter 8,
Dec. 6 Th  NP completness, reductions I.
Dec. 11 Tu  NP completness, reductions II.
Comprehensive final exam
Dec. 20 Thursday FINAL EXAM (4:00pm, CSB 209)
(following university final exam schedule)
Grading

The grade for the course is the minimum of the exam grade and the homework grade.
 The inclass exams contribute
60% to the exam grade; the final exam contributes 40% to the exam grade.
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
the lowest homework score will be
dropped.
 You may work with other people on the
homework, but you must each write up your solutions separately
(without any written aid). If you work with other people, indicate
who you worked with on your solution.
Test Rules
 All tests are closed book. No text
or notes, no scratch paper allowed.
 There will be 4
fullclass exams and a final exam. There will be no makeup exams.
 In the final evaluation everybody's one lowest exam
score will be dropped.
This course follows
The University Policy on Academic Honesty .