UMD Logo

Course Description - CMSC 420, Fall 2000, Section 0301

The main focus of this course is description and properties of advanced data structures, as well as algorithms for manipulating these data structures. Applications include areas such as information retrieval and operating systems.
Required Text Books
  • H. Samet, The Design and Analysis of Spatial Data Structures, Addison-Wesley, Reading, MA, 1990. ISBN 0-201-50255-0.
  • H. Samet, Notes on Data Structures (F'00).

Tentative Topics Covered
  • Basic Data Structures
  • Trees
  • Graphs
  • Sorting
  • Searching
  • Balanced-Tree Searching
  • B-trees and Red-Black Trees
  • Point Methods
  • Hashing
  • Winged Edge Data Structure
  • Lists and Garbage Collection
  • Dynamic Storage Allocation
  • Alternative Rectangle Representation
  • Priority Search Trees and Range Trees
  • Representations of Line Segments

4-8 homework assignments consisting of problems.
A major programming project to be writeen in C or C++. It will be submitted incrementally as specified in the project specification (access restricted).
A midterm and a final will be given. Any schedule conflicts involving exam dates must be reported to the instructor within one week of the announcement of the exam date.
Grading (Tentative)
  • Homeworks:   10%
  • Projects:     35%
  • Midterm:     25%
  • Final:     30%
The weights are approximate and may change by upto 5%. The instructor reserves the right to fail, regardless of overall numeric score, students who do not submit a good faith attempt to complete all programming assignments.
Regrading Policy
All requests to change grading of homework, programming projects, or exams must be submitted in writing within one week of when initial grade was given. Requests must be specific and explain why you feel your answer deserves additional credit. A request to re-grade an assignment can result in the entire assignment being re-evaluated and as a result the score of any part of the assignment be increased or lowered as appropriate.
Academic Integrity
All work that you submit in this course must be your own. See the Undergraduate Catalog for definitions and sanctions. Academic dishonesty is a serious offense which may result in suspension or expulsion from the University. In addition to any other action taken, the grade "XF" denoting "failure due to academic dishonesty" will normally be recorded on the transcript of students found responsible for acts of academic dishonesty. Sharing of code on programming assignments or solutions of homework assignments are forms of academic dishonesty.
Class Newsgroup
The class newsgroup is csd.cmsc420.0301 on the newsserver. This will be used mainly for discussions.
Most class related announcements will be done through e-mail via an e-mail reflector setup by the University of Maryland Electronic Gradeing system. Please make sure that your e-mail address is up to date at the university.

[Last updated Sat Aug 19 2000]    [Please see copyright regarding copying.]