UMD Logo

Data Structures - CMSC 420, Fall 1999, Section 0301
Basic Information
  • Time: TuTh 9:30am - 10:45am
  • Location: CLB 0111

  • Instructor: Leana Golubchik, E-mail: leana@cs.umd.edu
  • Office: 4129 AVW, Office Hours: Tu 10:45am - 11:45am, Th 5:00 - 6:00 pm, or by appointment

  • TA: Kuo-Tung Kuo, E-mail: ktg@cs.umd.edu
  • Office: 1152 AVW, Office Hours: Wed: 2:00pm - 3:00pm, Fri: 2:00pm - 3:00pm, or by appointment

  • Class accounts: UNIX accounts on the OIT (Office of Information Technology) UNIX cluster systems.

  • Class newsgroup: csd.cmsc420.0301

News
  • 12/12: The final exam on 12/20/99 will focus on the following topics:

    • RECT Quadtree (branch and bound)
    • Tournament Sort, Heap Sort, Priority Queues, Quick Sort, Median Computation, Radix-exchange Sort, Radix Sort, Merge Sort, Polyphase Merge
    • Graphs, Minimum Spanning Tree, Shortest Path Algorithm
    • Sequential Searching, Self Organized Files, Binary Search Trees, AVL Trees
    • List Arrays, Skip Lists
    • B-trees, B+-trees, Digital Searching
    • Hashing Methods
    • Memory Allocation and Garbage Collection
    • Point Quadtree, Region Quadtree, MX Quadtree, PR Quadtree, PM1 Quadtree
    • K-D Trees

    Note that, as can be seen by the list of topics above, the final exam will focus on the post-midterm material. However, you are still responsible for knowing the pre-midterm material and being able to use in solving final exam questions (even though final exam questions will not be testing you directly on that material). For instance, it is fair game for us to ask a question whose solution involves the use of stacks. (Note that, this is just an example.)

    Make sure you bring your photo ID. The final is closed book, closed notes, closed everything, and it will last 120 minutes.

  • 12/8: Reminder: final exam will be 10:30am - 12:30pm on 12/20/99.
  • 12/8: Midterm solutions are now available.
  • 12/3: Homework 4 will be due on 12/14/99. There is NO late submission for this homework assignment. Please see the homeworks page.
  • 11/23: Homework 3 will be due on 12/2/99. Please see the Homeworks section below.
  • 11/22: The deadline for project part (4) has been extended. Project part (4) is now due late night on Wednesday, 12/1/99 (you can think of it as being due at 11:59:59 PM on 12/1/99). As before, late policy applies and your submission must compile and link as is, or you will get at most 10% of the 50 points allocated to part (4).

  • 11/22: Update on the way the final grade will be calculated. During the first lecture, it was announced that, tentatively, your final grade was supposed to be calculated as follows: 
        HW      10%
    Project 30%
    Midterm 25%
    Final   35%
    The new scheme is that HW is still 10% of your final grade. Your best score among Project/Midterm/Final will be worth 35%, your second best score among Project/Midterm/Final will be worth 30%, and your worst score among Project/Midterm/Final will be worth 25%. (Note: The way your project score is calculated was also mentioned in the first lecture.)
  • 11/17: There was an error in the initial version of part4.sol. The answer to the WITHIN(Q4,16) should have been "B D F L". It has been corrected.

  • 11/17: There was an error in the initial version of part4.dat. The width of rectangle G should have been 20. It has been corrected.
  • 11/16: Project part (4) test data and solution are available. Please see the Project section below. If you do not agree with the solution, please send e-mail to both the instructor and the TA as soon as possible.

    When you submit part (4), you must include with your submission a test data file named part4.dat. This will be the test data file which you claim will produce no errors when we run your submission on it.

    For example, if your program is p4, then running: 

        p4 < part4.dat
    shall produce no errors. For this purpose, you can use the test data provided by us or submit your own test data. Note that, your submission will be tested on other test data in addition to part4.dat in your submission.

  • 11/16: Just a reminder. Project part (4) is due late night on Wednesday, 11/24/99 (you can think of it as being due at 11:59:59 PM on Wednesday). Late policy applies. As mentioned before, what you submit must compile and link as is, or you will get at most 10% of the 50 points allocated to part (4).
  • 10/28: Project part (4) clarifications are posted with the lecture 17 slides. Please check them and send the instructor comments if they are unclear.
  • 10/18: The midterm on 10/21/99 will cover the following topics:

    • RECT Quadtree
    • Selection Sort, Bubble Sort, Insertion Sort, Distribution Counting, Shell Sort
    • Binary Tree Traversal (Inorder, Preorder, Postorder)
    • Forests to Binary Tree Conversion
    • Replacement of Subtree in a Threaded Tree
    • Equivalence Relations / Equivalence Classes
    • XOR Lists / XOR Trees
    • Expression Generation from Binary Tree to Parenthesized Infix Expression
    • Topological Sort
    • Array Index / Location
    • Lists (Singly-linked, Doubly-linked, Circular)
    • Stacks / Queues / Deques

    Make sure you bring your photo ID. This midterm is closed book, closed notes, closed everything, and it lasts for 75 minutes.

  • 10/17: Just a reminder. Project part (3) is due late night on Monday, 10/18/99 (you can think of it as being due at 11:59:59 PM on Monday). Late policy applies. As mentioned before, what you submit must compile and link as is, or you will get at most 10% of the 30 points allocated to part (3). Also, make sure you include a file named part3.dat which contains test data you claim your program can handle. This is for your own benefit!
  • 10/11: Project part (3) test data is available. Please see the Project section below. When you submit part (3), you must include with your submission a test data file named part3.dat. This will be the test data file which you claim will produce no errors when we run your submission on it.

    For example, if your program is p3, then running 

        p3 < part3.dat
    shall produce no errors. For this purpose, you can use the test data provided by us or submit your own test data. Note that, your submission will be tested on other test data in addition to part3.dat in your submission.

    You are reminded here again to read the 9/18 news item below about how your submission must compile and link as is.

  • 10/7: Homework 2 will be due on 10/14/99. Please see the Homeworks section below.
  • 10/6: In implementing the LIST_RECTANGLES() operation it is OK to use strcmp (i.e., you do not have to write your own string comparison function). But, you have to make sure to document that fact in your project submission.
  • 10/4: For problem 6 of HW1, you can think of the list as having n+2 nodes with one dummy node H1(L) at the beginning and one dummy node H2(L) at the end. The pointer field of H1(L) contains the address of real node 0 and the pointer field of H2(L) contains the address of real node n-1 and you are asked to delete one of the real nodes.

  • 10/4: For problems 2 and 3 of HW1, you need to use pointer manipulation (you can not exchange contents of nodes).

  • 10/4: Project clarification -- The left and bottom sides of a rectangle are closed and the top and right sides are open. Thus the open and closed conventions are the same for both the rectangles and the quadrant subdivision lines. Please see Project clarifications (also given below) for details.
  • 9/29: Homework 1 will be due on 10/7/99. Please see the Homeworks section below.
  • 9/20: The midterm exam will be on 10/21/99, during class.
  • 9/18: Project part (3) is due on 10/18/99 at midnight (late policy applies). If what you submit does not compile and link as is, you will receive at most 10% of the 30 points allocated to part (3).

    There will be no solutions for part (3) of the project. So if you can not get enough things to work for part (3), you will be in trouble for part (4) which is worth 50 points.

    Project part (4) is due on 11/24/99 at midnight (late policy also applies -- but you'll be working on Thanksgiving). If what you submit does not compile and link as is, you will receive at most 10% of the 50 points allocated to part (4).

  • 9/18: For all remaining parts of the project you must follow the submission procedure. There are no e-mail submissions for the rest of the project. Please read the procedure very carefully. If you miss a file, you will not receive credit for it. If you do not submit a Makefile, we are not going to create one for you.

  • 9/18: Regarding test data: please see the Project section below. Inside the library of drawing routines, there is a file called test.mxcif. At the top of that file, there are a few lines that can be used as test data.

    Please note that there is an error in the 2nd CREATE_RECTANGLE() in test.mxcif. The last number should be an integer. Also, please interpret the coordinates as in the project description (and ignore the outputs in test.mxcif where it says that the first 2 coordinates specify the center of a rectangle).

  • 9/13: Some people have been asking what exactly does it mean that you must use the solution to part (1). What it means is that you must follow the spirit of the data structures given in the solutions to part (1) of the project for the rest of the project. You do not have to use exactly those data structures, but you should not stray too far from them.

    For example, the data structures imply that the rectangles are organized in a binary search tree. You can use an external structure if you like, but you must use a binary search tree. If you use a linear list to organize rectangles, you will receive a very low score on your project.

    Another example is that the data structures in the solution imply that a leaf node of the quadtree has a pointer to a rectangle data structure; therefore, you must not embed a rectangle data structure inside a quadtree node.

  • 9/13: Please read the class newsgroup for a sample output for part (2) of the project.
  • 9/13: Some peoploe have been asking what the terminating command is for the command decoder. Please use end-of-file detection. If you are using fgets(), "man fgets" says that it returns a null pointer when end-of-file is detected. If you are using something other than fgets(), there are equivalent conditions.
  • 9/10: Lecture Notes page has been updated with slides in PDF and gzipped 2-up PostScript formats.
  • 9/9: New project related information has been posted below, including: (1) library of drawing routines, (2) corresponding description, and (3) project submission guidelines. Please remember that you must use the solutions to part (1) of the project to do parts (2), (3), and (4).
  • 9/9: Solutions to part (1) of the project are now posted by Dr. Golubchik's office (4129 AVW).
  • 9/7: Dr. Golubchik's Thu's office hours have been changed.
  • 9/6: Lecture 1 notes have been posted.
  • 9/6: There was a mistake in Figure C of the project description; the corresponding project and lecture notes web pages have been modified to correct that mistake.
  • 9/1: The class project has been assigned. Part (1) is due on 9/9/99; part (2) is due on 9/16/99. Part (1) is due by the beginning of class (either hardcopy submission or through email). Note that there are NO late submissions allowed for these parts of the assignment.
  • 9/1: To request a class account, send email to the TA.
  • 9/1: To request access to the restricted parts of the class web page from outside of umd.edu contact Dr. Golubchik.

Course Handouts

Projects
(Please note that access to project related information below is restricted.)
Homeworks
(Please note that access to homework related information below is restricted.)
[Last updated Sun Dec 12 1999]    [Please see copyright regarding copying.]