CMSC 420, Section 0101 - Data Structures
Fall 2011
Announcements
- 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: lisp_p3_tests.zip. 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: grading4.4.zip
- 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 (florinc@cs.umd.edu).
- 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: grading4.2.zip and
grading4.3.zip. We ran your programs against these tests, as well as the sample input / output files posted on the class webpage
initially.
- We compiled your source files in the linux.grace.umd.edu environmnent, by running make in the directory where we decompressed your source files. If no Makefile
was provided, we ran g++ <your source files> or gcc <your source files>, depending on if they had the extension .c or .cpp.
- The command we used to run your programs was <program> < <input file> > <output file>.student. For example: part4.2 < 001.in > 001.out.student
- The display part was removed from your output files (everything starting with $$$$ and ending with EP\n.
- The primary check was to diff compare your output with ours: diff <output file> <output file>.student -w
- If there were no differences, you received full credit for the test. Otherwise, we opened the file and compared your output with ours manually. Formatting
differences were ignored.
- If your sources didn't compile, you received no credit for your homework. If the program wasn't runnable - crushed, hanged, etc., you received 0 credit for
each test it crushed / hanged for.
- The grade was computed by dividing the number of tests passed by the number of test cases (6 for part 4.2, and 32 for part 4.3) and multiplying the result by 10 and 30 respectively.
Wherever differences were minor, partial credit was given (usually, 1/2 test credit).
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:
- On the forum, you should respect the University of Maryland code of honor, as well as the course rules, presented in the Syllabus (provided on the course page). The forum should be used for general discussions, and not for posting solutions of any kind.
Any questions you may have for the instructor, or the TA, you can also post here. I'll do my best to monitor the forum and respond to any concerns as promptly as possible. However, this is not, by any means, a replacement for the office hours.
- Try to be up to date with your readings, and ask any questions you have as early as possible, so that you don't find yourselves in the situation of writing on this forum one day before the exam, and not getting an answer in time.
- The thread will be moderated. Any inappropriate / off-the-topic post will be removed. This is not a place for complaints, but rather, for technical questions and clarification.
- As a courtesy, please sign your posts, so we know whom we're talking to.
- 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
Location
CSI 1122,
TuTh 11:00am-12:15pm
Personnel
Instructor: Hanan Samet (hjs@cs.umd.edu)
Office: AVW
4425
Office hours: Tue 10:00am-11:00am
Teaching assistant: Florin Chelaru (florinc@cs.umd.edu)
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)
Syllabus
Link
Textbooks
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 linux.grace.umd.edu 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 linux.grace.umd.edu
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 linux.grace.umd.edu 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 hw01.zip
Here is a set of instructions for the submission using the GRACE cluster.
Exams
|
Exams
|
Date
|
|
Midterm Exam
|
Tuesday October 18.
|
|
 |
|
Final Exam
|
Thursday, December 15, at 8:00AM-10:00AM. The final exam is not cumulative. It covers material since the midterm.
|
Assignments
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.
Homework
|
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.in / lisp_p3_sample.out.
Here are some additional test files: lisp_p3_tests.zip. 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
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++.
Resources
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.
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
Link
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 linux.grace.umd.edu.
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.
