Computer Science 282
Design and Analysis of Efficient
Algorithms
Fall 2011
Instructor:
Daniel Stefankovic Class: Tuesday,
Thursday 11:05am12:20pm, CSB 601.
Instructor office hours (CSB 620): Monday 4:45pm  5:45pm (and by appointment).
TA: Qi Ge (CSB 728)
TA office hours: Wednesday 4:45  5:45pm (and by appointment)
"Exam" problem sessions (usually held by the instructor): CSB 601, Mondays before exams, 4:45pm  5:45pm.
"Homework" problem sessions (starring Rintaro Kuroiwa and Josh Pawlicki): CSB 601, Wednesday 6:15  7:15pm.
Textbooks (all on a 2 hour reserve in the library):
 required: Algorithms, S. Dasgupta, C. Papadimitriou, U.
Vazirani (a
draft is available online), 2006.
 recommended: 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.
Course google group.
Prerequisites: CSC162 or CSC172 or MTH172.
Schedule
TOPIC: Number Theory/Cryptography
Sep. 1 Th  Why is number theory interesting (RSA)? Basic operations (addition, multiplication, division)
Sep. 6 Tu  GCD. Euclid's algorithm. Modular arithmetic. Extended Euclid's algorithm.
Sep. 8 Th  Primality testing.
Sep. 13 Tu  EXAM #1
TOPIC: Divide and Conquer Algorithms
Sep. 15 Th  recurrences, KaratsubaOffman
Sep. 20 Tu  Fast fourier transform
Sep. 22 Th  deterministic lineartime kselect algorithm
Sep. 27 Tu  EXAM #2
TOPIC: Graph algorithms
Sep. 29 Th  Finding connected components, DFS, testing whether graph is strongly connected.
Oct. 4 Tu  Linearization (topological sorting). Strongly connected components.
Oct. 6 Th  BFS, Shortest paths  Dijkstra.
Oct. 11 Tu  no class (fall break)
Oct. 13 Th  Dealing with negative edge weights(Bellman Ford). FloydWarshal.
Oct. 18 Tu  Minimum spanning trees.
Oct. 20 Th  Matchings.
Oct. 25 Tu  EXAM #3
TOPIC: Greedy algorithms/Dynamic programming
Oct. 27 Th  When does greedy algorithm for the coin change problem work?
Nov. 1 Tu  Dynamic programming for the coin change problem. Knapsack (integer weights).
Nov. 3 Th  Knapsack revisited (integer values). Longest increasing subsequence.
Nov. 8 Tu  Edit distance. Chain matrix multiplication.
Nov. 10 Th  to be determined
Nov. 15 Tu  EXAM #4
TOPIC: Linear programming
Nov. 17 Th  Solving systems of equations, Rank of a matrix, Gaussian elimination.
Nov. 22 Tu  Linear programming, duality, zerosum games.
Nov. 24 Th  no class (thanksgiving)
Nov. 29 Tu  Solving linear programs  simplex algorithm.
Dec. 1 Th  Linear programming for approximation (relaxation, rounding).
Dec. 6 Tu  EXAM #5
TOPIC: NP
reading: DPV Chapters 8, no handout.
Dec. 8 Th  NP completness, reductions I.
Dec. 13 Tu  NP completness, reductions II.
Comprehensive final exam
Dec. 21 Wednesday FINAL EXAM (4:00pm, CSB 601)
Grading
The
grade for the course is the minimum of the
exam grade and the
homework grade.
 The homework grade is the better of the basic homework grade, the mixed homework grade, and the advanced homework grade.
 The basic homework grade is based on the points from the basic homework problems and is in the range E to B+.
 The advanced homework grade is based on the points from the advanced homework problems and is in the range E to A.
 The mixed homework grade is based on the points from the basic and the advanced homework problems and is in the range E to A.
 The exam grade is the better of the basic exam grade, the mixed exam grade, and the advanced exam grade.
 The basic exam grade is based on the points from the basic exam problems and is in the range E to B+.
 The advanced exam grade is based on the points from the advanced exam problems and is in the range E to A.
 The mixed exam grade is based on the points from the basic and advanced exam problems and is in the range E to A.
 The inclass exams contribute 60% to the exam grades; the final exam contributes 40% to the exam grades.
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 (this is done separately for the basic and the advanced parts).
 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 5
fullclass exams and a final exam. There will be no makeup quizzes.
 In the final evaluation everybody's one lowest exam
score will be dropped (this is done separately for the basic and the advanced parts).
This course follows
The University Policy on Academic Honesty .