Computer Science 282/482

Design and Analysis of Efficient Algorithms

Fall 2019

Instructor: Daniel Stefankovic
Class: Tuesday, Thursday 11:05am-12:20pm, Wegmans 1400.
Instructor office hours (Wegmans 2315): Tuesday 12:30pm-1:30pm, Thursday 12:30pm-1:30pm.

TAs: Laasya Bangalore, Lusine Keshishyan, Patrick Phillips, Daniel Ro, Yiyang Su, Hanlin Tang, Yipeng Zhang

TA office hours:

Laasya Bangalore (Wegmans 4205): Wednesday 3pm-5pm
Hanlin Tang (Wegmans 3209): Monday 3pm-5pm


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: Greedy algorithms. Dynamic programming. (Homework #1 due Sep. 12, exam #1 on Sep. 19.)

Reading:
• [CLRS] Chapter 15,
• [Erickson] Chapter 3 (Dynamic programming),
• [DPV] Section 5.2, Chapter 6,
• advanced dynamic programming (Erickson).

homework 1

Problem sessions:

• Sep. 9 (Monday) 6:15pm - 7:15pm in Hylan 202 (Daniel Ro)
• Sep. 10 (Tuesday) 6:15pm - 7:15pm in Goergen 109 (Yiyang Su)
• Sep. 11 (Wednesday) 6:15pm - 7:15pm in Gavett 310 (Hanlin Tang)
• Sep. 11 (Wednesday) 7:40pm - 8:40pm in Hutchinson 473 (Hanlin Tang)

• Sep. 16 (Monday) 6:15pm - 7:15pm in Hylan 202 (Patrick Phillips)
• Sep. 17 (Tuesday) 6:15pm - 7:15pm in Goergen 109 (Yipeng Zhang)
• Sep. 18 (Wednesday) 6:15pm - 7:15pm in Gavett 310 (Yipeng Zhang)
• Sep. 18 (Wednesday) 7:40pm - 8:40pm in Hutchinson 473 (Patrick Phillips)

Aug. 29 Th - Introduction.


Sep. 3 Tu - When does greedy algorithm for the coin change problem work?
Sep. 5 Th - Dynamic programming for the coin change problem. Knapsack (integer weights).


Sep. 10 Tu - Knapsack revisited (integer values). Longest increasing subsequence.
Sep. 12 Th - Edit distance. Chain matrix multiplication.


Sep. 17 Tu - More dynamic programming problems.
Sep. 19 Th - EXAM #1 (topics: Greedy algorithms/Dynamic programming)


TOPIC: Graph algorithms. (Homework #2 due Oct. 10, homework #3 due Oct. 24, exam #2 on Oct. 31.)

Reading:
• [CLRS] Chapters 22, 23, 24, 25, 26 (excluding sections 26.4, 26.5),
• [Erickson] Chapters 4,5,6,7,8,9,10,11 (Graph algorithms),
• [DPV] Chapters 3, 4, 5.

homework 2

homework 3

Problem sessions:

• Oct. 7 (Monday) 6:15pm - 7:15pm in Hylan 202 (Patrick Phillips)
• Oct. 8 (Tuesday) 6:15pm - 7:15pm in Goergen 109 (Yipeng Zhang)
• Oct. 9 (Wednesday) 6:15pm - 7:15pm in Gavett 310 (Yipeng Zhang)
• Oct. 9 (Wednesday) 7:40pm - 8:40pm in Hutchinson 473 (Patrick Phillips)


• Oct. 21 (Monday) 6:15pm - 7:15pm in Hylan 202 (Daniel Ro)
• Oct. 22 (Tuesday) 6:15pm - 7:15pm in Goergen 109 (Yiyang Su)
• Oct. 23 (Wednesday) 6:15pm - 7:15pm in Gavett 310 (Lusine Keshishyan)
• Oct. 23 (Wednesday) 7:40pm - 8:40pm in Hutchinson 473 (Lusine Keshishyan)


• Oct. 28 (Monday) 6:15pm - 7:15pm in Hylan 202 (Laasya Bangalore)
• Oct. 29 (Tuesday) 6:15pm - 7:15pm in Goergen 109 (Laasya Bangalore)
• Oct. 30 (Wednesday) 6:15pm - 7:15pm in Gavett 310 (Lusine Keshishyan)
• Oct. 30 (Wednesday) 7:40pm - 8:40pm in Hutchinson 473 (Lusine Keshishyan)


Sep. 24 Tu - Undirected graphs, finding connected components, DFS.
Sep. 26 Th - Directed graphs, strong connectedness, linearization (topological sorting).


Oct. 1 Tu - Strongly connected components.
Oct. 3 Th - BFS, Shortest paths (Dijkstra)


Oct. 8 Tu - Dealing with negative edge weights (Bellman Ford). Floyd-Warshal.
Oct. 10 Th - Matchings I.


Oct. 15 Tu - No class (Fall break).
Oct. 17 Th - Matchings II.


Oct. 22 Tu - Minimum spanning trees.
Oct. 24 Th - Flows I.


Oct. 29 Tu - Flows II.
Oct. 31 Th - EXAM #2 (topics: Graph algorithms)


TOPIC: Linear programming. Reductions (NP-completeness). (Homework #4 due Nov. 21, no exam)

Reading:
• [CLRS] Chapter 29,
• linear programming (Erickson).
• [DPV] Chapter 7.
• [CLRS] Chapter 34,
• [Erickson] Chapter 12 (NP),
• [DPV] Chapter 8.

homework 4.

Problem sessions:
• Nov. 18 (Monday) 6:15pm - 7:15pm in Hylan 202 (Daniel Ro)
• Nov. 19 (Tuesday) 6:15pm - 7:15pm in Goergen 109 (Yiyang Su)
• Nov. 20 (Wednesday) 6:15pm - 7:15pm in Gavett 310 (Hanlin Tang)
• Nov. 20 (Wednesday) 7:40pm - 8:40pm in Hutchinson 473 (Hanlin Tang)


Nov. 5 Tu - Modeling with linear programs I (classical problems).
Nov. 7 Th - Solving systems of equations (Gaussian elimination), solving systems on inequalities (Fourier-Motzkin elimination).


Nov. 12 Tu - Duality, Modeling with linear programs II (zero-sum games).
Nov. 14 Th - Linear programming for approximation (relaxation, rounding).


Nov. 19 Tu - More linear programming.
Nov. 21 Th - NP completness, reductions I.


TOPIC: Divide and Conquer Algorithms (Homework #5 due Dec. 5, no exam)

reading:
• [CLRS] Chapters 4, 9,30,
• FFT (Erickson),
• [DPV] Chapter 2.

homework 5

Problem sessions:

• Dec. 2 (Monday) 6:15pm - 7:15pm in Hylan 202 (Daniel Ro)
• Dec. 3 (Tuesday) 6:15pm - 7:15pm in Goergen 109 (Yiyang Su)
• Dec. 4 (Wednesday) 6:15pm - 7:15pm in Gavett 310 (Laasya Bangalore)
• Dec. 4 (Wednesday) 7:40pm - 8:40pm in Hutchinson 473 (Laasya Bangalore)


Nov. 26 Tu - NP completness, reductions II.
Nov. 28 Th - THANKSGIVING.

Dec. 3 Tu - Fast fourier transform, convolution I.
Dec. 5 Th - Fast fourier transform, convolution II.

Dec. 10 Tu - Linear-time k-select algorithm (randomized, deterministic).



Comprehensive final exam

Dec. 19 Thursday FINAL EXAM (4:00pm-7:00pm, Douglass Ballroom) (following university final exam schedule)

Grading

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

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 2 full-class exams and a final exam. There will be no make-up exams.

This course follows The University Policy on Academic Honesty .