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 objectoriented 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. 23 trees, AVLtrees) 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 45: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 810 (Kim), Thu 46 (Sam), Fri 12:302: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 nonacademic 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 objectoriented design. Designing a toilet.  Make sure you know Java! Chapters 12 of the textbook, or if you really want to know your stuff, chapters 14 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 34 of the textbook. 
Slides by Noah Smith on asymptotic
complexity and bigOh 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 17 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 Redblack 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. 
breadthfirst
and depthfirst
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 25pm in Shaffer 101. (Review session Wednesday 5 May.)  review topics  Practice exams will be made available. 