Computer Science 282

Design and Analysis of Efficient Algorithms

Fall 2011

Instructor: Daniel Stefankovic
Class: Tuesday, 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. 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

reading: DPV Chapter 1, handout 1

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

reading: DPV Chapter 2, handout 2

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

reading: DPV Chapter 3,4, handout 3

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

reading: DPV Chapters 5,6, handout 4

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

reading: DPV Chapter 7, handout 5

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


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 in-class 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 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 .