Computer Science 282/482

Design and Analysis of Efficient Algorithms

Fall 2020

Instructor: Daniel Stefankovic
Class: Tuesday, Thursday 11:05am-12:20pm, ONLINE.
Instructor office hours (ONLINE): Monday 8:30pm-9:30pm and Wednesday 8:00am-9:00am.

TAs: Mandar Juvekar, Ben Kuehnert, Helios Nguyen, Akira Sah, Joshua Sobel, Conor Taliancich, Anis Zaman.

TA office hours:

Anis Zaman (ONLINE): Monday 7:30pm-8:30pm and Wednesday 7:30pm-8:30pm


Problem sessions (only in weeks with exams or when homework is due; full schedule is below):
• Monday 6:15pm - 7:15pm in Hoyt Hall Room 104
• Tuesday 6:15pm - 7:15pm in Hoyt Hall Room 104
• Wednesday 6:15pm - 7:15pm in Hoyt Hall Room 104
• Wednesday 7:40pm - 8:40pm ONLINE

Textbooks:

• 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:

• 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. 10, exam #1 on Sep. 17.)

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

HOMEWORK #1 is on Blackboard

Problem sessions:

• Sep. 7 (Monday) 6:15pm - 7:15pm in Hoyt Hall Room 104 (Joshua Sobel)
• Sep. 8 (Tuesday) 6:15pm - 7:15pm in Hoyt Hall Room 104 (Mandar Juvekar)
• Sep. 9 (Wednesday) 6:15pm - 7:15pm in Hoyt Hall Room 104 (Akira Sah)
• Sep. 9 (Wednesday) 7:40pm - 8:40pm ONLINE (Helios Nguyen)

• Sep. 14 (Monday) 6:15pm - 7:15pm in Hoyt Hall Room 104 (Joshua Sobel)
• Sep. 15 (Tuesday) 6:15pm - 7:15pm in Hoyt Hall Room 104 (Conor Taliancich)
• Sep. 16 (Wednesday) 6:15pm - 7:15pm in Hoyt Hall Room 104 (Akira Sah)
• Sep. 16 (Wednesday) 7:40pm - 8:40pm ONLINE (Anis Zaman)

Aug. 27 Th - Introduction.


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. (Homework #2 due Oct. 8, homework #3 due Oct. 22, exam #2 on Oct. 29.)

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 is on Blackboard

Problem sessions:

• Oct. 5 (Monday) 6:15pm - 7:15pm in Hoyt Hall Room 104 (Joshua Sobel)
• Oct. 6 (Tuesday) 6:15pm - 7:15pm in Hoyt Hall Room 104 (Conor Taliancich)
• Oct. 7 (Wednesday) 6:15pm - 7:15pm in Hoyt Hall Room 104 (Ben Kuehnert)
• Oct. 7 (Wednesday) 7:40pm - 8:40pm ONLINE (Helios Nguyen)


• Oct. 19 (Monday) 6:15pm - 7:15pm in Hoyt Hall Room 104 (Joshua Sobel)
• Oct. 20 (Tuesday) 6:15pm - 7:15pm in Hoyt Hall Room 104 (Mandar Juvekar)
• Oct. 21 (Wednesday) 6:15pm - 7:15pm in Hoyt Hall Room 104 (Ben Kuehnert)
• Oct. 21 (Wednesday) 7:40pm - 8:40pm ONLINE (Anis Zaman)


• Oct. 26 (Monday) 6:15pm - 7:15pm in Hoyt Hall Room 104 (Akira Sah)
• Oct. 27 (Tuesday) 6:15pm - 7:15pm in Hoyt Hall Room 104 (Mandar Juvekar)
• Oct. 28 (Wednesday) 6:15pm - 7:15pm in Hoyt Hall Room 1040 (Ben Kuehnert)
• Oct. 28 (Wednesday) 7:40pm - 8:40pm in ONLINE (Helios Nguyen)


Sep. 22 Tu - Undirected graphs, connected graphs, trees.
Sep. 24 Th - finding connected components, DFS.


Sep. 29 Tu - Directed graphs, strong connectedness, linearization (topological sorting).


Oct. 1 Th - Strongly connected components.


Oct. 6 Tu - BFS, Shortest paths (Dijkstra)
Oct. 8 Th - Dealing with negative edge weights (Bellman Ford). Floyd-Warshal.


Oct. 13 Tu - Matchings I.
Oct. 15 Th - Matchings II.


Oct. 20 Tu - Flows I.
Oct. 22 Th - Flows II.


Oct. 27 Tu - Minimum spanning trees.
Oct. 29 Th - EXAM #2 (topics: Graph algorithms)


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

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

Problem sessions:
• Nov. 16 (Monday) 6:15pm - 7:15pm in Hoyt Hall Room 104 (Akira Sah)
• Nov. 17 (Tuesday) 6:15pm - 7:15pm in Hoyt Hall Room 104 (Mandar Juvekar)
• Nov. 18 (Wednesday) 6:15pm - 7:15pm in Hoyt Hall Room 104 (Ben Kuehnert)
• Nov. 18 (Wednesday) 7:40pm - 8:40pm ONLINE (Conor Taliancich)


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


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


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


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

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

Problem sessions:

• Nov. 30 (Monday) 6:15pm - 7:15pm ONLINE (Helios Nguyen)
• Dec. 1 (Tuesday) 6:15pm - 7:15pm ONLINE (Conor Taliancich)
• Dec. 2 (Wednesday) 6:15pm - 7:15pm ONLINE (Anis Zaman)
• Dec. 2 (Wednesday) 7:40pm - 8:40pm ONLINE (Anis Zaman)


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

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

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



Comprehensive final exam

Dec. 17 Thursday FINAL EXAM (4:00pm-7:00pm, ONLINE) (following university final exam schedule)

Grading

• The grade for the course is computed from the exam grade (35%), the homework grade (20%), the final exam grade (40%), and class participation (5%).

Homework Rules

• Homework will be submitted on Gradescope, the deadline is 11am on the date the homework is due.
• The 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

• The exams will be through Gradescope. All tests are closed book. No text or notes. No electronic devices (calculators, phones) besides the computer you are using for the exam.
• 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.