|
|
||||
|
|
|
|
|
|
Data Structures
|
|
getting
started with WebCT and configuring
your browser (Linux is fine); be sure to allow popups
Welcome! Virtually any computer program - no matter how interesting or boring - has to store data carefully, to make it efficient to retrieve, summarize, search, or change the data as the program requires. This course covers some of the most commonly used data structures and their methods. You'll learn not only how to use these data structures, but also what algorithms they use internally, so that you can figure out when to use them and how to design new data structures. The course will also build up your skills in object-oriented design and basic analysis of algorithms. In short, this is the course where you turn into a real programmer.
Course catalog entry: This course covers the design and implementation of data structures including arrays, stacks, queues, linked lists, binary trees, heaps, balanced trees (e.g. 2-3 trees, AVL-trees) and graphs. Other topics include sorting, hashing, memory allocation, and garbage collection. Course work involves both written homework and Java programming assignments. Prereq: 600.107 (preferred) or 600.109 required; intermediate programming (600.120 or equivalent) highly recommended.
| Lectures: | MW 4-5:15 pm in Shaffer 100. Note that class lasts the full 75 minutes, so we get 2 x 75 instead of 3 x 50 minutes per week. |
| Web page: | http://cs.jhu.edu/~jason/226 - course site http://webct.jhu.edu - for online warmups etc. |
| Mailing lists: |  - announcements, free discussion - questions for CAs/TA/prof - report problems with the mailing list |
| Prof: | Jason
Eisner -  (or ) - office hours Mon+Wed after class in NEB 324A |
TA: CAs: | We have help available in the CS undergrad lab (NEB
225/227) at Tue 8-10 (Kim), Thu 4-6 (Sam), Fri 12:30-2:30 (Ray). Sam Small -  (or ) Raymond Buse -  (or )Kim Jordan -  (or ) |
| Textbook: |
The purchase links below help JHU's grad students. Required: Goodrich & Tamassia, Data Structures, 3rd edition - ISBN 0471469831. amazon, barnes&noble, textbookx, ebay. Also fine to use the 2nd edition if you can get it cheaper (differences) - ISBN 0471383678, amazon, barnes&noble, textbookx, ebay Recommended: Arnold, Gosling & Holmes, The Java Programming Language, 3rd edition - ISBN 0201704331, amazon, barnes&noble, textbookx, ebay Recommended: Flanagan, Java in a Nutshell, 4th edition - ISBN 0596002831 amazon, barnes&noble, textbookx, ebay |
| Policies: |
Academic integrity: read this!
It says your work must be your own. The only exception for this course (so far) is that you may collaborate on the online warmups. Intellectual engagement: much encouraged Grading: 10% online warmups and class participation (graded on effort only), 45% programming assignments, 15% midterm, 30% final. Submission procedure: instructions, upload page Lateness policy: 1 day late = 10% off, 2 days late = 20% off, etc., up to a maximum of 5 days. For example, if the homework is due 4pm Friday, then 3pm Saturday would be 1 day late and 5pm Saturday would be 2 days late. (Of course, if you have a non-academic emergency, talk to academic advising to get a Dean's note.) |
| Dates | Topics | Readings | Resources | Homework |
| Mon 1/26, Wed 1/28 | Why data structures are cool. Review of Java and object-oriented design. Designing a toilet. | Make sure you know Java! Chapters 1-2 of the textbook, or if you really want to know your stuff, chapters 1-4 of Java in a Nutshell. | Download or browse the Toilet code developed in class. | Fill out the online questionnaire. Homework 1 due Fri 2/6. |
| Mon 2/2 | The recursive Russian Doll class. | The Russian Doll code. | Homework 2 due Fri 2/13. | |
| Wed 2/4, Mon 2/9 | Asymptotic complexity. Sequence implementations: arrays, partial arrays, linked lists, doubly linked lists. Sequence interfaces: stacks, queues, deques. Example use of stacks: parenthesis matching. | Chapters 3-4 of the textbook. |
Slides by Noah Smith on asymptotic
complexity and big-Oh notation (Powerpoint, PDF). A finished version of the MatchParen class developed in lecture. |
Warmup 1 - complexity. Homework 3 due Fri 2/20. |
| Wed 2/11, Mon 2/16 | Vectors, lists, sequences. Ways to reverse a sequence. Extensible arrays and amortized analysis. Iterators. | Chapter 5 of the textbook. | Warmup 2 - vectors. Homework 4 due Fri 2/27. | |
| Wed 2/18, Mon 2/23 | Trees. What they are, what they can represent, how to store them. Using a tree to quickly update the sum of a set of numbers. Various iterators over some or all nodes of a tree. | Chapter 6 of the textbook. | Sample tree iterator code developed in class. | Warmup 3 - trees. Homework 5 due Fri 3/5. |
| Wed 2/25, Mon 3/1 ... also Wed 3/10 |
Priority queues and their
implementation as heaps. Implementing insert(),
removeMin(), and a fast heap constructor. Runtime
analysis. The interfaces Comparable and
Comparator. Heapsort. Finding just the k smallest elements via insertion
sort and heapsort.
|
Chapter 7 of the textbook. | A nice animation of heapsort (near bottom of page). | Warmup 4 - heaps. Homework 6 due Tue 3/23 at 4pm (just after spring break). |
| Wed 3/3, Mon 3/8 | Dictionaries and their implementation as hash tables. | Chapter 8 of the textbook (except for the material on skip lists). | Hash table animation (near bottom of page) | Warmup 5 - dictionaries. Homework 7 due Fri 4/2. |
| Mon 3/15, Wed 3/17 |
No class (spring break). Note that we do have class as usual on 3/10 and 3/22: look carefully at the schedule (two rows away). |
[A good time to study for the midterm, if you're not having a better time on the beach.] | [You could finish HW6 over break, if you didn't manage to get it done beforehand. Or get a headstart on HW7, if you're that kind of person.] | |
| Wed 3/24 | Midterm exam in class. (Midterm review session by TA probably on the evening of Mon 3/22.) | The midterm will cover chapters 1-7 of the textbook. Note: We won't penalize minor Java coding errors, but you should be relatively comfortable with Java, and able to explain how you would use Java classes and interfaces to design a data structure. | Practice exams will be made available. | Try the practice midterm before the review session ... Read the official solutions after the exam ... |
| Mon 3/22, Mon 3/29, Wed 3/31, Mon 4/5 | Search trees. | Chapter 9 of the textbook, plus the skip list material from chapter 8. |
Algorithm animations: Basic binary search tree AVL tree Red-black tree; another |
Warmup 6 - search trees (due Mon 3/29). Homework 8 (final election system) due Fri 4/9. |
| Wed 4/7, Mon 4/12 | (More) sorting algorithms. | Chapter 10 of the textbook. | Sorting animations (with Java source code!) | Warmup 7 - sorting. Homework 9 (paper assignment) on search-'n'-sort due Fri 4/16. |
| Wed 4/14, Mon 4/19 | Graphs and graph algorithms. | Chapter 12 of the textbook. |
breadth-first
and depth-first
search animations; also on trees Dijkstra's algorithm animation (near bottom of page) |
Warmup 8 - graphs. Homework 10 due Sun 5/2. |
| Wed 4/21, Mon 4/26 | Text processing. | Chapter 11 of the textbook. | Warmup 9 - text processing. | |
| Wed 4/28 | Design examples of real systems ... | |||
| Week of Thu 5/6 - Thu 5/13 | Final exam will be Sat 8 May from 2-5pm in Shaffer 101. (Review session Wednesday 5 May.) | review topics | Practice exams will be made available. |