CMSC 420, Section 0101 - Data Structures

Fall 2010


12 Nov 2010
LISP assignment 4 is posted and is due on Nov 16th.
17 Oct 2010
The due date for Project 1 - Part 4 is extended to Oct 26th.
17 Oct 2010
The hint section in the updated project description now includes some hints on how to implement the operations that require using a priority queue.
13 Oct 2010
Searching assignment and LISP assignment 1 - 3 have been posted.
10 Oct 2010
There is a new hint section added to the end of the updated project description.
5 Oct 2010
The mid-term exam will be on Oct 21st.
27 Sep 2010
Assignment 3 has been posted.
27 Sep 2010
The new specification for project 1 has updated to fix some typos / minor mistakes.
22 Sep 2010
An updated specification for project 1 has been posted.
15 Sep 2010
Homework assignment 2 has been posted. It is due on Thu, 23 Sep 2010.
11 Sep 2010
Here is the information that you need to submit the part 2 of the project 1:
  1. We will be using the submit server for submission/grading of the projects. Please make sure that you can login to submit server. Please let the TA know if you cannot login ASAP.
  2. There is a sample input/output file for the part2 of the project available on the course webpage. There is also a tar file containing the stub file for your code, drawing routines, Makefiles and the submit script.
  3. The starter files contain an empty file which you should edit to implement the decoder. Your decoder should read from the standard input and write to the standard output.
  4. You can submit your code by running the script
  5. The starter files also include the drawing routines/tools. There is also a README file. The documentation for the drawing routines is provided in the comments in drawing_c.h.
7 Sep 2010
The deadline for Homework assignment 1 has been extended to Tue, 14 Sep 2010.
30 Aug 2010
The quadtree project description has been posted. Part 1 is due on Tue, 7 Sep 2010.
Homework assignment 1 has been posted. It is due on Thu, 9 Sep 2010.
27 Aug 2010
Syllabus posted.
13 Aug 2010
Web page created.

Course Info


CSI 1121, TuTh 9:30am-10:45am


Instructor: Hanan Samet
Office: AVW 4425
Office hours: Tu 11am-noon

Teaching assistant: Saeed Alaei
Office: TA Room (AVW 1112)
Office hours: Monday 1:30pm-2:30pm, Friday 3:00pm-4:00pm
(Please email the TA if none of the above hours work for you)




H. Samet. Foundations of Multi-Dimensional and Metric Data Structures. Morgan Kaufmann, 2006. ISBN 0-12-3694469.

H. Samet. Notes on Data Structures. University of Maryland, College Park, MD, 2003 (available for purchase in lecture note form at the University Book Center)

Class Accounts

All projects should compile and will be tested on the GRACE cluster, and specifically on one of the machines. To access GRACE, you will need a Glue account. Click here for information about gaining access to and using the GRACE cluster, as well as requesting a Glue account.

Once your account is activated, you should be able to access GRACE by using an SSH client. Click here to see a list of OIT-supported SSH software. Use your client to connect to using your Directory ID and password.

If you have trouble connecting to GRACE or questions about class accounts, please notify the teaching assistant.


Midterm ExamThursday, Oct 21
Final ExamTuesday, Dec 14, 8:00am-10:00am



AssignmentDue Date
Assignment 1Sep 14th 2010
Assignment 2Sep 23rd 2010
Assignment 3Oct 5th 2010
Assignment (Searching) Oct 19th 2010
LISP Assignment 1Oct 19th 2010
LISP Assignment 2Oct 28th 2010
LISP Assignment 3Oct 28th 2010
LISP Assignment 4Nov 16th 2010

Quadtree Projects

Link to project description

Link to the updated project descriptoin

AssignmentDue DateSample Test DataOtherAll Test Data
Part 17 Sep 2010N/A
Part 214 Sep 2010 [sample input ][sample output] [starter files] [all tests]
Part 330 Sep 2010 [sample input ][sample output] [starter files] [all tests]
Part 426 Oct 2010 [sample input ][sample output] [starter files]

Lisp Projects

AssignmentDue DateTest DataOther
LISP Project 111 Nov 2010 [sample input ][sample output] [starter files]
LISP Project 223 Nov 2010 [sample input ][sample output] [starter files]
LISP Project 39 Dec 2010 [sample input ][sample output] [starter files]


Lecture Slides

These lecture slides are a natural complement to the textbooks, and are provided here for your information. Each slide set has two versions: "Animated" and "Cumulative". The Animated slides contain multiple overlays per slide, which are traversed in sequence. This makes for more understandable viewing on your computer. The Cumulative slides contain only the slides after all layers have been added, which saves paper if you need to print the slides.

List Structures[anim][cum]
Winged Edge Data Structure[anim][cum]
Searching Techniques[anim][cum]
Sorting Techniques[anim][cum]
Dynamic Storage Allocation[anim][cum]
Garbage Collection[anim][cum]
Representation of Point Data[anim][cum]
Rectangle Data[anim][cum]
Range Trees[anim][cum]
Hashing Methods[anim][cum]
Nearest Neighbor[anim][cum]
Bulk Loading[anim][cum]
Surface Data[anim][cum]
3d Data[anim][cum]

All course materials are copyright © Hanan Samet 2010. All rights reserved. Students are permitted to use course materials for their own personal use only. Course materials may not be reproduced by any means (mechanical, electronic, or any other) and/or distributed without the express written permission of Hanan Samet.

Spatial Index Demo Applets


Lisp Information

Some useful Lisp resources:

The Lisp interpreter that we'll be using is called Allegro Common Lisp (or Franz Lisp). It is installed on the GRACE cluster, so just connect as normal to

Once connected, run the command tap allegro81 to get access to the Lisp interpreter. To start up the interpreter, run mlisp. You should now have a Lisp prompt, and you can begin entering Lisp commands and seeing the results.

If you have your Lisp program stored in a file called, for example, helloworld.lisp, you can load the program by entering (load "helloworld") at the Lisp prompt. Note that you don't need to include the .lisp extension in the argument to load the program.