- Recent Announcements.
- All your scores have been consolidated.
- Final exam will be in EGR2107. 1:30-3:30 PM. Please
make sure you know where it is and come about 5 minutes in advance.
- Course Overview: At the end of this course, you will be able
to use (advanced) data structures with (usually optimal) algorithms that
manipulate retrieve content. You will also be familiar with mathematical
techniques for analyzing the efficiency of these data structures.
- Texts: Note the description in the text section.
- Course Prerequisites: CMSC 330. Students are expected to be
familiar with Java (we might do a quick refresher should you feel the
need). Knowledge of basic data structures (arrays, linked lists, queues)
is assumed. Knowledge of basic discrete mathematics (sets, proofs by
induction, manipulation of summation, asymptotic notations) is assumed.
- What I will cover next.
- Review, Exam
- Topics covered I sincerely thank David
Mount for providing xfig source files used in many of the slides
- Week 1 (1/28) : Hashing: Hash functions, expected time analysis of
hashing, Quadratic probing.
Weiss, Chapter 20 (all sections).
Goodrich, 2.5.1 to 2.5.5
Samet, Notes. Section 6.2 up to Gonnet-Munro).
- Week 2 (2/4) Self organizing hashing. Samet, Notes. (section 6.2
up to Gonnet Munro).
Fundamental non-linear data structure: Trees,
Ordered Trees, Binary trees.
Weiss (Sections 18.1, 18.2 and 18.4).
- Week 3 (2/11) Simple, compressed and Patricia tries. Comparision
with binary search trees.
Goodrich (Section 9.2.1, 9.2.2).
Samet Notes 5.3
- Week 4 (2/18) Suffix tries and Internet search engines. Simple
binary search trees. Expected height of a binary search tree. This
material is not available in the two text books (in the form I
Weiss (Section 19.3)
Goodrich (Section )
- Week 5 (2/25) How to do ordered search: AVL trees. restructure()
is available only in Goodrich and slides. Weiss does not discuss
delete in AVL trees
Weiss (Section 19.4)
Goodrich (Section )
(Pages 201, 202 )
- Week 6: (3/4) How to do ordered search: Splay Trees, and Amortized
Weiss (Chapter 22, except top down splaying)
Samet Notes ()
- Week 7: (3/11) Splay tree proof. B+-tree Search, Insert
Weiss Section 19.8
Goodrich (Section )
- Week 8: (3/18). Review and Midterm exam. Mid term course
- Week 9 (3/25): Spring break.
- Week 10 (4/1): Second exam. Solutions. Review of
midterm examination, midterm student feedback.
- Week 11 (4/8): Delete algorithm for B+-tree. Introduction to
spatial data structures.
Goodrich (Section 12.3)
Samet Notes ()
- Week 12 (4/15): kd-trees.
- Week 13 (4/22): Nearest Neighbors
Priority queues and Nearest Neigbours.
Weiss (Section 21.1, 21.2)
- Week 14 (4/29): Range Search with kd-trees.
Range Search with Range Trees
Goodrich (Section 12.1)
Also in Samet Notes (pages 273-277)
- Week 15 (5/6): Potourri:
Quadtrees revisited. Slides [printable]
Skip Lists. Slides [printable] Goodrich
(Section 3.5). See Samet Notes (pages 208-212)
Weiss (Section 24.3, 24.4)
- Week 15 (5/13): Ackermann Function. Review.
- Topics to be covered.
The schedule (of things yet to be covered) below is tentative. Some
overlap between weeks is expected.
- Week 11 (4/8): Multi-dimensional Search: Priority Range Trees.
- 5/17: Final exam. Location: TBA. 1:30-3:30 pm.
- Demos, samples.
I'll list some neat stuff that I come across on the Internet
(typically Java applets). If you find something, please let me know so
that I can list it here and give you brownie points!
- Skip list demos. Useful to
watch inserts. Another
More animated version.
- Splay Tree
Demo. It would be nice to see animation of intermediate
steps, this is not shown.
- Five hashing
algorithms. Unfortunately doesn't do the sophisticated
ones that we did in class.
- Binary Search trees and AVL tree
demo. Uncheck the AVL box to get a simple binary tree.
- Some graph
Spatial data structures.
Assignments are not optional. You MUST submit every assignment.
- Assignment 0: Please send the TA your correct student id, name and
preferred name (alias used for posting grades on the web page).
- Assignment 1: Homework Number 1 [pdf]
- Programming Assignment 1: is
here. Final part (that is (d)) is due on April 11
- Part (a). Due Feb 21.
- Part (b). Due Mar 7.
- Part (c). Due Mar 22.
- Part (d). Due April 11.
- Programming Assignment 2: Due May 13!.
- Homework Number 2 [pdf]
- Homework Number 3 [pdf]
- Homework Number 4 [pdf]
- Notes on evaluation.
- Grading (these numbers are approximate, the final numbers will be
tweaked to give YOU the MAXIMUM possible grade).
- Four-Six Homework: 15-20%
- Midterm Exam: 25%
- Programming Assignment: 20-25%
- Comprehensive Final exam: 35%
- Collaboration: By default, you may not discuss assignments with
friends (or anyone else for that matter). You are expected to
implement your own solutions, please do not plagiarize from the
Internet or other sources (this scheme is of course is to help you)
On the programming assignments, you are permitted (and encouraged)
to discuss your project with others, but you may not share code.
By reading these lines, you agree to these terms :-)
- Attending the class is optional.
- Homeworks are to be turned in by the start of class on the due
date. Homeworks should be written neatly on standard letter sized
paper. Please identify yourself on the homework, and number, staple
all pages. Your marks will be based on your ability to convince the
reader that your answers are correct by way of simplicity, and
elegance. (less is more).
- If you miss a submission deadline or an exam, your marks will be
rescaled (based on other assignments) ONLY in exceptional
circumstances (medical reason for example). These must be approved by
me BEFORE the due date. The default for not turning in homework is
that you get zero.
- M. A. Weiss. Data Structures and Algorithms in Java.
Addison-Wesley. 2nd Edition. This is an excellent book, and the only
problem is that it is overpriced (they all are). This book is great
for classical data structures (trees, binary search trees, heaps,
dictionaries). The problem is that it misses out on some really nice
data structures (skip lists, binomial queues, tries, spatial data
structures). The other problem (?) is that we don't really use more
than half the book. Good for CMSC 451 also.
- M. Goodrich and R. Tamassia. Algorithm Design. This is another
very nice book. The treatment is more compact than in Weiss. If you
like verbose description, choose the Weiss book. Also, as the title
suggests, it concentrates a bit more on algorithm design.
- H.Samet, Notes on Data Structures. This contains more elaborate
treatment on Hashing, Tries than any other book. Note also the section
on range trees. Like the Weiss book, it has more material than we
- H.Samet, The Design and Analysis of spatial algorithms. These
contain more details of Quadtrees, kd-trees, and other spatial data
structures. We won't be able to cover all of these.
- Old Announcements
- Last programming
assignment was discussed in class on Tuesday Apr 30 (see below for
- Homework 4 has been placed (see in the Tasks section)
- Course evaluation was completed as announced on Tuesday
- Makeup Exam ONLY on 4/2 (no other days, please). Review on 4/2.
Discussion on feedback on 4/2 and 4/4.
- Programment assigment 1C has been announced. Due after midterm
- Midterm next Thursday (Mar 21). Please have your review questions
- Midterm course eval will happen on Mar 21. You will probably
receive your 1B grades and hw2 grades by Mar 21.
- Homework 2 is up.
Due on March 14 (before class)
- Please pick up solutions, handouts, unpicked assignments (such as
homework) within two week of when they are first made available. No
guarantees after that.
- Modification to programming assignment specs for 1-B were given on
Feb 28. Due Mar 7!
- Homework 1 solutions were given on Feb 21
- Homework 1 is out (Feb 12)
- and so are the specs of programming assignment 1.
- Please start using csd.cmsc420.0401 to ask generic
questions (that is, questions not specific to your individual
circumstances). Be sure to clear out old messages the first time you
- If you have some questions that can't be placed on the newsgroup,
send email to me. But please DO NOT use HTML in emails sent to me. I
will unceremoniously delete all messages that have HTML content or
proprietary formats such as Microsoft Word. (Check your outlook,
hotmail or netscape settings for sending plain text). I'll appreciate
if you can place the string "cmsc 420" somewhere in your subject.
- Please read all sections of this page carefully (whenever you read
- Welcome to the course. I enjoy teaching, I hope you have fun in
- I know this course meets early. If you think this is a
disadvantage, you can turn things around on its head by, guess what,
planning things and making it an advantage!
- You must identify yourself CLEARLY on your project submissions AND
- If you have a quick question, drop by any time. Feel free to send
email any time. If my office hours are inconvenient, please feel free
to arrange another time. However, do not call me unless absolutely
essential (for example, email to me bounces).
- If you do not want your marks to be displayed, please let the me
or the TA know.
- All course related mails will be sent to the course mailing list
email@example.com. Please subscribe to it. Please
for information on how to subscribe to course mailing lists.
- Prerequisites will be enforced in all CMSC classes. If students
have any questions or concerns regarding this they should go to room
1119 AVW to see an advisor between 9-5pm M-F. Students who don't meet
the prerequisites will be removed from appropriate courses over the
Waitlisted Students: Please remain patient through next
week as changes are still occurring to waitlists. Remember to check in
online to Testudo every day (otherwise you are automatically dropped
from the class).
- I used to post solutions, but nowadays I hand them
out in class. Solutions may be occasionally posted and deleted
asynchronously (in order that students from other courses do not
- Mid term Course Evaluation.
- The questions.
- The result.