Course Description - CMSC 420, Fall 2001, Section 0301

Focus

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.

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

Additional Lecture Slides (access to slides is restricted)

The PostScript files below were used by Prof. Hanan Samet in his CMSC420 class. They are copyrighted and may not be redistributed. They are provided here for your information. Our class does not follow these slides exactly. (These links are no longer valid.)

List structures / (animated).
Trees / (animated).
Graphs / (animated).
Winged Edge data structure / (animated).
Triangulations / (animated).
Searching Techniques / (animated).
Sorting Techniques / (animated).
Dynamic Storage Allocation / (animated).
Garbage Collection / (animated).
Representation of Point Data / (animated).
Rectangle data / (animated).
Range trees / (animated).
Hashing methods / (animated).
Nearest neighbor / (animated).
Bulk loading / (animated).
Quadtrees / (animated).
Surface data / (animated).
3D data / (animated).

Homework

4-8 homework assignments consisting of problems.

Projects

A major programming project to be writeen in C, C++, or Java. It will be submitted incrementally as specified in the project specification (access restricted).

Exams

A midterm and a final will be given. The dates of the examinations will be posted on the class calendar. Any schedule conflicts involving exam dates must be resolved with the instructor at least one week before 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.

Late Policy

All homeworks and project assignments must be turned in on time. Late submissions will receive a score of zero. Written homeworks are to be turned in at the beginning of specified classes. You may also leave written homeworks in the instructor's mailbox by the end of specified classes. Due to clock skews, project submissions will be accepted a few minutes after the specified deadlines. If your submission is more than 10 minutes late according to the machine time at the server, your submission will be considered late. No exceptions.

If you are unable to complete a homework or a programming assignment due to illness or family emergency, please see the instructor 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 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.

Office Hours

Office hours are held twice a week for one hour each. The instructor will be at the designated office for the first 15 minutes. If no students is waiting to see the instructor 15 minutes into the office hour, the instructor may cut the office hour short. You are always welcome to make an appointment to see the instructor. So, if you plan to show up after 15 minutes into the office, you are better off making an appointment.

Extra Credits

No extra credit assignments will be given for this class. So, don't bother to ask. Try your best from the beginning and don't slack off!

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 nntp.cs.umd.edu newsserver. This newsgroup serves two purposes.

When the instructor replies to a student's e-mail and feels that the rest of the class may benifit from the reply, the reply will be sent to the class newsgroup. This means that if you have a question about homeworks or projects, you should check the class newsgroup first since your question may have already been answered here.
Students can use the class newsgroup to discuss about homeworks and projects. Students may not exchange answers here because it would violate academic integrity. Posting of small code segments is allowed as long as it is meant to clarify discussions.

The instructor and the TA do not normally read the class newsgroup. Please do not post questions for them here.

Please note that you may not be able to access the class news server if you are not on campus.

E-mail

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.