CMSC 420: Data Structures

Course objectives: Introduce methods for organizing data so that the data can be accessed and updated efficiently within a computer program. Particular emphasis will be placed on handling data that represent geometric items such as points and lines.

The class work will consist of 4-6 homeworks, a midterm, a final, and a multipart programming project (to be done in C or C++).

Announcements

• Grades for project 2 have been emailed and posted to the grades server. The tests used can be downloaded here. The grader program accepts any ordering of genes. Regrade requests should be made by Wednesday noon.
• You should email a .zip file containing your source code and Makefile to Radu Dondera (the TA) at rdondera AT cs.umd.edu as described below.

  Please use the subject line "420 Project Submission". Please do not include your executable or .o files in the .zip file. The TAs will recompile your program with the command "make", and will run your program with the command &quo;gene_mapper < testcase.txt".

  Please name your zip file DIRECTORYID-Project2.zip, where DIRECTORYID is your UMD Directory ID name.

  For example:

  % zip carlk-Project2.zip *.cc *.h Makefile

  will create a zip file of the correct name that contains only the source files & Makefile.

  You should double check that your zip file contains all the files needed to recompile your project.

• Final exam is at: CSI 1121 Mon, May 19 10:30 am - 12:30 pm
• An extra credit homework assignment is now available. Due May 13.
• Additional Project Part 2 Notes:
  • Use the upper median when taking the median of 2k numbers. In other words, if you put 2k numbers in an 0-based array, the median would be at position k.
  • You can use qsort() or sort() to sort the elements.
• Project Part 2 Notes:
  • Our test cases won't have duplicate points in them
    
  • Two example inputs and outputs are available here
  • You can assume a "Genome" command will be issued before any "AddGene" command.
• A reference implementation of project part 1 Includes the tests that were used to determine the grade.
• Part 2 of the Programming Project is now available. Due: May 13 at 11:59pm.
• Homework 4 is now available.
• Change in class policies:
  1. Projects that are between 24 and 48 hours late will be discounted 20% (instead of 30%)
  2. Projects that are between 48 and 72 hours late will be discounted 40% (as in the syllabus)
  3. Homework must be picked up either in class the day it's returned or during my office hours (or email another time).
  4. Homework regrades: must be in writing, within 1 week of homework return. Preferably, regrade requests should be submitted to the TAs first.
• Each project part is worth 15% of the total class grade.
  
  

  ---

  Older Announcements

  ---

Lecture Slides

1. 1/29 Introduction, review of big-O, data structuring principles [PDF]
   Reading: Shaffer chapter 1, review chapters 2 & 3 as needed.
2. 1/31 Quick intro to C++ [PDF]
3. 2/5 Stacks, queues, deques, lists, sets; sequential and linked allocation. [PDF]
   Reading: Shaffer chapter 4 and sections 9.1-9.2.
4. 2/7 Graphs and matrices [PDF]
   Reading: Shaffer sections 11.1-11.3 and sections 12.2, 12.3
5. 2/12 Trees [PDF]
   Reading: Shaffer sections 5.1-5.3, chapter 6
6. 2/14 Binary Search Trees [PDF]
   Reading: Shaffer sections 5.4 Python Code
7. 2/19 AVL Trees [PDF]
   Reading: Shaffer section 13.2.1
8. 2/21 Splay trees [PDF]
   Reading: Shaffer 13.2.2
9. 2/26 B-Trees [PDF]
   Reading: Shaffer 10.4, 10.5; Samet appendix A.
10. 2/28 Heaps [PDF]
    Reading: Shaffer 5.5
11. 3/4 Minimum Spanning Trees [PDF]
    Reading: Shaffer 11.5
12. 3/6 Skip lists [PDF]
    Reading: Shaffer section 12.1 Python Code
13. 3/11: Midterm review
14. 3/13: Midterm
15. 3/25: Review of delete in B-trees and splay trees; introduction to geometric concepts.
16. 3/27: Midterm answers
17. 4/1: Quadtrees (PR, MX, Point) [PDF]
    Reading: Shaffer 13.3.1, Samet 1.4 through 1.4.3 (skipping 1.4.1.2)
18. 4/3: More Quadtrees (slides included above)
    Reading: Shaffer 13.3, 13.3.3
19. 4/8: kd-trees [PDF]
    Reading: Shaffer 13.3.1, Samet 1.5.1 through 1.5.1.3
20. 4/10: kd-trees, continued (variants, range searching, incremental NN) [PDF]
    Reading: Samet 4.1 through 4.1.3
21. 4/15: Range trees [PDF]
    
22. 4/17: Range trees cont + fractional cascading (slides included above)
    
23. 4/22: Interval trees, priority search trees [PDF]
    
24. 4/24: Segment trees (slides included above)
25. 4/29: Binary Space Partitions (board lecture, in-class handout)
26. 5/1: Winged Edge (board lecture, in-class handout)
27. 5/6: Grid Files, Hashing (board lecture)
    Reading: Samet 1.7.2.1 (Grid Files)
28. 5/8: Hashing, Suffix trees [PDF]
    Reading: Shaffer 9.4 (Hashing)]
29. 5/13: Suffix trees, review for the final (slides above)

Homeworks

1. Part 2 of the Programming Project, Due May 13.
2. Homework 4, Due April 17.
3. Homework 3, Due March 11.
4. Homework 2, Due March 4.
5. Part 1 of the Project, Due April 3. Makefile & Suggested Organization
6. Homework 1, Due Feb 26.

Administrative Information

Office hours: Tues 3:15-4:15 in AVW 3223 (Phone: 5-6713)
If you cannot attend office hours, email me about scheduling a different time.

Teaching assistants:

• Radu Dondera, rdondera AT cs.umd.edu, Office Hours: Monday 12:30-2:30 in AVW 1112 (TA room).
• Subhojit Basu, subhojit AT umd.edu OR subhojit.basu AT gmail.com, Office Hours: Wed 2-4pm in AVW 1305.

Class time: Tues/Thurs 2:00-3:15 in CSI 1121

Textbooks:

• Practical Introduction to Data Structures and Algorithm Analysis, C++ Edition, 2nd Edition by Clifford A. Shaffer. Prentice Hall, 2000. ISBN: 0-13-028-446-7.
• (optional) Foundations of Multidimensional and Metric Data Structures by Hanan Samet. Morgan Kaufmann, 2006. ISBN: 0-12-369-446-9.

Syllabus: An overview of course policies, topics, and grading is availible from this PDF.

Resources

• Dave Mount's Lecture Notes
• Brabec and Samet's Spatial Index Demos
• C++ Tutorial
• SGI STL Documentation

Fine Print

Excused absences. Students claiming an excused absence must apply in writing and furnish documentary support (such as from a health care professional who treated the student) for any assertion that the absence qualifies as an excused absence. The support should explicitly indicate the dates or times the student was incapacitated due to illness. Self-documentation of illness is not itself sufficient support to excuse the absence. Absences for religious observances must be submitted in writing to the instructor within two weeks of the start of the semester. The instructor is not under obligation to offer a substitute assignment or to give a student a make-up assessment unless the failure to perform was due to an excused absence. An excused absence for an individual typically does not translate into an extension for team deliverables on a project.

Academic accommodations. Any student eligible for and requesting reasonable academic accommodations due to a disability is requested to provide, to the instructor in office hours, a letter of accommodation from the Office of Disability Support Services (DSS) within the first two weeks of the semester.

Last modified 30 Aug 2007.