Computer Science 282
Design and Analysis of Efficient
Instructor: Daniel Stefankovic
Thursday 11:05am-12: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.
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):
Course google group.
Algorithm Design, J. Kleinberg and E. Tardos, 2005.
- The Design and Analysis of Algorithms, D. Kozen,
- The Design and Analysis of Computer
Algorithms, A. Aho, J. Hopcroft, J. Ulman, 1974.
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,
- Approximation Algorithms, V. Vazirani,
Prerequisites: CSC162 or CSC172 or MTH172.
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, Karatsuba-Offman
Sep. 20 Tu - Fast fourier transform
Sep. 22 Th - deterministic linear-time k-select 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). Floyd-Warshal.
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, zero-sum 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
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)
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 in-class exams contribute 60% to the exam grades; the final exam contributes 40% to the exam grades.
- 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.
- All tests are closed book. No text
or notes, no scratch paper allowed.
- There will be 5
full-class exams and a final exam. There will be no make-up 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