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: divide-and-conquer, 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 in-class
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 in-class
Focuses on material till end of greedy |
29
|
Apr
1
Knapsack
(slides)
Reading: Section 6.4
|
2
|
3
Knapsack practice
(activity)
Reading: Section 6.4
|
4
|
5
|
8
Reading: Section 7.1
|
9
|
10
Max Flow problem (2)
Reading: Section 7.1
|
11
Rhulman - No classes
|
12
|
15
No classes
|
16
|
17
Review dynamic programming
|
18
Applications of Max Flow
(slides)
Reading: Section 7.2
|
19
|
22
Tractability of algorithms
(slides)
[Optional] Reading: Chapter 8
|
23
|
24
TBD
|
25
Guest lecture by Brian Brubach
|
26
|
29
Exam 3 in-class
Covers remaining material |
30
|
May
1
In-class presentations
|
2
Reading period starts
|