CMSC 420: DATA STRUCTURES
Catalog Description
Description,
properties, and storage allocation of data structures
including lists and trees. Algorithms for manipulating
structures. Applications from areas such as data
processing, information retrieval, symbol manipulation,
and operating systems.
Prerequisites
CMSC 330 or CMSC 400.
Topics
- Sequential Allocation (1 lecture)
- Linked Lists (1 lecture)
- Trees (2 lectures)
- Lists and Garbage Collection (1 lecture)
- Multilinked Structures and Dynamic Storage
Allocation (2 lectures)
- Heapsort and Quicksort (1 lecture)
- Sequential, Binary and Digital Searching (1 lecture)
- B-trees (1 lecture)
- Hashing (3 lectures)
- Introduction to LISP (6 lectures)
- Plane-Sweep and Rectangle Intersection Problems (2-3 lectures)
- Winged Edge Data Structures (1 lecture)
- MX-CIF Quadtrees (2 lectures)
- Hashing (3 lectures)
- Special Topics: Multimedia Data Structures (1 lecture)
Course Text
- H. Samet. The Design and Analysis
of Spatial Data Structures, Addison Wesley, 1989.
- H. Samet. Notes on Data Structures.
- D. E. Knuth. The Art of Computer Programming,
Vol. 1: Fundamental Algorithms,
Addison Wesley.
Typical Grading and Workload
- 30 % - MidTerm Exam
- 30 % - Final Exam
- 30 % - Programming Projects
- 10 % - Homework