|
|
CS 161 |
Rough plan:
|
Algorithmic
complexity and analysis (4 lectures) |
Chapters
2&3 |
|
Randomization,
divide and conquer (2 lectures) |
Chapters
4&5&7, no 5.4 |
|
Heaps
and counting sort (1 lecture) |
Chapters
6&8 |
|
Hashing
(2 lectures) |
Chapter
11 |
|
Tree
and graph definitions and properties (1 lecture) |
Chapters
10, 22.1 |
|
Binary
Search Trees (1 lecture) |
Chapter
12 (no 12.4), 14 |
|
Greedy
Algorithms (2 lectures) |
Chapters
16.1, 16.2, 16.3, 23 |
|
Dynamic
programming (3 lectures) |
Chapters
15 |
|
Graph
algorithms (4 lectures) |
Chapters
22,24,25 |
|
Tentative Syllabus – periodically updated
throughout the quarter |
HW schedule is tentative. There might be more than 5 HWs.
The schedule will be periodically updated.
|
Lecture # |
Date |
Description |
Reading |
Assignments |
|
1 |
9/23 |
Introduction,
algorithmic complexity and asymptotic analysis |
CLRS
2 |
|
|
2 |
9/25 |
Asymptotic
notation, Stable Matching |
CLRS
3. KT 1.1 for Stable Matching |
HW1
out |
|
3 |
9/30 |
Divide-and-conquer
and recursive algorithms, solving simple recurrences. Iterating recurrences. |
CLRS
4.1-4.3 |
|
|
4 |
10/2 |
Master
Method. Randomization. |
CLRS
4.4-4.5; 5.1-5.3 |
HW1
due |
|
5 |
10/7 |
More
randomization examples. Closest pair of points
algorithm. |
CLRS
7; KT 5.4 for closest pair of points. |
HW2
out |
|
6 |
10/9 |
Median
and Order Statistics. |
CLRS
9. |
|
|
7 |
10/14 |
Heaps |
CLRS
6 |
HW2
due |
|
|
10/16 |
QUIZ-1,
location: Hewlett 200 |
|
HW3
out |
|
8 |
10/21 |
Sorting
lower bounds. Counting Sort. Start hashing. |
CLRS
8 |
|
|
9 |
10/23 |
Analysis
of hashing with chaining. Analysis of open addressing. |
CLRS
11.1-11.4 |
HW3
due |
|
10 |
10/28 |
Bloom
filter. Binary Search Trees |
CLRS
12.1-12.4 |
|
|
11 |
10/30 |
Red/Black
Trees. Extending Red Black Trees. |
CLRS
13, 14 |
HW4
out |
|
12 |
11/4 |
Skip
lists. Start greedy algorithms. Activity scheduling. Homework scheduling.
Huffman encoding |
CLRS
16.1-16.3 |
|
|
13 |
11/6 |
Start
graph algorithms. DFS/BFS. Discovering cycles. Partial orders. Topological
sort. |
CLRS
22 |
HW4
due |
|
11/11 |
QUIZ-2,
location: Hewlett 200 |
|||
|
14 |
11/13 |
Minimum-cost
spanning tree. Prim's algorithm. |
CLRS
23 |
HW5
out |
|
15 |
11/18 |
Kruskal's algorithm. Union-find data structure. |
CLRS
23 |
|
|
16 |
11/20 |
Start
Dynamic Programming. Longest Common Subsequence. |
CLRS
15 |
HW5
due |
|
-- |
11/25 |
THANKSGIVING |
||
|
-- |
11/27 |
THANKSGIVING
|
||
|
17 |
12/2 |
Matrix
chain multiplication. Subset sum. Knapsack. |
||
|
18 |
12/4 |
Single
source shourtest paths. Bellman-Ford. All-pairs shortest
paths. Floyd-Warshall. |
CLRS
24, 25 |
|
|
12/10 |
Final
at 12/10, 7pm. No alternative finals will be given.
Location: Bishop Auditorium, Graduate School of Business. Source: Registrar's office |