Computer Science 282/482

Design and Analysis of Efficient Algorithms

Fall 2022

Instructor: Daniel Stefankovic
Class: Tuesday, Thursday 11:05am-12:20pm, Wegmans 1400.
Instructor office hours: ONLINE (zoom link on blackboard) Monday 8:30pm-9:30pm and Wednesday 8:30pm-9:30pm.

TAs: Shengyi Jia (sjia6@u.rochester.edu), Yurong Liu (yliu217@u.rochester.edu), Zeyu Nie (znie2@u.rochester.edu).

Problem sessions (only in weeks with exams or when homework is due; full schedule is below):

• Monday 6:15pm - 7:15pm in Hylan Building Room 202 (Shengyi Jia)
• Tuesday 6:15pm - 7:15pm Goergen Hall Room 109 (?)
• Wednesday 6:15pm - 7:15pm in Gavett Hall Room 310 (?)

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

A textbook is not required for this course. Homework problem statements will be self contained. It is a good idea to have access to the recommended books (electronic or paper; the version/edition is not too important) while taking the course and after.

• 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, Linear Programming. (Homework #1 due Sep. 15, Homework #2 due Sep. 29, Exam #1 on Oct. 13.)

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


• [CLRS] Chapter 29,
• linear programming (Erickson).
• [DPV] Chapter 7.

Problem sessions:

• Sep. 12 (Monday) 6:15pm - 7:15pm in Hylan Building Room 202 (Shengyi Jia)
• Sep. 13 (Tuesday) 6:15pm - 7:15pm in Goergen Hall Room 109 (Yurong Liu)
• Sep. 14 (Wednesday) 6:15pm - 7:15pm in Gavett Hall Room 310 (Zeyu Nie)
• Sep. 26 (Monday) 6:15pm - 7:15pm in Hylan Building Room 202 (Shengyi Jia)
• Sep. 27 (Tuesday) 6:15pm - 7:15pm in Goergen Hall Room 109 (Yurong Liu)
• Sep. 28 (Wednesday) 6:15pm - 7:15pm in Gavett Hall Room 310 (Zeyu Nie)
• Oct. 3 (Monday) 6:15pm - 7:15pm in Hylan Building Room 202 (Shengyi Jia)
• Oct. 4 (Tuesday) 6:15pm - 7:15pm in Goergen Hall Room 109 (Yurong Liu)
• Oct. 5 (Wednesday) 6:15pm - 7:15pm in Gavett Hall Room 310 (Zeyu Nie)

Sep. 1 Th - Introduction.


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


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


Sep. 20 Tu - More dynamic programming problems.
Sep. 22 Th - Modeling with linear programs I (classical problems).


Sep. 27 Tu - Solving systems of equations (Gaussian elimination), solving systems on inequalities (Fourier-Motzkin elimination).
Sep. 29 Th - Duality, Modeling with linear programs II (zero-sum games).


Oct. 4 Tu - Linear programming for approximation (relaxation, rounding).
Oct. 6 Th - More linear programming.


Oct. 11 Tu - FALL BREAK (no class).
Oct. 13 Th - EXAM #1 (topics: Greedy algorithms/Dynamic programming/Linear Programming)


TOPIC: Graph algorithms. (Homework #3 due Oct. 27, Homework #4 due Nov. 10, Exam #2 on Nov. 17.)

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.

Problem sessions:

• Oct. 24 (Monday) 6:15pm - 7:15pm in Hylan Building Room 202 (Shengyi Jia)
• Oct. 25 (Tuesday) 6:15pm - 7:15pm in Goergen Hall Room 109 (Yurong Liu)
• Oct. 26 (Wednesday) 6:15pm - 7:15pm in Gavett Hall Room 310 (Zeyu Nie)


• Nov. 7 (Monday) 6:15pm - 7:15pm in Hylan Building Room 202 (Shengyi Jia)
• Nov. 8 (Tuesday) 6:15pm - 7:15pm in Goergen Hall Room 109 (Yurong Liu)
• Nov. 9 (Wednesday) 6:15pm - 7:15pm in Gavett Hall Room 310 (Zeyu Nie)


• Nov. 14 (Monday) 6:15pm - 7:15pm in Hylan Building Room 202 (Shengyi Jia)
• Nov. 15 (Tuesday) 6:15pm - 7:15pm in Goergen Hall Room 109 (Yurong Liu)
• Nov. 16 (Wednesday) 6:15pm - 7:15pm in Gavett Hall Room 3100 (Zeyu Nie)


Oct. 18 Tu - Undirected graphs, finding connected components, DFS.
Oct. 20 Th - Directed graphs, strong connectedness, linearization (topological sorting).


Oct. 25 Tu - Strongly connected components.
Oct. 27 Th - BFS, Shortest paths (Dijkstra).


Nov. 1 Tu - Dealing with negative edge weights (Bellman Ford). Floyd-Warshal.
Nov. 3 Th - Matchings I.


Nov. 8 Tu - Matchings II.
Nov. 10 Th - Minimum spanning trees.


Nov. 15 Tu - (review/buffer)
Nov. 17 Th - EXAM #2 (topics: Graph algorithms)


TOPIC: Reductions (NP-completeness), Divide and Conquer Algorithms. (no homework, no exam)

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


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

Nov. 22 Tu - (online/zoom class) NP completness, reductions I.
Nov. 24 Th - THANKSGIVING (no class).

Nov. 29 Tu - NP completness, reductions II.
Dec. 1 Th - Fast fourier transform, convolution I.

Dec. 6 Tu - Fast fourier transform, convolution II.
Dec. 8 Th - Divide and Conquer Algorithms .

Dec. 13 Tu - (review/buffer)


Comprehensive final exam

Dec. 20 Tuesday FINAL EXAM (7:15pm-10:15pm, location to be determined) (following university final exam schedule)

Grading

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

Homework Rules

• Homework will be submitted on Gradescope, the deadline is 11am on the date the homework is due.
• There will be the following two types of homework.
  • Major homework will require typeseting one or more of the following: algorithms, pseudocode, code, reasoning, proofs. Major homework is submitted on gradescope and will be graded by the TAs.
  • Minor homework will be answering questions on gradescope. Minor homework will be autograded.
• Major homework must be typeset (for example, you can use LaTeX, word, powerpoint (of course, any open office or google variants are fine), etc).
• 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.