CS 31: Algorithms [archived]
Spring 2023 | 2A hour (TTh 14:25—16:15; W 17:30—18:20) | Irving 080
Professor Amit Chakrabarti

This page is retained for archival purposes. The links to materials in the schedule table will not work.

Homework sets will be available on this course's Canvas page (you will need to click through to Gradescope). Please read the policies section of the course website for submission instructions, the lateness policy (which is absolutely strict), grading standards, and the academic honor principle.

## Lectures, Exams, and Submissions Due

In the table below, references are to the three designated reference books. Notation like "[KT 2.1]" refers to section 2.1 of the Kleinberg-Tardos book. Similarly, [CLRS Ch 2] refers to chapter 2 of the Cormen-Leiserson-Rivest-Stein book and [Eri] refers to the Erickson book.

# Date Class Topics / Other Events References
1

Tue Mar 28 Analyzing time complexity ● What is a unit cost operation? ● Arrays, lists, dictionaries, binary trees ● Binary search [KT 2.1]; [CLRS 2.1, 2.2]; [Eri Ch 0]
(slides)
2

Wed Mar 29 (x-hour) Administrivia ● How to succeed in this course course website and canvas
(board)
3

Thu Mar 30 Asymptotic notation: O, Ω, Θ ● Proving algorithm correctness using invariants ● Recursion [CLRS Ch 2]; [Eri 1.1—1.6]
(board)
S

Mon Apr 03 Homework 1 due by 22:00
4

Tue Apr 04 Efficient sorting ● InsertionSort and MergeSort ● QuickSort and HeapSort (teaser) [CLRS Ch 2, 6.4, 7.2]; [KT 2.4, 2.5]; [Eri 1.4, 1.5]
(notes)  (board)
5

Wed Apr 05 (x-hour) Graphs and digraphs ● Adjacency list ● Adjacency matrix [CLRS 20.1]; [KT 3.1, 3.3]; [Eri 5.1—5.4]
(board)
6

Thu Apr 06 Breadth-first search ● Shortest paths (unweighted) [CLRS 20.2]; [KT 3.1—3.3]; [Eri Ch 5]
(notes)  (board)
S

Mon Apr 10 Homework 2 due by 22:00
7

Tue Apr 11 Depth-first search ● Parenthesis theorem and Path lemma ● DAGs and Cycle finding [Eri 6.1, 6.2]; [KT 3.3—3.6]; [CLRS 20.3, 20.4]
(board)
X

Wed Apr 12 (x-hour) used as extra office hours
8

Thu Apr 13 Topological sort ● Strongly connected components [Eri 6.3, 6.5, 6.6]; [CLRS 20.4, 20.5]
(board)
S

Mon Apr 17 Homework 3 due by 22:00
9

Tue Apr 18 Divide-and-conquer ● MergeSort redux ● Counting inversions ● Karatsuba integer multiplication [KT 5.1—5.3, 5.5]; [Eri 1.7, 1.9]; [CLRS Ch 4]
(board)
X

Wed Apr 19 x-hour not used
10

Thu Apr 20 Strassen matrix multiplication ● Closest pair of points ● Selection in linear time [Eri 1.8]; [CLRS 9.1, 9.3]
(board)
S

Mon Apr 24 Homework 4 due by 22:00
11

Tue Apr 25 Analysis of linear-time selection ● Dynamic programming: Fibonacci numbers, Rod cutting [Eri 3.1—3.5]; [CLRS 14.1]
(board)
Q

Wed Apr 26 **Midterm 1** from 17:30 to 20:30
12

Thu Apr 27 Systematically presenting a DP algorithm ● Weighted interval scheduling ● Longest common subsequence ● Matrix chain multiplication [KT 6.1, 6.2]; [CLRS 14.2—14.4]
(notes)  (board)
S

Mon May 01 Homework 5 due by 22:00
13

Tue May 02 DP and graph algorithms ● Bellman-Ford SSSP ● Floyd-Warshall APSP [Eri 8.7, 9.8]
(board)
X

Wed May 03 x-hour not used
14

Thu May 04 Floyd-Warshall revisited ● Subset-Sum and pseudopolynomial time ● DP wrap-up [KT 6.4]; [Eri 3.8]
(notes)  (board)
S

Mon May 08 Homework 6 due by 22:00
15

Tue May 09 Generic relaxation-based SSSP algorithms ● Correctness of Bellman-Ford algorithm ● Dijkstra's algorithm and its correctness [KT 4.4]; [CLRS Ch 22]; [Eri 8.6]
(board)
16

Wed May 10 (x-hr) Minimum spanning trees and Prim's algorithm [KT 4.5]; [CLRS Ch 21; [Eri 7.1—7.4]
(board)
17

Thu May 11 Priority queues ● Time complexity of Dijkstra and Prim ● Cut property and correctness of Prim [KT 4.5]; [CLRS Ch 21; [Eri 7.1—7.4]
(board)
S

Mon May 15 Homework 7 due by 22:00
18

Tue May 16 Randomized algorithms; QuickSelect and QuickSort [KT 13.12, 13.5]
(notes)  (board)
Q

Wed May 17 **Midterm 2** from 17:30 to 20:30
19

Thu May 18 Hash functions; hash tables; closest-pair redux [KT 13.6, 13.7]
(board)
S

Mon May 22 Homework 8 due by 22:00
20

Tue May 23 Flows and cuts I [Eri Ch 10]
(board)
X

Wed May 24 x-hour not used
21

Thu May 25 Flows and cuts II [Eri Ch 11]
(board)
S

Mon May 29 Homework 9 due by 22:00
22

Tue May 30 Tying up loose ends; Wrap-up (no refs)
(board)

The **final exam** has been scheduled by the Registrar's Office:
8:00 to 11:00 on Sat Jun 03, in Spanos Auditorium (Cummings 100).

Please do not schedule anything during the X-hour: we may need to use one at short notice.