
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, Radixexchange 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
 Btree, B+tree, Digital Searching, Patrician Trie
 Hashing Methods, Separate Chaining, Inplace Chaining, Open
Addressing with Linear & Quadratic Probing, Double Hashing
 Memory Allocation, Buddy System
 Inverted List, Region Quadtree, Point/MX/PR Quadtrees
 Kd 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 postmidterm material. However, you are
still responsible for knowing the premidterm 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.
 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 (Singlylinked, Doublylinked, 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 email to the instructor and the TA as soon as possible.
Please note the following when you test with part3.dat:
 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.
 There should be no trouble inserting line segment NO_TROUBLE.
 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.
 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 email 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 email 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 email 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.

