CMSC 420, Section 0101 - Data Structures

Fall 2011


7 Dec 2011
The deadline for the last Lisp project has been extended to Tuesday, Dec 13, 2011
Posted some tips and hints on the forum page, to aid with getting the last project done: here. Also posted some tests with the same format that will be used for grading: Good luck!
30 Nov 2011
Updated due date for the last Lisp project: Thursday, December 8, 2011
29 Nov 2011
Posted some clarifications about the last Lisp project on the forum. Also posted sample input/output files. Please see Assignments.
28 Nov 2011
Uploaded a file containing the fexpr, implode, and explode macro definitions for the last Lisp project. You can download it from here or see Assignments.
23 Nov 2011
The tests used for grading the 4th part of the Quadtree project have been uploaded:
22 Nov 2011
Have a nice Thanksgiving Holiday!
The tests for Lisp Project 2 have been posted here. The archive contains a README.txt file with running instructions (which are slightly different than for the last project). Please send me (Florin) an email if there's something causing confusion, and I'll try to help out.
16 Nov 2011
Updated due date for the 2nd Lisp Project: 29 Nov 2011.
11 Nov 2011
Corrected the in-class questions. (Some confusion there.) Please see Assignments.
10 Nov 2011
Added some additional clarifications on the forum, about efficiency. Please visit this particular thread more often until you submit the project - based on the questions you guys send me, I might write additional advice.
Updated the tests for Lisp Project 1 - there was an error in 3_b2.out - used NIL instead of nil.
Posted the in-class questions that are due next Tuesday (15 Nov 2011). See Assignments.
9 Nov 2011
The tests for Lisp Project 1 have been posted here. The archive contains a .txt file with running instructions. Please send me (Florin) an email if there's something causing confusion, and I'll try to help out.
The due date for Lisp Project 1 has been extended: 11 Nov 2011, 11:59 PM
You can find submission instructions, as well as some hints for the project here
4 Nov 2011
Added some files that may help out when you start coding in Lisp. See Assignments.
1 Nov 2011
The class on Thursday, Nov 3rd, 2011 has been cancelled. (The instructor is out of town.)
27 Oct 2011
The Midterm grades distribution has been posted in the Exams section.
22 Oct 2011
The TA office hours session on Monday, October 24 will be canceled. For any urgent questions, please send an email (
14 Oct 2011
Following the discussion about parts 2 and 3 of the project in class, we're posting the input / output files used to test your projects: and We ran your programs against these tests, as well as the sample input / output files posted on the class webpage initially. As stated in class, on Monday, Oct 17 there will be an extended office hours session, starting at 11:00 AM, which will go on for as long as it needs to. Before coming to ask for extra credit, you should run the tests at home, and make sure your program runs correctly. Be advised that I will run your programs using the source files you submitted! In other words, for this session, you are not allowed to make any changes in your code. You will only get extra credit if you manage to show that you was penalised for tests that produce the correct output (either on your machine, or on the linux environment).
10 Oct 2011
Midterm exam date was set and posted on the class webpage: 18 Oct 2011
5 Oct 2011
Posted new Lisp assignments in the Lisp Projects section. See Assignments.
Posted due dates for projects and homework assignments. See Assignments.
Posted sample input / output for part 4.4 of the first assignment. Also posted a sample drawing and opened a new forum thread with notes and clarifications. See Assignments.
29 Sep 2011
Important message from the Professor: Dear Students - as you know, the class of Thursday, September 29, was canceled. We will not have a makeup class on Friday. We will meet again on Tuesday, October 4. You are given an extension for submitting part 3, by Friday, September 30 at midnight. It is important to turn in a working project. If you have not finished by the due time, you still will need to turn in a working project which will be late and I will apply a late penalty to be determined later. Please make sure to get going on Part 4 as soon as you can. Thanks and see you on Tuesday. Hanan Samet.
27 Sep 2011
Added one more example of input-output for part 4.3. See Assignments.
New Homework Assignments posted, with due dates 4 Oct 2011, and 11 Oct 2011. See Assignments.
22 Sep 2011
Several students asked me to change the TA Office Hours session on Monday, because they have overlapping classes at that time. Here is a poll on the forum page, for choosing a new time. At the end of next week there will be another update on the class webpage if the time changes.
21 Sep 2011
Important: There's an error in the data structure code you received last week.
On page 4, look for the line struct bNode *rectTree; /* Rectangle bin tree; sorted w/respect to rect names */
Replace that with: struct Rectangle *rectTree; /* Rectangle bin tree; sorted w/respect to rect names */
19 Sep 2011
Updated due date for the 3rd part of the project assignment: Sep 29, 2011. See Assignments.
Added additional notes, sample input / output files. See the part 3 section of the project assignment, in Assignments.
15 Sep 2011
Updated due date for the 2nd homework assignment. See Assignments.
10 Sep 2011
Updated homework assignment 1 - for problem 3, you can use any pseudo-code.
Added instructions on how to submit your work via the GRACE cluster. See Assignments.
Sample input and output files for the 2nd part of the projects are up. See Assignments.
The drawing routines for the 3rd part of the project are up. Please see the Assignments section.
The class forum is up at this address. A few rules:
Part 2 of the first project is due Thursday, Sep 15. Please see Assignments.
7 Sep 2011
Added clarifications on what you should hand in for each assignment. Please see Assignments.
Added some instructions on how to submit your work using the GRACE cluster. See Class Accounts, under Course Info
3 Sep 2011
Since the TA office hours before the due assignment fall on a holiday (Monday - Labor Day), there will be a make-up office hours session on Wednesday, September 7, at 11:00am-12:00pm.
Programming assignment 1 rules modified. Please download the latest version of the file.
1 Sep 2011
Programming assignment 1 due date updated: 8 Sep 2011
Homework assignment 1 due date updated: 13 Sep 2011
Programming assignment 1 posted.
Homework assignments 1 and 2 posted.
31 Aug 2011
Syllabus posted.
30 Aug 2011
Web page created.

Course Info

11:38 AM 9/7/2011


CSI 1122, TuTh 11:00am-12:15pm


Instructor: Hanan Samet (
Office: AVW 4425
Office hours: Tue 10:00am-11:00am

Teaching assistant: Florin Chelaru (
Office: TA Room (AVW 1112)
Office hours: Mon 11:00am-12:00pm; Thu 3:30pm-4:30pm.
(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.

In order to submit your work using the GRACE cluster, log on with your Directory ID and password, and run a command of the following format:

submit 2011 fall cmsc 420 0101 <homework #> <your archive>.zip

where <homework #> represents the number corresponding to the homework number (1 for the first, 2 for the second, etc), and <your archive>.zip is the archive containing the files of your homework. For example: submit 2011 fall cmsc 420 0101 1

Here is a set of instructions for the submission using the GRACE cluster.


Exams Date
Midterm Exam Tuesday October 18.
CMSC420-0101 Fall 2011 Midterm Grades Distribution
Final Exam Thursday, December 15, at 8:00AM-10:00AM. The final exam is not cumulative. It covers material since the midterm.


For the first part of the programming assignment, as well as for all the homeworks, you should hand in printed copies to the professor / TA at the time of the lecture. For the rest of the programming assignments, you should submit electronic copies via the GRACE cluster.


Assignment Due Date
Assignment 1 13 Sep 2011
Assignment 2 20 Sep 2011
Assignment 3 - Sorting 4 Oct 2011
Assignment 4 - Searching 11 Oct 2011
In-class questions (Exercises 34 and 36 in Section 2.3 of the Notes on Data Structures book, pages 114 and 115):
  • Prove that the definition of APPEND is associative. In other words, APPEND(x,APPEND(y,APPEND(APPEND(x,y),z). [Hint: use induction on the length of the list bound to x.]
  • Show how the FLAT function can be transformed to yield the FLAT2 function using the transformations we described for adding an accumulator variable and thereby making the function be tail recursive.
15 Nov 2011

Lisp Projects

Assignment Due Date Test Data Other
Written Assignment 1 11 Oct 2011
Written Assignment 2 13 Oct 2011
Lisp Warmup 25 Oct 2011
Lisp Project 1 (Programming Project 3) New due date: 11 Nov 2011, 11:59 PM You can find the test data at this location. The archive contains a readme file with instructions on running the tests. Florin: I have put together a set of files that I hope will help you guys get started with Lisp (if you haven't already). It mostly contains functions and macros that you may find useful. There are also some links in there that you may like to look at. lisp help 1, lisp help 2, and lisp help 3. Submission instructions and some hints: here
Lisp Project 2 (Programming Project 4) 29 Nov 2011 You can find the test data at this location. The archive contains a readme file with instructions on running the tests.
Lisp Project 3 (Programming Project 5) Updated due date: 13 Dec 2011

Sample input/output files for the project can be found here: / lisp_p3_sample.out.

Here are some additional test files: IMPORTANT: The same test format will be used for grading, so make sure all of these tests pass!

Here is the file containing the fexpr macro as well as the "implode"/"explode" functions definitions. Note that you should copy/paste this file into your lisp program.

Some clarification about the project, and submission instructions, on the forum.

Programming Project

Assignment Due Date Other
Assignment 1 (Part 1) 8 Sep 2011 [The rules in the abstract of the assignment have been updated on 9/3/11.]
Assignment 1 (Part 2) 15 Sep 2011
Assignment 1 (Part 3) 29 Sep 2011 The drawing routines are posted here. For detailed use, read the notes on the class forum page.
Assignment 1 (Part 4) 13 Oct 2011 See the thread entitled Project 1 Part 4.4 Notes on the forum page.

A few rules for the programming projects

The permitted programming languages for the projects are C, C++, and PASCAL. Java is not permitted. Also, you are not allowed to make use of any built in data structures from any library such as, but not limited to, STL in C++.


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]
Trees [anim] [cum]
Graphs [anim] [cum]
Winged Edge Data Structure [anim] [cum]
Triangulations [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]
Quadtrees [anim] [cum]
Surface Data [anim] [cum]
3d Data [anim] [cum]
Lisp [anim] [cum]
Laths [anim] [cum]

All course materials are copyright © Hanan Samet 2011. 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.