Computer Science 282/482
Design and Analysis of Efficient
Algorithms
Fall 2017
Instructor:
Daniel Stefankovic
Class: Tuesday, Thursday 11:05am12:20pm, Wegmans 1400.
Instructor office hours (Wegmans 2315): Tuesday 12:30pm1:30pm, Thursday 12:30pm1:30pm.
TAs:
Jackson Abascal, Ben King, Shir Maimon, Ben Nemeth, Andrew ReadMcFarland, Eric Weiss, Conrad Wehner, Brandon Willet.
TA office hours: Andrew ReadMcFarland (Wegmans 3209): Monday 4pm5pm, Wednesday 4pm5pm.
Problem sessions (only in weeks with exams or when homework is due):
 Monday 6:15pm  7:15pm in Hylan 202
 Tuesday 6:15pm  7:15pm in Goergen 109
 Wednesday 6:15pm  7:15pm in Gavett 310
 Wednesday 7:40pm  8:40pm in Hutchinson 473
Textbooks (all on a 2 hour reserve in the library):

recommended (available in the campus bookstore): [CLRS] = Introduction to Algorithms (3rd edition), T. Cormen, C. Leiserson, R. Rivest, and C Stein, 2009.

recommended: [DPV] = Algorithms, S. Dasgupta, C. Papadimitriou, U. Vazirani, 2006.
Other resources/recommended reading (all on a 2 hour reserve in the library; or free):

Algorithms, J. Erickson, 2013.

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.
 Algorithms, R. Sedgewick, K. Wayne, 2011.
 The Algorithm Design Manual, S. Skiena, 2008.
Prerequisites: CSC162 or CSC172 or MTH172.
Schedule
TOPIC: Dynamic programming (homework #1 due Sep. 7, exam #1 on Sep. 14)
Aug. 31 Th  Dynamic programming for the coin change problem. Knapsack (integer weights).
Sep. 5 Tu  Knapsack revisited (integer values). Longest increasing subsequence.
Sep. 7 Th  Edit distance. Chain matrix multiplication.
Sep. 12 Tu  More dynamic programming problems.
Sep. 14 Th  EXAM #1 (topics: Dynamic programming)
TOPIC: Graph algorithms (homework #2 due Oct. 5, homework #3 due Oct. 19, exam #2 on Oct. 26)
Problem sessions:
 Oct. 2 (Monday) 6:15pm  7:15pm in Hylan 202
 Oct. 3 (Tuesday) 6:15pm  7:15pm in Goergen 109
 Oct.4 (Wednesday) 6:15pm  7:15pm in Gavett 310
 Oct. 4 (Wednesday) 7:40pm  8:40pm in Hutchinson 473
 Oct. 16 (Monday) 6:15pm  7:15pm in Hylan 202
 Oct. 17 (Tuesday) 6:15pm  7:15pm in Goergen 109
 Oct. 18 (Wednesday) 6:15pm  7:15pm in Gavett 310
 Oct. 18 (Wednesday) 7:40pm  8:40pm in Hutchinson 473
 Oct. 23 (Monday) 6:15pm  7:15pm in Hylan 202
 Oct. 24 (Tuesday) 6:15pm  7:15pm in Goergen 109
 Oct. 25 (Wednesday) 6:15pm  7:15pm in Gavett 310
 Oct. 25 (Wednesday) 7:40pm  8:40pm in Hutchinson 473
Sep. 19 Tu  Finding connected components, DFS, testing whether graph is strongly connected
Sep. 21 Th  Linearization (topological sorting). Strongly connected components.
Sep. 26 Tu  BFS, Shortest paths (Dijkstra)
Sep. 28 Th  Dealing with negative edge weights (Bellman Ford). FloydWarshal.
Oct. 3 Tu  Matchings I.
Oct. 5 Th  Matchings II.
Oct. 10 Tu  No class (Fall break).
Oct. 12 Th  Minimum spanning trees.
Oct. 17 Tu  Flows I.
Oct. 19 Th  Flows II.
Oct. 24 Tu  More graph algorithms.
Oct. 26 Th  EXAM #2 (topics: Graph algorithms)
TOPIC: Linear programming (homework #4 due Nov. 9, exam #3 on Nov. 16)
Problem sessions:
 Nov. 6 (Monday) 6:15pm  7:15pm in Hylan 202
 Nov. 7 (Tuesday) 6:15pm  7:15pm in Goergen 109
 Nov. 8 (Wednesday) 6:15pm  7:15pm in Gavett 310
 Nov. 8 (Wednesday) 7:40pm  8:40pm in Hutchinson 473
 Nov. 13 (Monday) 6:15pm  7:15pm in Hylan 202
 Nov. 14 (Tuesday) 6:15pm  7:15pm in Goergen 109
 Nov. 15 (Wednesday) 6:15pm  7:15pm in Gavett 310
 Nov. 15 (Wednesday) 7:40pm  8:40pm in Hutchinson 473
Oct. 31 Tu  Modeling with linear programs I (classical problems).
Nov. 2 Th  Solving systems of equations (Gaussian elimination), solving systems on inequalities (FourierMotzkin elimination)
Nov. 7 Tu  Duality, Modeling with linear programs II (zerosum games).
Nov. 9 Th  Linear programming for approximation (relaxation, rounding).
Nov. 14 Tu  Solving linear programs.
Nov. 16 Th  EXAM #3 (topics: Linear programming)
TOPIC: Divide and Conquer Algorithms (homework #5 due Dec. 7)
Problem sessions:
 Dec. 4 (Monday) 6:15pm  7:15pm in Hylan 202
 Dec. 5 (Tuesday) 6:15pm  7:15pm in Goergen 109
 Dec. 6 (Wednesday) 6:15pm  7:15pm in Gavett 310
 Dec. 6 (Wednesday) 7:40pm  8:40pm in Hutchinson 473
Nov. 21 Tu  recurrences, KaratsubaOffman algorithm
Nov. 23 Th  No class (Thanksgiving).
Nov. 28 Tu  Fast fourier transform, convolution
Nov. 30 Th  deterministic lineartime kselect algorithm
Dec. 5 Tu  randomized lineartime kselect algorithm
TOPIC: NP
Dec. 7 Th  NP completness, reductions I.
Dec. 12 Tu  NP completness, reductions II.
Comprehensive final exam
Dec. 21 Thursday FINAL EXAM (4:00pm7:00pm, Wegmans 1400)
(following university final exam schedule)
Grading

The grade for the course is computed from the exam grade (54%), the homework grade (10%), and
the final exam grade (36%).
Homework Rules
 Homework is collected on the due date, before class, in the classroom.
 No late homework will be accepted without instructor's
permission (a permission must be requested at least 24 hours
before the due date).
 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. No electronic devices (calculators, phones, computers, etc).
 There will be 3
fullclass exams and a final exam. There will be no makeup exams.
This course follows
The University Policy on Academic Honesty .