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

## Meet your instructors & tutors

### Instructors

Christine Bassem
Office hours:
Wednesday and Thursday 1pm-2:30pm

### Tutors

Wednesday TA: Sally Kim
Drop-in tutors:
Karen Xiao
Emily Suh
Kaitlyn Tsien
Yiduo Wang

## CS231 Syllabus

All course info and logistics can be found in the course syllabus

## CS231 Schedule

Please note that this page will be updated frequently, and it will contain all course content and resources
Monday Tuesday Wednesday Thursday Friday
Jan
22
Introduction and Review
(slides)
23
24
(I) Basics:
Complexity analysis
(stubs)
25
Priority queues and heaps
(slides)
Assignment 0 due at 11:59pm (pdf file - tex file)
26
29
Analysis and asymptotics
(slides)
30
31
Analysis and asymptotics
(activity)
Feb
1
Stable matching (1)
(slides)
2
5
Stable matching (2)
(slides - stubs)
6
7
Stable matching (3)
8
(II) Graphs: Definitions and representation
(slides)
Assignment 1 due at 11:59pm (pdf file - tex file)
9
12
BFS
(slides)
13
14
BFS
(activity)
15
DFS
(slides)
16
19
No classes
20
DAGs and Topological ordering
(slides)
21
(III) Greedy algorithms:
Interval Scheduling
22
Review graphs
(activity)
Assignment 2 due at 11:59pm (pdf file - tex file - starter code)
23
26
Scheduling (2) and exchange argument
(slides)
27
28
Exam 1 in-class
Focuses on material till end of DFS
29
Exchange argument 2
(proof)
Mar
1
4
Shortest path routing
(slides)
5
6
Review proofs
7
Minimum spanning trees
(slides)
8
11
(IV) Divide and Conquer:
Merge sort
(sort slides - recurrence slides)
12
13
Solving Recurrences
14
Counting Inversions
(slides)
No class - watch videos shared on Piazza
Assignment 3 due at 11:59pm (pdf file - tex file)
15
18
Spring break
19
Spring break
20
Spring break
21
Spring break
22
Spring break
25
(V) Dynamic programming:
Weighted interval scheduling
(slides - activity)
26
27
Jillian Amaral talk
Final paper description
28
Exam 2 in-class
Focuses on material till end of greedy
29
Apr
1
Weighted interval scheduling
(same slides as last week)
2
3
Weighted Interval Scheduling practice
(activity)
4
Knapsack
(slides)
5
8
Shortest path revisited
( slides )
9
10
Practice dynamic programming
11
Rhulman - No classes
Assignment 4 due at 11:59pm (pdf file - tex file)
12
15
No classes
16
17
(VI) Max Flow:
Max Flow problem
(slides)
18
Applications of Max Flow
(slides)
19
22
Guest lecture by Brian Brubach
(slides)
23
24
No class!
25
Tractability of algorithms
(slides)
Assignment 5 due at 11:59pm (pdf file - tex file - sample input)
26
29
Exam 3 in-class
Covers remaining material
30
May
1
In-class presentations
2