CS 320 Algorithms Theory and Practice (all sections)
Computer Science Department
Spring 2022

Schedule Outline

The detailed schedule is maintained on Canvas. Everything past the current week is subject to change.
Exams are given on Canvas. Campus students must take them in CSB 110. Online students will use the Respondus Lockdown browser.
Recordings of the lectures are available on Canvas.

Week	Reading, Slides, Materials	Worksheets, Programs, Quizzes, Exams
1 01/17	Welcome! Algorithm Design, Kleinberg/Tardos, Chapter 1 Course Introduction, Representative Problems) Review CS 220 and prepare for review exam next week. Here's an open discrete math textbook. It has much of, but not all, the information from that class.	How much do you remember? Take the Canvas quizzes on CS 220 prerequisites to help you prepare.
2 01/24	Introduction to Algorithms, Chapters 1.1-3.2 Orders of magnitude Survey of common running times Study Python Tutorial, especially dictionaries.
3 01/31	Introduction to Algorithms, Chapter 6 Line Of Sight Heaps and Heapsort	W3: Big Oh Fundamentals
4 02/07	Introduction to Algorithms, Chapter 22 Graphs	W4: Heaps Programming Assignment 1: Line of Sight
5 02/14	Introduction to Algorithms, Chapter 16.1-16.3 Greedy Algorithms	W5 Graphs Q4: Complexity, Orders of Magnitude
6 02/21	Introuction to Algorithms, Chapters 4.1, 4.3, 4.5 Divide & Conquer, Master Theorem Review	W6 Greedy Midterm Exam 1
7 02/28	Introduction to Algorithms, Chapters 23, 24 Minimum Spanning Trees, Shortest Paths	W7 Recurrences
8 03/07	Introduction to Algorithms, Chapter 33.4 Counting Inversions Closest Point Pair	W8 Minimum Spanning Trees, Shortest Paths Q8: Divide and Conquer: Setting Up and Solving Recurrences
Spring Recess, Mar 12-20
9 03/21	Introduction to Algorithms, Chapter 15 Dynamic Programming: Recursive substructure, memoization, Weighted Interval Scheduling, Knapsack KPDP-full.xlsx Memory Efficient Knapsack, No-backtrack knapsack KPDP-ME.xlsx	Programming Assignment 2: Huffman Encoding using Heaps W9 Weighted Interval Scheduling W9 Knapsack Q10: KnapSack
10 03/28	Introduction to Algorithms, Chapter 24.1 Bellman Ford Shortest Paths revisited: Bellman Ford Subset-Sum, Making Change	W10 Belman Ford
11 04/04	Introduction to Algorithms, Chapter 15.2 Matrix Chain Product (OSP) Review	Midterm Exam 2
12 04/11	Introduction to Algorithms, Chapter 27 Dynamic Multi-Threading
13 04/18	Parallel Scans (Prefix Sums), Reductions, and Fibonacci Prefix sum	W13 Dynamic Multi-Threading Programming Assignment 3: Counting Inversions
14 04/25	Introduction to Algorithms, Chapter 34.1-3 Reductions (the other kind)
15 05/02	P, NP, and NP Completeness Wrap up and recap	W15 Reductions W15 P & NP
Final Exam, May 12, 4:10-6:10 PM