Spring 2024 CS231
This is a course about algorithms; their design and analysis
The language of computer science is to a great extent the language of algorithms. Although there are many thousands of algorithms, there are relative few basic design techniques. These include: divideandconquer, greedy, dynamic programming, and network flow. We will illustrate these techniques by studying a few fundamental algorithms of each type. In addition to helping us understand classic solution techniques, these algorithms have proven very useful in practice. Their names and the names of the problems they solve have become a standard part of the language of computer science.
Unfortunately, there is rarely a best algorithm to solve a given problem. Each approach involves a series of tradeoffs. Therefore, we will also study methods for evaluating the usefulness of an algorithm in a given situation. Among the various competing measures, we will focus primarily on the anal ysis of time and space complexity. However, a number of other issues will also be discussed.
Monday  Tuesday  Wednesday  Thursday  Friday 

Jan
22
Introduction and Review
(slides)
Reading: Course syllabus

23

24

25
Priority queues and heaps
(slides)
Optional Reading: Section 2.5

26

29
Analysis and asymptotics
(slides)
Reading: Sections 2.1 and 2.2

30

31
Analysis and asymptotics
(activity)
Reading: Sections 2.1 and 2.2

Feb
1
Stable matching (1)
(slides)
Reading: Section 1.1

2

5

6

7
Stable matching (3)
Reading: Section 2.3

8
(II) Graphs:
Definitions and representation
(slides)
Reading: Sections 3.1 and 3.2

9

12
BFS
(slides)
Reading: Sections 3.3 and 3.4

13

14
BFS
(activity)
Reading: Sections 3.3 and 3.4

15
DFS
(slides)
Reading: Sections 3.3 and 3.5

16

19
No classes

20
DAGs and Topological ordering
(slides)
Section 3.6

21
Reading: Section 4.1

22
Review graphs
(activity) 
23

26
Scheduling (2) and exchange argument
(slides)
Reading: Section 4.2

27

28
Exam 1 inclass
Focuses on material till end of DFS 
29
Exchange argument 2
(proof)
Reading: Section 4.2

Mar
1

4
Shortest path routing
(slides)
Reading: Section 4.4

5

6
Review proofs

7
Minimum spanning trees
(slides)
Reading: Section 4.5

8

11
Reading: Sections 5.1 and 5.2

12

13
Solving Recurrences
Reading: Sections 5.1 and 5.2

14
Reading: Section 5.3

15

18
Spring break

19
Spring break

20
Spring break

21
Spring break

22
Spring break

25

26

27
Jillian Amaral talk
Final paper description 
28
Exam 2 inclass
Focuses on material till end of greedy 
29

Apr
1
Weighted interval scheduling
(same slides as last week)
Reading: Sections 6.1 and 6.2

2

3
Weighted Interval Scheduling practice
(activity)
Reading: Sections 6.1 and 6.2

4
Knapsack
(slides)
Reading: Section 6.4

5

8
Shortest path revisited
( slides )
Reading: Section 6.8

9

10
Practice dynamic programming
Reading: Section 7.1

11
Rhulman  No classes

12

15
No classes

16

17
Reading: Section 7.1

18
Applications of Max Flow
(slides)
Reading: Section 7.2

19

22
Guest lecture by Brian Brubach
(slides) 
23

24
No class!

25
Tractability of algorithms
(slides)
[Optional] Reading: Chapter 8

26

29
Exam 3 inclass
Covers remaining material 
30

May
1
Inclass presentations

2
Reading period starts
