1. All your scores have been consolidated.
2. 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.

1. Review, Exam

1. Week 1 (1/28) : Hashing: Hash functions, expected time analysis of hashing, Quadratic probing.
   Slides [pdf] [printable]
   Weiss, Chapter 20 (all sections).
   Goodrich, 2.5.1 to 2.5.5
   Samet, Notes. Section 6.2 up to Gonnet-Munro).
2. 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.
   Slides [pdf] [printable]
   Weiss (Sections 18.1, 18.2 and 18.4).
   Goodrich 2.3
3. Week 3 (2/11) Simple, compressed and Patricia tries. Comparision with binary search trees.
   Slides [pdf] [printable]
   Goodrich (Section 9.2.1, 9.2.2).
   Samet Notes 5.3
4. 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 presented).
   Slides [pdf] [printable]
   Weiss (Section 19.3)
   Goodrich (Section )
   Samet Notes (Section )
5. 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
   Slides [pdf] [printable]
   Weiss (Section 19.4)
   Goodrich (Section )
   Samet Notes (Pages 201, 202 )
6. Week 6: (3/4) How to do ordered search: Splay Trees, and Amortized Complexity.
   Slides [pdf] [printable]
   Weiss (Chapter 22, except top down splaying)
   Goodrich (Section )
   Samet Notes ()
7. Week 7: (3/11) Splay tree proof. B+-tree Search, Insert
   Slides [pdf] [printable]
   Weiss Section 19.8
   Goodrich (Section )
   Samet Notes (216-223).
8. Week 8: (3/18). Review and Midterm exam. Mid term course evaluation (informal).
9. Week 9 (3/25): Spring break.
10. Week 10 (4/1): Second exam. Solutions. Review of material covered, midterm examination, midterm student feedback.
11. Week 11 (4/8): Delete algorithm for B+-tree. Introduction to spatial data structures.
    Slides [pdf] [printable]
    Goodrich (Section 12.3)
    Samet Notes ()
12. Week 12 (4/15): kd-trees.
    Slides [pdf] [printable]
13. Week 13 (4/22): Nearest Neighbors
    Slides [pdf] [printable]
    Priority queues and Nearest Neigbours.
    Slides pdf Printable
    Weiss (Section 21.1, 21.2)
14. Week 14 (4/29): Range Search with kd-trees.
    Slides [pdf] [printable]
    Range Search with Range Trees
    Slides [printable]
    Goodrich (Section 12.1)
    Also in Samet Notes (pages 273-277)
15. Week 15 (5/6): Potourri:
    Quadtrees revisited. Slides [printable]
    Skip Lists. Slides [printable] Goodrich (Section 3.5). See Samet Notes (pages 208-212)
    Union Find, Slides [printable] Weiss (Section 24.3, 24.4)
16. Week 15 (5/13): Ackermann Function. Review.

The schedule (of things yet to be covered) below is tentative. Some overlap between weeks is expected.

1. Week 11 (4/8): Multi-dimensional Search: Priority Range Trees.
2. 5/17: Final exam. Location: TBA. 1:30-3:30 pm.

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!

1. Skip list demos. Useful to watch inserts. Another More animated version.
2. Splay Tree Demo. It would be nice to see animation of intermediate steps, this is not shown.
3. Five hashing algorithms. Unfortunately doesn't do the sophisticated ones that we did in class.
4. Binary Search trees and AVL tree demo. Uncheck the AVL box to get a simple binary tree.
5. Some graph algorithms.
6. Spatial data structures.

Assignments are not optional. You MUST submit every assignment.

1. Assignment 0: Please send the TA your correct student id, name and preferred name (alias used for posting grades on the web page).
2. Assignment 1: Homework Number 1 [pdf] [printable].
3. Programming Assignment 1: is here. Final part (that is (d)) is due on April 11
   1. Part (a). Due Feb 21.
   2. Part (b). Due Mar 7.
   3. Part (c). Due Mar 22.
   4. Part (d). Due April 11.
4. Programming Assignment 2: Due May 13!.
5. Homework Number 2 [pdf]
6. Homework Number 3 [pdf]
7. Homework Number 4 [pdf]

• Grading (these numbers are approximate, the final numbers will be tweaked to give YOU the MAXIMUM possible grade).
  1. Four-Six Homework: 15-20%
  2. Midterm Exam: 25%
  3. Programming Assignment: 20-25%
  4. 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 need.
• 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.

1. Last programming assignment was discussed in class on Tuesday Apr 30 (see below for updated specs)
2. Homework 4 has been placed (see in the Tasks section)
3. Course evaluation was completed as announced on Tuesday Apr 30
4. Makeup Exam ONLY on 4/2 (no other days, please). Review on 4/2. Discussion on feedback on 4/2 and 4/4.
5. Programment assigment 1C has been announced. Due after midterm exam.
6. Midterm next Thursday (Mar 21). Please have your review questions ready.
7. Midterm course eval will happen on Mar 21. You will probably receive your 1B grades and hw2 grades by Mar 21.
8. Homework 2 is up. Due on March 14 (before class)
9. Please pick up solutions, handouts, unpicked assignments (such as homework) within two week of when they are first made available. No guarantees after that.
10. Modification to programming assignment specs for 1-B were given on Feb 28. Due Mar 7!
11. Homework 1 solutions were given on Feb 21
12. Homework 1 is out (Feb 12)
13. and so are the specs of programming assignment 1.
14. 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 start.
15. 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.
16. Please read all sections of this page carefully (whenever you read it).
17. Welcome to the course. I enjoy teaching, I hope you have fun in the course.
18. 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!
19. You must identify yourself CLEARLY on your project submissions AND all submissions.
20. 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).
21. If you do not want your marks to be displayed, please let the me or the TA know.
22. All course related mails will be sent to the course mailing list cmsc420-0401-spr02@coursemail.umd.edu. Please subscribe to it. Please visit http://www.helpdesk.umd.edu/mail/coursemail/ for information on how to subscribe to course mailing lists.
23. 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 next week.
    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).

1. The questions.
2. The result.