|
|
|
|
|
SCHEDULE SUBJECT TO CHANGE
GT is Goodrich and Tamassia (the course textbook)
| Week |
Date |
Content |
Readings |
Assignments |
| #1 |
September 28 |
Administrivia |
GT ch. 1-3
syllabus |
|
| September 30 |
Java review |
GT ch. 1-3
RecursionDemo.java
List interface / implementation (no iterators)
SimpleIntList notes
SimpleAbstractIntList notes
SimpleArrayIntList notes
|
|
| #2 |
October 3 |
Big-O part 1 |
GT ch. 4
matlab plots from today
|
HW0 up |
| October 5 |
Big-O part 2, recursion |
GT ch. 4
notes from today
size of human genome
size of Internet
insertion sort demo
(pick quadratic sorts,
press start viz)
|
|
| October 7 |
merge-sort |
GT ch. 11.1
insertion/merge sort
merge sort slides
merge/insertion sort results
|
|
| #3 |
October 10 |
List interface, implementation |
GT ch. 6
see handout from 9/30
some notes |
HW0 due
HW1 up |
| October 12 |
iterators |
GT ch. 6
IntList, Iterators, ArrayIntList
LinkedIntList
|
|
| October 14 |
stacks and queues |
GT ch. 5
Stacks/Queues
some notes
|
|
| #4 |
October 17 |
priority queues, heaps |
GT ch. 8.1-8.2, 14.2 |
|
| October 19 |
heaps, adaptable priority queues |
GT ch. 8
practice midterm |
|
| October 21 |
adaptable priority queues, review |
GT ch. 8
adaptable pqs |
|
| #5 |
October 24 |
Midterm |
|
|
| October 26 |
Map, Hashmap |
GT ch. 9
Midterm solns |
|
| October 28 |
hash codes, load factors |
GT ch. 9.1-9.2
excerpt from Bloch on hashcodes (paper only)
notes |
HW1 due
HW2 up |
| #6 |
October 31 |
binary search trees |
GT ch 7, 10.1
bst code |
|
| November 2 |
AVL trees |
GT ch. 10.2
BST/AVL
demo
AVL slides
AVL animation
|
|
| November 4 |
AVL trees |
GT ch. 10.2
AVL/Splay demo
(uses LRRR... removal)
|
|
| #7 |
November 7 |
Splay trees |
GT ch. 10.3
log-ineq lemma
splay proof
|
HW2 due
HW3 up |
| November 9 |
Quick sort |
GT ch. 11.2
Sorting Demos
advanced QuickSort stuff
practice midterm |
|
| November 11 |
Holiday (no class) |
|
|
| #8 |
November 14 |
other sorting topics |
GT ch. 11.3-11.5
sorting movie
|
|
| November 16 |
Midterm |
|
|
| November 18 |
graphs |
GT ch. 13.1-13.3
slides |
|
| #9 |
November 21 |
graph traversals |
GT ch. 13.1-13.3
DFS/BFS
|
HW3 due
HW4 up |
| November 23 |
bonus turkey lecture |
GT ch. 14.3
B-Trees
CLR 19 (paper only)
|
|
| November 25 |
Holiday (no class) |
|
|
| #10 |
November 28 |
graph traversals |
GT ch. 13.4-13.5
topological sort
Warshall Algorithm
|
|
| November 30 |
Dijkstra's algorithm |
GT ch. 13.6
Dijkstra quotes
Dijkstra,Floyd-Warshall
|
|
| December 2 |
minimal spanning trees |
GT ch. 13.7
MSTs
|
|
| #11 |
December 5 |
sets |
GT ch. 11.6
disjoint sets
|
|
| December 7 |
network flow |
CLR 27.2 (paper only)
network flow
Flow Demo
practice final
|
|
| December 9 |
review, course evals |
|
HW4 due
|
| Final |
Thursday December 15, 8:30-10:20 |
Final |
|
|
|
UW Home 
