Tentative schedule of topics and readings:
Week 1: Introduction; binary and leftist heaps [T 3] Week 2: Binomial and Fibonacci heaps [CLR 20-21] Homework due 21 Jan: CLR 18.3-3, 18.4-4, 20.2-8, 21.4-1 Week 3: Binary search trees [CLR 13,14,19; T 4] Homework due 2 Feb: CLR 13.2-5, 13.4-2, 14.2-5, 14-2 Week 4: Splay trees; persistence [T 4] Week 5: MIDTERM; suffix trees Week 6: hashing [CLR 12] Homework due 18 Feb: CLR 12.3-2, 12-1, 12-3 Week 7: lowest common ancestors; augmenting data structures [T 5; CLR 15] Week 8: cutting and linking trees [T 5] Study problems on LCAs and cutting and linking trees -- Solutions Week 9: geometric searching[CLR 15] Study problems on segment and interval trees Week 10: union find[T 2; CLR 22]
David Eppstein,
Theory Group, Dept. Information & Computer
Science, UC Irvine.
Last update: