UMD Logo

Course Description - CMSC 420, Fall 1999, 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.

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 handout.

Two examinations, a midterm and a final, will be given. The dates of the examinations will be posted on the class web page. Any schedule conflicts involving exam dates must be reported to Dr. Golubchik within one week of the announcement of the exam date.

Grading (Tentative)
  • Homeworks   10%
  • Projects     30%
  • Midterm     25%
  • Final     35%
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.
  • 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'99).

Late Policy
Unless specified otherwise on a particular assignment, the late policy is as follows: 50% off for being 1-24 hours late; 75% off for being 25-48 hours late; 100% off for being more than 48 hours late. If you are unable to complete a homework or a programming assignment due to illness or family emergency, please see Dr. Golubchik as soon as possible to make special arrangements.

Regrading Policy
All requests to change grading of homework, programming projects, or exams must be submitted in writing (typed) within one week of when the assignment was made available for pickup. 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 assignement 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 assignements 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 for announcements and discussions.

[Last updated Wed Sep 1 1999]    [Please see copyright regarding copying.]