The study of data structures studies the problem of preprocessing and organizing large data that mostly does not change over time such that we can answer queries on this data efficiently. You encounter these types of problems more often than you think: think of interactions with Google search (return a document among many that contains a query text), finding directions (return the shortest path between two points on a large map that mostly does not change), querying employee databases (return all employees that satisfy certain criteria, e.g. fall within some salary and age ranges), etc.
There have been many recent results in the area of data structures with many more problems remaining open. The course will provide an overview of existing data structuring results, present in-depth understanding of some of the specific results, teach specific data structuring techniques, and provide the students with an opportunity to tackle some of the open problems.
To get a flavor of the types of problems studied in this course, consider the following questions:
I am traveling during the first week of classes and the following Monday is a holiday. So the first "real" lecture will not be until after the add date, if you are considering registering for the course after attending the first couple of lectures. Therefore, if you are wondering if this course is for you, I suggest you email me as soon as possible.
During the first week (in lieu of the lectures), there will be a take-home assessment exam, which is posted on this webpage. I will use the results of the exam to determine students' level of preparation for the prerequisites and to adjust the course and topics approriately. Therefore, to give an accurate picture of students' knowlege, the exam should be individual effort.
This is a course on advanced algorithmic concepts, so you should be very comfortable with asymptotic notation, design and analysis of basic algorithms, and the algorithms taught in ICS 311 (most of the material from the CLRS textbook). Therefore, unless you received an 'A' in ICS 311 or equivalent, I suggest you talk to me before registering for the course.
There is no textbook for the material in this course because the material consists mostly of recent research results. The articles covering the material will be posted here.
The grade in the course will consist of the following components:
Content. The notes you write should cover all the material covered during the relevant lecture, plus real references to the papers containing the covered material. Your notes should be understandable to someone who has not been to the lecture. You should write in full sentences where appropriate; point form (like I write on the board) is often too terse to follow without a sound track (though occasionally it is appropriate). Use numbered sections, subsections, etc. to organize the material hierarchically and with meaningful titles. If you feel it is appropriate, use nested bullets to organize material hierarchically even deeper. Try to preserve the motivation, difficulties, solution ideas, failed attempts, and partial results obtained along the way in the actual lecture.
Format. Write your notes using LaTeX, with figures in Encapsulated PostScript (generated from xfig, ipe, Adobe Illustrator or whatever you want). Start from the Latex template, which sets the style.
Timing. Try to write the lecture notes for a class on the same day while the material is fresh in your mind and it will save you time. You should finish the first draft of your notes and send it to me by two days after the lecture. Then I'll either send you comments via email or we'll schedule a meeting to go over your write-up, I'll make suggestions, you'll make a second pass, and send it to me. I'll make the final pass, and post it on the webpage. The goal will be to get the notes out by one week after the corresponding class.
There will be 3-5 homeworks (once every 2-3 weeks) throughout the semester. Each homework will contain as many problems as there are students in class. You may collaborate with anyone on the homeworks, but you must write up your own solutions. You must write the names of everyone you discussed the solution with in your homework write-up. The homework must be typed up. It will be due at the beginning of the lecture on the day it is due and can be either submitted in person in lecture (preferred) or emailed to me. Homework solutions will be discussed in class on that day, therefore, no late homeworks will be accepted (even if you miss that lecture).
Homework grading. This semester I will be testing a new method of grading homeworks: on the day the homework is due, for each problem I will ask by show of hands who solved that problem. If you don't raise your hand, you will receive 0 pts for that problem. If you raise your hand, you must be ready to explain your solution on the board. Among those who raised their hand, I will randomly ask one of you to the board to explain your solution to the class. If the student called to the board stumbles or has an incorrect solution, I will randomly ask another person who raised their hand to help out. You will receive points to the problem based on the correctness and presentation of your solution. If you raised your hand and weren't called to explain the solution, you receive credit based on the write-up of your solution. I reserve the right to change the grading method to grading just the write-up for any of the homeworks.
Goal. Ideal outcome of the project at the end of the class is for you to obtain results that can be published at an algorithms conference. To receive full credit on the project, you do not have to achieve this goal (that's the nature of research), but that should be your goal. If you do not achieve publishable results, your write-up should describe the ideas and approaches you took to solve the problem.
Topic. The topic of your research project should be related to data structures. I will be available for brainstorming during office hours for possible topic of interest. You must be interested in the topic, but I must approve the topic, so check with me first.
Format. Here is a list of possible formats of the project. This list is not exhaustive, so if you have an interesting idea that you don't see on the list below, come discuss it with me.
Write-up. The project must be written up in a research paper format. It should be somewhere between 6 to 15 single-spaced pages with 1 inch margins. It should start with a title, author and a 1-2 paragraph abstract. The body of the write-up should consist of introduction, the body and the conclusions. The introduction should describe the problem you are addressing, present a brief literature review of related results on the topic, and a summary of your results. The body should describe your solution, teachnique/approach to solving it and results. If you haven't achieved significant results, you should still describe the techniques/approaches you have tried and why they didn't work. The conclusions should summarize what you have presented and present possible directions for future research, e.g. open problems that remain unsolved and/or possible approaches that you might have tried if you had more time. You are welcome to collaborate on the project with anyone (even outside the class), including me, but you should give credit to people you have collaborated with. This is the nature of research.
Presentation. At the end of the semester you should give a 30 minute presentation about your project.
The class will cover a subset of the following topics:
Specific topic covered will depend on the students' interest. The schedule below will be updated with the topics as they are covered.
| Class | Day | Date | Topic | Scribe Notes | Notes |
| 1 | Mon | Jan 11 | NO CLASS (Nodari is at a conference): Take-home assessment exam | Due 5:00pm on Thursday, Jan 14 (either by email or in POST 309C) |
|
| 2 | Wed | Jan 13 | NO CLASS (Nodari is at a conference): Finish the take-home assessment exam | ||
| -- | Mon | Jan 18 | HOLIDAY: Martin Luther King Day | ||
| 3 | Wed | Jan 20 | Review of the assessment exam | Kyle | |
| 4 | Mon | Jan 25 | Amortized Analysis: Aggregation, accounting, potential methods | Ben (Notes 01) | Reading: [CLRS, Ch. 17], [T] |
| 5 | Wed | Jan 27 | Self-adjusting Data Structures: Move-to-front | Ben (Notes 02) | Reading: [ST85a] |
| 6 | Mon | Feb 1 | Self-adjusting Data Structures: Splay Trees | Ben (Notes 03) | Reading: [ST85b] |
| 7 | Wed | Feb 3 | Splay tree access properties. Geometry of BSTs | Ben (Notes 04) | Reading: [ST85b], [Iac01], [Col00], [DHIKP09] |
| 8 | Mon | Feb 8 | Geometry of BSTs: offline equivalence | Kyle (Notes 05) | Reading: [DHIKP09] |
| 9 | Wed | Feb 10 | Geometry of BSTs: online equivalence | Maria | Reading: [DHIKP09] |
| -- | Mon | Feb 15 | HOLIDAY: Presidents' Day | ||
| 10 | Wed | Feb 17 | Online BSTs: Lower bounds | Maria | Reading: [DHIKP09], [W89] |
| 11 | Mon | Feb 22 | Guest Lecture: Riko Jacob External Memory Search Trees |
Ben (Notes 08) | Reading: [BF03] |
| 12 | Wed | Feb 24 | Predecessor search: van Emde Boas Trees | Ben | Reading: [CLRS, Ch 20], [V75], [V77] |
| 13 | Mon | Feb 29 | Predecessor search: van Emde Boas Trees (cont.) | Kyle (Notes 10) | Reading: [CLRS, Ch 20], [V75], [V77] |
| 14 | Wed | Mar 2 | Lowest Common Ancestors (LCA), Range Minima Queries (RMQ) |
Maria | Reading: [HT84], [BF00] |
| 15 | Mon | Mar 7 | Level Ancestors | Maria | Reading: [BF04] |
| 16 | Wed | Mar 9 | String Matching: Tries | Kyle (Notes 13) | Reading: [CKL06] |
| 17 | Mon | Mar 14 | Nodari is at a conference | ||
| 18 | Wed | Mar 16 | Nodari is at a conference | ||
| -- | Mon | Mar 21 | SPRING BREAK | ||
| -- | Wed | Mar 23 | SPRING BREAK | ||
| 19 | Mon | Mar 28 | Tries (cont.), Suffix Trees | Kyle (Notes 14) | Reading: [CKL06] |
| 20 | Wed | Mar 30 | Suffix Array construction, DC3 algorithm | Kyle (Notes 15) | Reading: [KSB06] |
| 21 | Mon | Apr 4 | Succinct data structures: binary trees, rank, select | Ben | Reading: [MR01], [P08] |
| 22 | Wed | Apr 6 | NO CLASS: Nodari is sick | ||
| 23 | Mon | Apr 11 | Persistent Data Structures | Kyle (Notes 17) | Reading: [DSST89] |
| 24 | Wed | Apr 13 | Fractional Cascading | Kyle (Notes 18) | Reading: [CG86a], [CG86b] |
| 25 | Mon | Apr 18 | Range Trees | Kyle | Reading: [BCKO08, Ch. 5] |
| 26 | Wed | Apr 20 | |||
| 27 | Mon | Apr 25 | Interval Trees, Priority Search Trees | Ben | Reading: [BCKO08, Ch. 10] |
| 28 | Wed | Apr 27 | Segment Trees | Kyle | Reading: [BCKO08, Ch. 10] |
| 29 | Mon | May 2 | Dictionaries, Hash Tables | Ben | |
| 30 | Wed | May 4 | Project presentations | project due |