Computer Science 282

Design and Analysis of Efficient Algorithms

Fall 2015

Instructor: Daniel Stefankovic
Class: Tuesday, Thursday 11:05am-12:20pm, B&L 109.
Instructor office hours (CSB 620): 1pm-2pm (Tuesdays and Thursdays).
TAs: Rupam Acharyya, Maria Janczak, Ryan Lee, Jacob Margolis, Adam Scrivener, Hassler Thurston, Gabriel Werman.
TA office hours: Rupam Acharyya (CSB 630) 4pm-5pm (Mondays and Wednesdays)

Problem sessions: during weeks when the homework is due or there is an exam

• Monday 6:30pm - 7:30pm in Goergen 108
• Tuesday 6:00pm - 7:00pm in Goergen 108
• Wednesday 6:15pm - 7:15pm in Goergen 108
• Wednesday 7:30pm - 8:30pm in Goergen 108

Textbooks (all on a 2 hour reserve in the library):

• required: [DPV] = Algorithms, S. Dasgupta, C. Papadimitriou, U. Vazirani, 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; 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: Greedy algorithms/Dynamic programming

reading: [DPV] Section 5.2, Chapter 6, homework 1

Sep. 1 Tu - When does greedy algorithm for the coin change problem work?
Sep. 3 Th - Dynamic programming for the coin change problem. Knapsack (integer weights).
Sep. 8 Tu - Knapsack revisited (integer values). Longest increasing subsequence.
Sep. 10 Th - Edit distance. Chain matrix multiplication.
Sep. 15 Tu - More dynamic programming problems.
Sep. 17 Th - EXAM #1 (topics: Greedy algorithms/Dynamic programming)


TOPIC: Graph algorithms

reading: [DPV] Chapters 3, 4, 5, homework 2, homework 3


Sep. 22 Tu - Finding connected components, DFS, testing whether graph is strongly connected.
Sep. 24 Th - Linearization (topological sorting). Strongly connected components.
Sep. 29 Tu - BFS, Shortest paths (Dijkstra)
Oct. 1 Th - Dealing with negative edge weights(Bellman Ford). Floyd-Warshal.
Oct. 6 Tu - No class (Fall break).
Oct. 8 Th - Matchings.
Oct. 13 Tu - Minimum spanning trees.
Oct. 15 Th - Flows I.
Oct. 20 Tu - Flows II.
Oct. 22 Th - EXAM #2 (topics: Graph algorithms)


TOPIC: Linear programming

reading: [DPV] Chapter 7, homework 4
Oct. 27 Tu - Modeling with linear programs I (classical problems).
Oct. 29 Th - Solving systems of equations (Gaussian elimination), solving systems on inequalities (Fourier-Motzkin elimination)
Nov. 3 Tu - Duality, Modeling with linear programs II (zero-sum games).
Nov. 5 Th - Linear programming for approximation (relaxation, rounding).
Nov. 10 Tu - Solving linear programs.
Nov. 12 Th - EXAM #3 (topics: Linear programming)


TOPIC: Divide and Conquer Algorithms

reading: [DPV] Chapter 2, homework 5

Problem sessions
• Nov. 30 (Monday) 6:30pm - 7:30pm in Goergen 108
• Dec. 1 (Tuesday) 6:00pm - 7:00pm in Goergen 108
• Dec. 2 (Wednesday) 6:15pm - 7:15pm in Goergen 108
• Dec. 2 (Wednesday) 7:30pm - 8:30pm in Goergen 108



Nov. 17 Tu - recurrences, Karatsuba-Offman algorithm
Nov. 19 Th - Fast fourier transform, convolution
Nov. 24 Tu - deterministic linear-time k-select algorithm
Nov. 26 Th - No class (Thanksgiving).
Dec. 1 Tu - randomized linear-time k-select algorithm


TOPIC: NP

reading: [DPV] Chapter 8,

Dec. 3 Th - NP completness, reductions I.
Dec. 8 Tu - NP completness, reductions II.



Problem sessions
• Dec. 7 (Monday) 6:30pm - 7:30pm in Goergen 108
• Dec. 8 (Tuesday) 6:00pm - 7:00pm in Goergen 108
• Dec. 8 (Wednesday) 6:15pm - 7:15pm in Goergen 108
• Dec. 9 (Wednesday) 7:30pm - 8:30pm in Goergen 108

Dec. 10 Th - EXAM #4 (topics: Divide and Conquer Algorithms and NP)


Comprehensive final exam

Dec. 19 Saturday FINAL EXAM (4:00pm-7:00pm, B&L 109) (following university final exam schedule)

Grading

• The grade for the course is computed from the exam grade (50%), the homework grade (20%), and the final exam grade (30%).

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 full-class exams and a final exam. There will be no make-up exams.
• In the computation of the exam grade the lowest exam score will be dropped.

This course follows The University Policy on Academic Honesty .