CMSC 420, Section 0101 - Data Structures

Fall 2014

Announcements

17 Dec 2014
The final exam is at 1:30PM-3:30PM Dec 19, 2014, in CSI2117.
15 Dec 2014
The topics whihc will be covered on the final exam are in this link, and the cover- and partition- fieldtree could be found in slides. Good Luck!
04 Dec 2014
The matrix homework has been post on the assignments section of webpage.
20 Nov 2014
The test data of lisp project 5 has been post, with the implementation of fexpr.
19 Nov 2014
Some students are asking me whether they would get extra credit for late submission of lisp projects. As Prof. Samet said in the class before the 1st lisp project due date, no late submission is accepted. I posted the last announcement because some other students who did submit the 1st lisp project before due date wanted to submit a more complete version (with implementing more functions) and wondered whether they could still get points for that part. The answer is no to both of the situations.
13 Nov 2014
No late lisp projects are accepted!
11 Nov 2014
Grading Mistake in LISP WARMUP homework    I made a mistake in grading the homework's last question of LISP WARMUP, esp. writting a "where is searchb or searchb1?", if you have this problem, please let me know so I can correct this.
30 Oct 2014
LISP APPEND and FLAT homework has been post! And No CLASS Next Tuesday!
29 Oct 2014
No homework due this Thursday!!!
26 Oct 2014
Notes ON LISP Assignments    I've been asked what functions you're allowed to use for lisp projects. For the assignments, you shouldn't look for anything more than what was already discussed in class: car, cdr, list, listp, atom, cons, append, null, and others from this range. I don't know all functions in Lisp, so I can't make a list of what you're not allowed to use. The general rule is that you should not use any functions that do the work you have to do yourself (like merge).
23 Oct 2014
IMPORTANT!     I made a mistake in the part3 sample.out.notes on the line "RECTANGLE_SEARCH(R2): found 2 rectangles: R3 R1", the correct answer is "RECTANGLE_SEARCH(R2): found 2 rectangles: R1 R3" because you have to avoid the qnode which does not intersect with your query. Thank Mingchao for pointing this out. I will re-grade the part3 for this, no points will be lost because of this.
16 Oct 2014
    The part4 due date is on Thursday, October 23rd.
12 Oct 2014
IMPORTANT!     The date of midterm is on Thursday, October 16th.There was a misprint about this in the syllabus, which has been corrected already.
09 Oct 2014
LISP Beginners!    Here is some resoure useful for beginning programming LISP, especially LISP Tutor Jr.

Here are some command tips and here is a table of commands.
09 Oct 20141
IMPORTANT!     The due date of lisp warmup has been extended one week later to 21OCT2014, to make sure you have enough time preparing for the midterm exam.
07 Oct 2014
The information about runing lisp and its development environment is in the resource sectoin here.
01 Oct 2014
-------------------- message about late policy --------------------
Dear Class,

    As I made clear at the beginning of the class, it is important to complete the class projects. All parts of the project must be turned in and working in order to pass the class. Simply doing well on the exams is not sufficient. If you are late, then you will lose about 2 points per class meeting date that you are late but you cannot punt on the project. There is no official extension. As I said, you will simply lose points for being late. As part 4 depends on things working in part 3, there is no advantage in turning in a project where certain key operations are not working (e.g., insert, delete, etc.). If your final grade is on the borderline, then I may discount the late points to help you attain the higher grade.

    Again, the key point for me in the class is that you demonstrate a mastery of the subject matter which is gauged in different ways.

Good luck.
Hanan Samet.
27 Sep 2014
I updated the sample out file in part3. If you are using the coordinate system in the ehanced description of quadtree project, you should use sample.out.notes to check your results. If you are using the coordinate system in the demo, you should use sample.out.demo to check your results.
27 Sep 2014
The coordinate systems in the sample data and the notes of the project are different. The coordinate system of rectangle in the sample data should be the on in this demo, that is, (0,0) is the upper left corner and (2^w, 2^w) is the lower right corner. In contrast, in the coordinate system in notes description, the (0,0) is the lower left corner and (2^w, 2^w) is the upper right corner. Both of these two coordinate systems are accepted. But if you've implemented your program according to the coordinate system in the notes, the output result of "RECTANGLE_SEARCH(R2)" should be "RECTANGLE_SEARCH(R2): found 2 rectangles: R3 R1" instead of "RECTANGLE_SEARCH(R2): found 2 rectangles: R1 R3". Thank Nathan for pointing this out.
26 Sep 2014
For the operation "RECTANGLE_SEARCH" and "CREATE_RECTANGLE", please refer to the specification on the enhanced notes. That is: "RECTANGLE_SEARCH" should output a list of rectangles which intersect with the given one; the parameters in "CREATE_RECTANGLE" should be "(name, lower_left_corner_x, lower_left_corner_y, upper_right_corner_x, upper_right_corner_y)". Sorry for the inconsistency.
26 Sep 2014
The slides of searching on September 25 and Setember 30 are available on here.
25 Sep 2014
The due date of part3 of quadtree project has extended to Oct 2nd, 2014.
18 Sep 2014
Class's next topic on September 25 and September 30 will be searching, please read Chapter 5 in the "Notes on Data Structures" on this topic.
16 Sep 2014
I might made a mistake in grading Assginments1. For the 7th question, I gave a failure if c0 =- 2. If you had this situation, please let me know so I can make it up.
10 Sep 2014
If you are interested in purchasing the book "Foundations of Multidimensional and Metric Data Structures", Elsevier, the publisher is running a special promotion on all books including it for 40% off. This means that the price is reduced from $83.95 to $50.37 plus sales tax. Shipping is free.

To order the book go to the publisher's (Elsevier) e store at here and place the book in your cart. At checkout, apply the special code "BTS14" to get the discount. This offer expires on September 14.
08 Sep 2014
The description of Quadtree Project has been updated, including the right due dates for the data structure part(due on 09SEP2014) of the project and also for the command decoder(due on 16SEP2014).
05 Sep 2014
Grace system is setup. See details in "Class Acounts" section on Course Info.
01 Sep 2014
Assignment #1, Assignment #2, and Syllabus posted.
Quadtree project description posted.
22 Aug 2014
Web page created.