CMSC 420, Data Structures - Section 0101, Fall 2002

---

Announcements

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

Links

• 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):
  • fall 1996 midterm
  • fall 1996 final
  • fall 2001 final
• The midterm exam for this class

Lecture Schedule

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
• 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
• 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)