UMD Logo

Data Structures - CMSC 420, Fall 2000, Section 0301
Basic Information

Class Resources

News
  • 12/11: The final exam on 12/19/2000 will cover the following topics (in addition to the midterm topics):

    • PM1 Quadtree (branch and bound, Union/Find -- project part (4))
    • 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, Depth First Search, Breadth First Search
    • Sequential Searching, Self Organized Files, Binary Search Trees, AVL Trees
    • List Array, Skip List
    • B-tree, B+-tree, Digital Searching, Patrician Trie
    • Hashing Methods, Separate Chaining, In-place Chaining, Open Addressing with Linear & Quadratic Probing, Double Hashing
    • Memory Allocation, Buddy System
    • Inverted List, Region Quadtree, Point/MX/PR Quadtrees
    • K-d Tree
    • PM1/2/3 Quadtree, RECT quadtree

    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 a final exam question may 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 for 120 minutes. No calculators are allowed.

  • 11/26: All class login ids and files for this course will be deleted on December 27, 2000.
  • 11/17: Project part (4) test data part4.dat is available (you should have been testing with part2.dat anyway). If you've found any problems with it, please send e-mail to the instructor as soon as possible.

    Please note that there is no DELETE() in this test data file. The quadtree is cleared using INIT_PM1_QUADTREE(). Please remember that this does not clear the database of line segments.

  • 10/18: The new project part (4) deadline is Friday December 1st at 11:59PM. No late submissions.
  • 10/16: The midterm on 10/24/2000 will cover the following topics:

    • PM1 Quadtree Insertion / Deletion / Display
    • AVL Tree Insertion / Rotation
    • Selection Sort, Bubble Sort, Insertion Sort, Distribution Counting, Shell Sort
    • Binary Tree Traversal (Inorder, Preorder, Postorder)
    • Forests to Binary Tree Conversion
    • Threaded Binary 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 to you bring your photo ID. This midterm is closed book, closed notes, closed everything, and it will last 75 minutes. No calculators are allowed.

  • 10/8: Project part (3) test data part3.dat is available (you should have been testing with part2.dat anyway). If you find any problems with it, please send e-mail to the instructor and the TA as soon as possible. Please note the following when you test with part3.dat:

    1. You should get the same quadtree before and after line segment EC is deleted and subsequently inserted back into the quadtree; i.e., the results of DISPLAY() after line 26 and line 33 should be identical.
    2. There should be no trouble inserting line segment NO_TROUBLE.
    3. You should get the same quadtree before and after line segment NO_TROUBLE is inserted and subsequently deleted from the quadtree; i.e., the results of DISPLAY() after line 26 and line 38 should be identical.
    4. Inserting line segment BAD should fail and the quadtree should stay the same; i.e., the results of DISPLAY() after line 26 and line 41 should be identical.
  • 10/2: The midterm exam will be on 10/24/2000.
  • 9/11: Project part (2) test data: part2.dat and part2.bad, is available. If you find any problems with it, please send e-mail to the instructor and the TA as soon as possible.
  • 9/10: I've made a mistake in assigning project parts percentages. For some reasons, I thought parts (3) and (4) had 8 operations each ... as was pointed out by someone in class, part (4) only has 6 operations. Therefore, the new assignment of project parts percentages is:

    part (1): 10%
    part (2): 10%
    part (3): 40%
    part (4): 40%
  • 5/24: To request a class account, please send e-mail to the instructor after the semester starts.

  • 5/24: University of Maryland students needing access to the restricted parts of the class web pages from outside of umd.edu, please send e-mail the instructor after the semester starts.

Important Information about the Class Project
The class project will be 1,000+ lines of C/C++ code to be developed on a UNIX environment. No other programming language will be accepted and your program must compile and run with a makefile on a class account machine. You must be familiar with the UNIX development environment (vi/pico/emacs, cc/gcc or g++/cxx, make, etc.)

The first part of the project is due exactly one week after the first day of class and the second part of the project is due exactly two weeks after the first day of class. No late submissions will be accepted.

If a student signs up late for this class, he/she is still required to turn in parts (1) and (2) of the project on time or he/she will receive a score of 0 for these assignments (parts 1 and 2 are each worth 10% of the total project grade). No exceptions!

Making a resonable effort on the class project is required for this class. This means that no matter how well you do on the midterm or the final, you stand the chance of failing the class unless you turn in a working project and you demonstrate that you've made a good effort on doing the project.
 

[Last updated Mon Dec 11 2000]    [Please see copyright regarding copying.]