Computer Science 282/482 - Design and Analysis of Efficient Algorithms - Fall 2026

Monday 6:15pm - 7:15pm in Hylan Building Room 202 (Zhiyuan Xiao)
Tuesday 6:15pm - 7:15pm Goergen Hall Room 109 (Danica Kim)
Wednesday 6:15pm - 7:15pm in Gavett Hall Room 310 (Skylar Abruzese)

Textbooks:

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: [Erickson] = Algorithms, J. Erickson, 2019 (a paper copy available from Amazon).
recommended: [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 Illuminated: Omnibus Edition, T. Roughgarden, 2022.
Algorithm Design, J. Kleinberg and E. Tardos, 2005.
Introduction to Algorithms: A Creative Approach, U. Manber, 1989.
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.
Algorithms, R. Sedgewick, K. Wayne, 2011.
The Algorithm Design Manual, S. Skiena, 2008.

Other resources/recommended reading (more advanced topics):

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.

Prerequisites: CSC162 or CSC172 or MTH172.

Schedule

TOPIC: Greedy algorithms. Dynamic programming. (Major homework #1 due Sep. 17, Exam #1 on Sep. 24.)

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

Sep. 7 (Monday) 6:15pm - 7:15pm in Hylan Building Room 202 (Zhiyuan Xiao)
Sep. 8 (Tuesday) 6:15pm - 7:15pm in Goergen Hall Room 109 (Danica Kim)
Sep. 9 (Wednesday) 6:15pm - 7:15pm in Gavett Hall Room 310 (Skylar Abruzese)

Sep. 14 (Monday) 6:15pm - 7:15pm in Hylan Building Room 202 (Zhiyuan Xiao)
Sep. 15 (Tuesday) 6:15pm - 7:15pm in Goergen Hall Room 109 (Danica Kim)
Sep. 16 (Wednesday) 6:15pm - 7:15pm in Gavett Hall Room 310 (Skylar Abruzese)

Sep. 21 (Monday) 6:15pm - 7:15pm in Hylan Building Room 202 (Zhiyuan Xiao)
Sep. 22 (Tuesday) 6:15pm - 7:15pm in Goergen Hall Room 109 (Danica Kim)
Sep. 23 (Wednesday) 6:15pm - 7:15pm in Gavett Hall Room 310 (Skylar Abruzese)

Sep. 1 Tue - Introduction.
Sep. 3 Thu - When does greedy algorithm for the coin change problem work? [minor homework #1 due 9/3 (released: 9/1)]

Sep. 8 Tue - Dynamic programming for the coin change problem. Knapsack (integer weights). [minor homework #2 due 9/8 (released: 9/3)]
Sep. 10 Thu - Knapsack revisited (integer values). Longest increasing subsequence. [minor homework #3 due 9/10 (released: 9/8)]

Sep. 15 Tue - Edit distance. Chain matrix multiplication.
Sep. 17 Thu - More dynamic programming problems.

Sep. 22 Tue - Review. [minor homework #4 due 9/22 (released: 9/15)]
Sep. 24 Thu - EXAM #1 (topics: Greedy algorithms/Dynamic programming).

TOPIC: Graph algorithms. (Major homework #2 due Oct. 8, Major homework #3 due Oct. 22, Exam #2 on Oct. 29.)

[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.

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

Problem sessions:

Sep. 28 (Monday) 6:15pm - 7:15pm in Hylan Building Room 202 (Zhiyuan Xiao)
Sep. 29 (Tuesday) 6:15pm - 7:15pm in Goergen Hall Room 109 (Danica Kim)
Sep. 30 (Wednesday) 6:15pm - 7:15pm in Gavett Hall Room 310 (Skylar Abruzese)

Oct. 5 (Monday) 6:15pm - 7:15pm in Hylan Building Room 202 (Zhiyuan Xiao)
Oct. 6 (Tuesday) 6:15pm - 7:15pm in Goergen Hall Room 109 (Danica Kim)
Oct. 7 (Wednesday) 6:15pm - 7:15pm in Gavett Hall Room 310 (Skylar Abruzese)

No problem sessions during FALL BREAK week

Oct. 12 (Monday) 6:15pm - 7:15pm in Hylan Building Room 202 (Zhiyuan Xiao)
Oct. 13 (Tuesday) 6:15pm - 7:15pm in Goergen Hall Room 109 (Danica Kim)
Oct. 14 (Wednesday) 6:15pm - 7:15pm in Gavett Hall Room 310 (Skylar Abruzese)

Oct. 19 (Monday) 6:15pm - 7:15pm in Hylan Building Room 202 (Zhiyuan Xiao)
Oct. 20 (Tuesday) 6:15pm - 7:15pm in Goergen Hall Room 109 (Danica Kim)
Oct. 21 (Wednesday) 6:15pm - 7:15pm in Gavett Hall Room 310 (Skylar Abruzese)

Oct. 26 (Monday) 6:15pm - 7:15pm in Hylan Building Room 202 (Zhiyuan Xiao)
Oct. 27 (Tuesday) 6:15pm - 7:15pm in Goergen Hall Room 109 (Danica Kim)
Oct. 28 (Wednesday) 6:15pm - 7:15pm in Gavett Hall Room 310 (Skylar Abruzese)

Sep. 29 Tue - Undirected graphs, finding connected components, DFS.
Oct. 1 Thu - Directed graphs, strong connectedness, linearization (topological sorting). [minor homework #5 due 10/1 (released: 9/29)]

Oct. 6 Tue - Strongly connected components.
Oct. 8 Thu - BFS, Shortest paths (Dijkstra). [minor homework #6 due 10/8 (released: 10/1)]

Oct. 13 Tue - FALL BREAK.
Oct. 15 Thu - Dealing with negative edge weights (Bellman Ford). Floyd-Warshal.

Oct. 20 Tue - Matchings I.
Oct. 22 Thu - Matchings II. [minor homework #7 due (released: 10/15)]

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

TOPIC: Linear Programming, integer linear programming. (Major Homework #4 due Nov. 12, Exam #3 on Nov. 19.)

Nov. 2 (Monday) 6:15pm - 7:15pm in Hylan Building Room 202 (Zhiyuan Xiao)
Nov. 3 (Tuesday) 6:15pm - 7:15pm in Goergen Hall Room 109 (Danica Kim)
Nov. 4 (Wednesday) 6:15pm - 7:15pm in Gavett Hall Room 310 (Skylar Abruzese)

Nov. 9 (Monday) 6:15pm - 7:15pm in Hylan Building Room 202 (Zhiyuan Xiao)
Nov. 10 (Tuesday) 6:15pm - 7:15pm in Goergen Hall Room 109 (Danica Kim)
Nov. 11 (Wednesday) 6:15pm - 7:15pm in Gavett Hall Room 310 (Skylar Abruzese)

Nov. 16 (Monday) 6:15pm - 7:15pm in Hylan Building Room 202 (Zhiyuan Xiao)
Nov. 17 (Tuesday) 6:15pm - 7:15pm in Goergen Hall Room 109 (Danica Kim)
Nov. 18 (Wednesday) 6:15pm - 7:15pm in Gavett Hall Room 310 (Skylar Abruzese)

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

Nov. 10 Tue - Duality, Modeling with linear programs II (zero-sum games).
Nov. 12 Thu - Integer linear programming. [minor homework #8 due 11/12 (released: 11/5)]

Nov. 17 Tue - Modeling with linear programs III.
Nov. 19 Thu - EXAM #3 (topics: linear programming, integer linear programming) .

TOPIC: Reductions (NP-completeness), Divide and Conquer Algorithms (FFT). (Major Homework #5 due Dec. 10.)

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

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

Problem sessions:

No problem sessions during Thanksgiving week

Nov. 31 (Monday) 6:15pm - 7:15pm in Hylan Building Room 202 (Zhiyuan Xiao)
Dec. 1 (Tuesday) 6:15pm - 7:15pm in Goergen Hall Room 109 (Danica Kim)
Dec. 2 (Wednesday) 6:15pm - 7:15pm in Gavett Hall Room 310 (Skylar Abruzese)

Dec. 7 (Monday) 6:15pm - 7:15pm in Hylan Building Room 202 (Zhiyuan Xiao)
Dec. 8 (Tuesday) 6:15pm - 7:15pm in Goergen Hall Room 109 (Danica Kim)
Dec. 9 (Wednesday) 6:15pm - 7:15pm in Gavett Hall Room 310 (Skylar Abruzese)

Nov. 24 Tue - Fast fourier transform, convolution I.
Nov. 26 Thu - THANKSGIVING (no class).

Dec. 1 Tue - Fast fourier transform, convolution II
Dec. 3 Thu - NP completness I. [minor homework #9 due 12/3 (released: 12/1)]

Dec. 8 Tue - NP completness II. [minor homework #10 due 12/8 (released: 11/24)]
Dec. 10 Thu - More divide and conquer algorithms.

Dec. 22 Tue - FINAL EXAM 4:00pm - 7:00pm.

Grading

The grade for the course is computed from the in-class exam grade (3 times 18%), the final exam grade (26%), and homework grade (20%).

Homework Rules

Homework will be submitted on Gradescope, the deadline is 11am on the date the homework is due.
There will be the following three types of homework.
- Major homework (10%) 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 (5%) will be answering questions on gradescope. Minor homework will be autograded.
- In-class/workshop worksheets (5%). The worksheets are submitted on gradescope (formative; graded for participation/submission).
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.

AI policy

AI use is allowed with the following two rules: The AI prompts and responses have to meaningfully go through your brain. The AI use has to be transparent. This means:
- Copying assignment into AI prompt in not allowed (you are allowed to ask AI about the assignment---the prompt has to be generated by your brain).
- Copying code or sentences from an AI response is not allowed (you are allowed to look at the AI responses and internalize them---the code and sentences that are in your solutions have be generated by your brain).
- When you use AI on an assignment, indicate which AI system you used and append the chat to the assignment (this includes prompts and AI responses).

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 full-class exams and a 3-hour final exam. There are no make-up exams (in the case of a medical emergency your grade will be extrapolated using the exams that you took).

This course follows The University Policy on Academic Honesty.