CMSC 420: Data Structures

A B-tree

Course objectives: Introduce methods for organizing data so that the data can be accessed and updated efficiently within a computer program. Particular emphasis will be placed on handling data that represent geometric items such as points and lines.

The class work will consist of 4-6 homeworks, a midterm, a final, and a multipart programming project (to be done in C or C++).


Lecture Slides

  1. 1/29 Introduction, review of big-O, data structuring principles [PDF]
    Reading: Shaffer chapter 1, review chapters 2 & 3 as needed.
  2. 1/31 Quick intro to C++ [PDF]
  3. 2/5 Stacks, queues, deques, lists, sets; sequential and linked allocation. [PDF]
    Reading: Shaffer chapter 4 and sections 9.1-9.2.
  4. 2/7 Graphs and matrices [PDF]
    Reading: Shaffer sections 11.1-11.3 and sections 12.2, 12.3
  5. 2/12 Trees [PDF]
    Reading: Shaffer sections 5.1-5.3, chapter 6
  6. 2/14 Binary Search Trees [PDF]
    Reading: Shaffer sections 5.4 Python Code
  7. 2/19 AVL Trees [PDF]
    Reading: Shaffer section 13.2.1
  8. 2/21 Splay trees [PDF]
    Reading: Shaffer 13.2.2
  9. 2/26 B-Trees [PDF]
    Reading: Shaffer 10.4, 10.5; Samet appendix A.
  10. 2/28 Heaps [PDF]
    Reading: Shaffer 5.5
  11. 3/4 Minimum Spanning Trees [PDF]
    Reading: Shaffer 11.5
  12. 3/6 Skip lists [PDF]
    Reading: Shaffer section 12.1 Python Code
  13. 3/11: Midterm review
  14. 3/13: Midterm
  15. 3/25: Review of delete in B-trees and splay trees; introduction to geometric concepts.
  16. 3/27: Midterm answers
  17. 4/1: Quadtrees (PR, MX, Point) [PDF]
    Reading: Shaffer 13.3.1, Samet 1.4 through 1.4.3 (skipping
  18. 4/3: More Quadtrees (slides included above)
    Reading: Shaffer 13.3, 13.3.3
  19. 4/8: kd-trees [PDF]
    Reading: Shaffer 13.3.1, Samet 1.5.1 through
  20. 4/10: kd-trees, continued (variants, range searching, incremental NN) [PDF]
    Reading: Samet 4.1 through 4.1.3
  21. 4/15: Range trees [PDF]
  22. 4/17: Range trees cont + fractional cascading (slides included above)
  23. 4/22: Interval trees, priority search trees [PDF]
  24. 4/24: Segment trees (slides included above)
  25. 4/29: Binary Space Partitions (board lecture, in-class handout)
  26. 5/1: Winged Edge (board lecture, in-class handout)
  27. 5/6: Grid Files, Hashing (board lecture)
    Reading: Samet (Grid Files)
  28. 5/8: Hashing, Suffix trees [PDF]
    Reading: Shaffer 9.4 (Hashing)]
  29. 5/13: Suffix trees, review for the final (slides above)


  1. Part 2 of the Programming Project, Due May 13.
  2. Homework 4, Due April 17.
  3. Homework 3, Due March 11.
  4. Homework 2, Due March 4.
  5. Part 1 of the Project, Due April 3. Makefile & Suggested Organization
  6. Homework 1, Due Feb 26.

Administrative Information

Professor: Carl Kingsford - 3113 Biomolecular Sciences Building (#296) - 301-405-7395 - carlk AT cs

Office hours: Tues 3:15-4:15 in AVW 3223 (Phone: 5-6713)
If you cannot attend office hours, email me about scheduling a different time.

Teaching assistants:

Class time: Tues/Thurs 2:00-3:15 in CSI 1121


Syllabus: An overview of course policies, topics, and grading is availible from this PDF.


Fine Print

Excused absences. Students claiming an excused absence must apply in writing and furnish documentary support (such as from a health care professional who treated the student) for any assertion that the absence qualifies as an excused absence. The support should explicitly indicate the dates or times the student was incapacitated due to illness. Self-documentation of illness is not itself sufficient support to excuse the absence. Absences for religious observances must be submitted in writing to the instructor within two weeks of the start of the semester. The instructor is not under obligation to offer a substitute assignment or to give a student a make-up assessment unless the failure to perform was due to an excused absence. An excused absence for an individual typically does not translate into an extension for team deliverables on a project.

Academic accommodations. Any student eligible for and requesting reasonable academic accommodations due to a disability is requested to provide, to the instructor in office hours, a letter of accommodation from the Office of Disability Support Services (DSS) within the first two weeks of the semester.

Last modified 30 Aug 2007. Valid HTML 4.01 Transitional