**Dec. 26. **Here is a list of the
final grades, and here are some answers to selected questions on
the final exam.

- Course description
- Newsgroup
- Homework assignments
- Information about your computer accounts
- Project 1, and Ransom's instructions on how to submit it.
- Project 2.
- Here's how to submit it (this is different from in probject 1).
- Ransom's example skip-list.

- Sample exams, with answers (PDF format):
- The midterm exam for this class

This schedule is very tentative - it will change as we go along.

- Tues 9/3: (lecture by Ransom Winder; I'll be out of town)
- Introduction, big-
*O*notation: Chapters 1 & 2

- Introduction, big-
- Thurs 9/5:
- no class; I'll be out of town

- Tues 9/10:
- review of
*O, Ω, Θ* - abstract data types: section 1.2
- lists: Chapter 3

- review of
- Thurs 9/12:
- trees and tree traversal (quick review): Chapter 4

- Tues 9/17:
- threaded trees (end of chapter 4)
- contiguous arrays: sections 5.1-5.2

- Thurs 9/19:
- constant-time array initialization: section 5.2
- sparse arrays: section 5.3
- due date for HW 1

- Tues 9/24:
- triangular matrices
- Huffman encoding: section 5.4
- start discussing Lempel-Ziv encoding: section 5.4
- late date for HW 1
- assign HW 2

- Thurs 9/26:
- finish discussing Lempel-Ziv encoding: section 5.4
- binary search: section 6.3
- range search: section 9.3
- Discuss Project 1

- Tues 10/1:
- Knuth-Morris-Pratt and Boyer-Moore algorithms: section 5.5
- due date for HW 2
- assign HW 3

- Thurs 10/3:
- finish discussing the Boyer-Moore algorithm
- sets as abstract data types, unordered lists, binary search, interpolation search: sections 6.1-6.3
- late date for HW 2

- Tues 10/8:
- skip lists: sections 6.3
- due date for HW 3

- Thurs 10/10:
- binary search trees: section 6.4
- (we'll skip section 6.5)
- AVL trees: section 7.1
- late date for HW 3

- Tues 10/15:
- review for the midterm exam
- due date for Project 1

- Wed 10/16:
- late date for Project 1

- Thurs 10/17:
- midterm exam

- Tues 10/22:
- review AVL trees: section 7.1
- 2-3 trees: section 7.2
- basic idea of red-black trees

- Thurs 10/24:
- (a,b)-trees

- Tues 10/29:
- B-trees and splay trees (end of Chapter 7)
- assign Project 2

- Thurs 10/31:
- bit vectors, start discussing tries (chapter 8)

- Tues 11/5:
- tries, patricia trees, de la Briandais trees, digital search trees (chapter 8)
- start discussing hashing (chapter 8)

- Thurs 11/7:
- hashing (chapter 8)

- Tues 11/12:
- heaps, up trees, path compression (chapter 9)

- Thurs 11/14:
- no class; I'll be out of town

- Tues 11/19:
- point quadtrees, region quadtrees, k-d trees (chapter 9)

- Thurs 11/21:
- reference counts, mark/sweep garbage collection (chapter 10)

- Tues 11/26:
- collection by copying, memory compacting (chapter 10)

- Thurs 11/28:
- no class (Thanksgiving)

- Tues 12/3:
- allocation strategies, data structures for freeing (chapter 10)
- lower bound for comparison sorting: section 11.5

- Thurs 12/5:
- no class - university closed due to snow

- Tues 12/10:
- bucket sorting, radix sorting: section 11.6
- graph searching, topological sorting: section 12.2

- Tues 12/12:
- review for final exam
- teacher/course evaluation (bring pencils!)

- Wednesday, 12/19, 10:30am--12:30pm (?)
- final exam (check the university exam schedule to make sure about this date and time)