#Week

Slides

Further Readings

1-2

Lecture 1: Balanced Search Trees (I)

Weiss Sec. 4.4-4.5, 11.5
CLRS Chap. 11
Splay Tree Paper

3

Lecture 2: Balanced Search Trees (II)

S&W Sec. 3.3
CLRS Chap. 13, 18

4

Lecture 3: Priority Queues

Weiss Sec. 6.5-6.7, 11.3

5

Lecture 4: Search and Backtracking

Weiss Sec. 10.5
AIMA Chap. 3, Sec. 5.1-5.4
UC Berkeley CS188 Lec. 2, 3, 6

6

Lecture 5: Divide and Conquer

DPV Ch.2
K&T Ch.5
CLRS Ch.4

7

Lecture 6: Dynamic Programming

Weiss Sec 10.3
CLRS Chap. 14
K&T Chap. 6
DPV Chap. 6
David Silver's RL course Lec 1-5

8

Lecture 7: Greedy Algorithms

DPV Chap. 5
CLRS Chap. 15
Yitong Yin's course notes
Information theory book

9

Lecture 8: Inverted File Index

Information Retrieval Book Ch.1, 4, 5, 6, 8
Survey Paper
Stanford cs276

10

Lecture 9: Intractability

DPV Chap. 8
K&T Chap. 8
CLRS Chap. 34
Intractability slides from Kevin Wayne
Shi Li's course notes
Computational complexity book Chap. 1

11

Lecture 10: Approximation Algorithms

Weiss Sec. 10.1.3
K&T Chap. 11
CLRS Chap. 35
Slides from Kevin Wayne
Yitong Yin's slides on greedy algorithms and slides on rounding DP and notes
Approximation algorithms book Chap. 8, 9

12

Lecture 11: Local Search

K&T Chap. 12
Slides from Kevin Wayne
Yitong Yin's slides and notes
Information theory book Chap. 12 on Hopfield nets

13

Lecture 12: Randomized Algorithms

K&T Chap. 13
CLRS Chap. 5
Slides from Kevin Wayne
Yitong Yin's slides and notes

14

Parallel Algorithms (Official Course Slides)

Notes from Uzi Vishkin

15

External Sorting (Official Course Slides)

TAOCP Volume 3 (2nd Edition), Sec. 5.4.1-5.4.2