Data Structures - CMSC 420, Fall 2001, Section 0301

(Mirrored site for UMD class web pages.)

Basic Information

Time: TuTh 11:00am - 12:15am
Location: JMP 3201
Instructor: Bill Cheng, E-mail: <william@cs.umd.edu>
Office Hours: TuTh 1:45-2:45pm in AVW 3369
Mailbox along the right hand wall as you enter in AVW 1103
TA: Adam (Woei-Jyh) Lee, E-mail: <adamlee@cs.umd.edu>
Office Hours: Mon 4:30-5:30pm and Wed 5:30-6:30pm in AVW 1151

Class Resources

Course Description: required text books, topics covered, grading policies, etc.
Lecture Notes (access restricted): slides from lectures in HTML, PostScript, and PDF formats.
Homework Assignments (no access)
Class Project (no access) -- please read important information about the class project
Class accounts: UNIX accounts on the OIT (Office of Information Technology) UNIX cluster systems.
Class Calendar: Public Yahoo Calendar (cmsc420_bc_fall01) - check out class events here. (If you don't have a Yahoo ID, just create a new one (and remember your ID and password), then come back to this page and click on this link again.)
Class newsgroup: csd.cmsc420.0301 on the nntp.cs.umd.edu newsserver.

News

12/6: The final exam will be on 12/14/2001 from 8:00AM to 10:00AM in JMP 3201. The exam will be closed book, closed notes, closed everything, and no calculators. Make sure you bring your photo ID. The exam will will focus on the following topics:
- PM3 Quadtree Class Project
- Tournament Sort, Heap Sort, Priority Queues, Quick Sort, Median Computation, Radix-exchange Sort, Radix Sort, Merge Sort, Polyphase Merge
- Graphs, Depth First Search, Breadth First Search, Minimum Spanning Tree, Shortest Path Algorithm
- Sequential Searching, Self Organized Files, Binary Search Trees, AVL Trees, Splay Trees
- List Array, Skip List
- 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
- Winged-edge Data Structure
- 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 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.)

11/21: Project part (4) test data: part4.dat is available. If you see bugs in it, please send e-mail to the instructor ASAP.

10/24: The midterm exam on 10/30/2001 will cover the following topics:
- PM3 Quadtree Insertion / Deletion / Display
- AVL Tree Insertion / Rotation / Display
- Selection Sort, Bubble Sort, Insertion Sort, Distribution Counting, Shell Sort
- Array Representation of Complete Binary Tree
- Binary Tree Traversal (Inorder, Preorder, Postorder)
- Forests to Binary Tree Conversion
- Threaded Binary Tree
- Equivalence Relations / Equivalence Classes / Union-Find
- 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. No calculators are allowed.

10/2: The midterm exam will be on 10/30/2001 during class.

9/18: Homework 1 has been assigned. Please see the homeworks page and click on the link for Homework 1.

9/11: Because of all that has happened today, the deadline for project part (2) has been extended to 11:45PM, Sunday, 9/16/2001.

9/9: There were bugs in part2.dat and part2.bad. Specifically, WINDOW should have integer arguments. They are fixed in the updated version. Please get a new copy of these files.

9/6: Project part (2) test data are available: part2.dat contains good data and part2.bad contains bad data. If you see bugs in these files, please send e-mail to the instructor ASAP.

8/23: Please note that the final exam time for this class is Friday 12/14/2001 from 8:00AM to 10:00AM in JMP 3201.

8/17: To request a class account, please send e-mail to the instructor after the semester starts. Please include your name, e-mail address, department, and class (e.g., junior, senior, grad) in the e-mail.
8/17: 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,500+ lines of C/C++/Java 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! This requirement also applys to studnets on the wait list.