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++).
- 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.
% 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:
- Projects that are between 24 and 48 hours late will be discounted 20% (instead of 30%)
- Projects that are between 48 and 72 hours late will be discounted 40% (as in the syllabus)
- Homework must be picked up either in class the day it's returned or
during my office hours (or email another time).
- 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.
- 1/29 Introduction, review of big-O, data structuring principles
Reading: Shaffer chapter 1, review chapters 2 & 3 as needed.
- 1/31 Quick intro to C++
- 2/5 Stacks, queues, deques, lists, sets; sequential and linked allocation.
Reading: Shaffer chapter 4 and sections 9.1-9.2.
- 2/7 Graphs and matrices [PDF]
Reading: Shaffer sections 11.1-11.3 and sections 12.2, 12.3
- 2/12 Trees [PDF]
Reading: Shaffer sections 5.1-5.3, chapter 6
- 2/14 Binary Search Trees [PDF]
Reading: Shaffer sections 5.4
- 2/19 AVL Trees [PDF]
Reading: Shaffer section 13.2.1
- 2/21 Splay trees [PDF]
Reading: Shaffer 13.2.2
- 2/26 B-Trees [PDF]
Reading: Shaffer 10.4, 10.5; Samet appendix A.
- 2/28 Heaps [PDF]
Reading: Shaffer 5.5
- 3/4 Minimum Spanning Trees [PDF]
Reading: Shaffer 11.5
- 3/6 Skip lists [PDF]
Reading: Shaffer section 12.1
- 3/11: Midterm review
- 3/13: Midterm
- 3/25: Review of delete in B-trees and splay trees; introduction to
- 3/27: Midterm answers
- 4/1: Quadtrees (PR, MX, Point) [PDF]
Reading: Shaffer 13.3.1, Samet 1.4 through 1.4.3 (skipping 184.108.40.206)
- 4/3: More Quadtrees (slides included above)
Reading: Shaffer 13.3, 13.3.3
- 4/8: kd-trees [PDF]
Reading: Shaffer 13.3.1, Samet 1.5.1 through 220.127.116.11
- 4/10: kd-trees, continued (variants, range searching, incremental NN)
Reading: Samet 4.1 through 4.1.3
- 4/15: Range trees [PDF]
- 4/17: Range trees cont + fractional cascading (slides included above)
- 4/22: Interval trees, priority search trees
- 4/24: Segment trees (slides included above)
- 4/29: Binary Space Partitions (board lecture, in-class handout)
- 5/1: Winged Edge (board lecture, in-class handout)
- 5/6: Grid Files, Hashing (board lecture)
Reading: Samet 18.104.22.168 (Grid Files)
- 5/8: Hashing, Suffix trees
Reading: Shaffer 9.4 (Hashing)]
- 5/13: Suffix trees, review for the final (slides above)
- Part 2 of the Programming Project, Due May 13.
- Homework 4, Due April 17.
- Homework 3, Due March 11.
- Homework 2, Due March 4.
- Part 1 of the Project, Due April 3.
Makefile & Suggested Organization
- Homework 1, Due Feb 26.
Professor: Carl Kingsford -
Biomolecular Sciences Building (#296) - 301-405-7395 - carlk AT
Office hours: Tues 3:15-4:15 in AVW 3223
If you cannot attend office hours, email me about
scheduling a different time.
- 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
- Practical Introduction to Data Structures and Algorithm Analysis, C++
Edition, 2nd Edition by Clifford A. Shaffer. Prentice Hall, 2000. ISBN:
- (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
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
Last modified 30 Aug 2007.