CSE332: Data Abstractions, Spring 2012

Course Info

Course Information and Policies

Lecture: Monday, Wednesday, Friday 2:30-3:20PM EEB 037
Section AA: Thursday 1:30-2:20, BNS 203
Section AB: Thursday 2:30-3:20, BNS 203

Office Hours:
  Dan Grossman, Allen Center 574, Fridays 10-11AM + by appointment + try coming by (please do visit!)
  TA: Tyler Robison, Wednesdays and Thursdays 3:30-4:30PM, CSE006 (basement lab)
  TA: Stanley Wang, Tuesdays 2:30-4:30PM, CSE006 (basement lab)

Contact Info

Contact Information

Course Email List (mandatory): You should receive email sent to the course mailing list regularly (roughly at least once a day). Any important announcements will be sent to this list.

Course staff:
  All staff: cse332-staff@cs.washington.edu
  Instructor: Dan Grossman, djg and then at and then cs.washington.edu
  TA: Tyler Robison, trobison and then at and then cs.washington.edu
  TA: Stanley Wang, snwang and then at and then cs.washington.edu

Email sent to cse332-staff@cs.washington.edu will reach the instructor and all the TAs. For questions multiple staff members can answer, we encourage you to use this email so that you get a quicker reply and the whole staff is aware of points of confusion.

Course Discussion Board (optional)

Anonymous Feedback (goes only to the instructor)


Lecture Materials

  1. 1. Mar 26: Introduction; ADTs; Stacks/Queues   pptx   pdf1up   pdf6up
  2. 2. Mar 28: Math Review; Algorithm Analysis   pptx   pdf1up   pdf6up   xlsx
  3. 3. Mar 30: Asymptotic Analysis   pptx   pdf1up   pdf6up   xlsx
  4. 4. Apr 2: Priority Queues   pptx   pdf1up   pdf6up
  5. 5. Apr 4: More Binary Heaps   pptx   pdf1up   pdf6up
  6. 6. Apr 6: Dictionaries; Binary Search Trees   pptx   pdf1up   pdf6up
  7. 7. Apr 9: AVL Trees   pptx   pdf1up   pdf6up   xlsx
  8. 8. Apr 11: AVL Delete; Memory Hierarchy   pptx   pdf1up   pdf6up
  9. 9. Apr 13: B Trees   pptx   pdf1up   pdf6up   xlsx
  10. 10. Apr 16: More B Trees; Hashing   pptx   pdf1up   pdf6up
  11. 11. Apr 18: More Hashing   pptx   pdf1up   pdf6up   xlsx   txt
  12. 12. Apr 20: Introduction to Sorting   pptx   pdf1up   pdf6up
  13. 13. Apr 23: Comparison Sorting   pptx   pdf1up   pdf6up
  14. 14. Apr 25: Beyond Comparison Sorting   pptx   pdf1up   pdf6up
  15. X. Apr 27: Midterm
  16. 15. Apr 30: Introduction to Graphs   pptx   pdf1up   pdf6up
  17. 16. May 2: Topological Sort / Graph Traversals   pptx   pdf1up   pdf6up
  18. 17. May 4: Shortest Paths   pptx   pdf1up   pdf6up
  19. 18. May 7: Introduction to Multithreading & Fork-Join Parallelism   pptx   pdf1up   pdf6up
  20. X. May 9 (continue previous lecture)
  21. 19. May 11: Analysis of Fork-Join Parallel Programs   pptx   pdf1up   pdf6up
  22. 20. May 14: Parallel Prefix, Pack, and Sorting   pptx   pdf1up   pdf6up
  23. 21. May 16: Shared-Memory Concurrency & Mutual Exclusion   pptx   pdf1up   pdf6up
  24. 22. May 18: Programming with Locks and Critical Sections   pptx   pdf1up   pdf6up
  25. 23. May 21: Remaining Topics in Shared-Memory Concurrency   pptx   pdf1up   pdf6up
  26. X. May 23 (continue previous lecture)
  27. 24. May 25 Minimum Spanning Trees (started in section on May 24)   pptx   pdf1up   pdf6up
  28. 24.5. May 30 Interlude on Intractability   pptx   pdf1up   pdf6up
  29. 25. May 30 Amortized Analysis   pptx   pdf1up   pdf6up
  30. 26. Jun 1: Course Victory Lap   pptx   pdf1up   pdf6up

Section Materials

  1. 1. Mar 29: Introductions, Eclipse and Java generics
  2. 2. Apr 5: JUnit and O()
  3. 3. Apr 12: Function Objects, Iterators and AVL trees
  4. 4. Apr 19: Timing and B-trees
  5. 5. Apr 26: Hashing and midterm review
  6. 6. May 3: Topological sort and graph traversals
  7. 7. May 10: ForkJoin Framework
  8. 8. May 17: Concurrency
  9. 9. May 24: MST
  10. 10. May 31: Final-exam review

Projects and Homework Assignments

Homework 0: on-line survey worth 0 points, "due" Thursday March 29

Dropbox for project turn-in


Midterm: Friday, April 27, in class,   unsolved   solved   more information

Final: Tuesday, June 5, 2:30-4:20PM EEB037   unsolved   solved   more information


Software Installation and Use

As needed, section will cover basic orientation to the software we need.

We will have 3 programming projects using Java. The third project will require Java 7, the most recent version of the language. So if installing Java on your own machine (rather than using the department lab machines), then you may as well get Java 7 now from http://jdk7.java.net/.

The course staff will assume you are using the Eclipse IDE, though we will not require this. You can download Eclipse for your own machine from http://eclipse.org/downloads; it is also installed on all the lab machines.

Java's support for generics will be very useful in our projects, but its support for generic arrays requires a few common workarounds. Read this to-the-point description.

Project 3 will use Java's Fork-Join Framework as described in this introductory document.


Textbooks and Other Resources

The textbook is Data Structures and Algorithm Analysis in Java, Mark Allen Weiss, 3rd Edition, 2011, ISBN: 0132576279. We will also do our best to support the 2nd Edition, ISBN: 0321370139. The textbook often provides a second explanation for material covered in class and we will likely assign some homework problems from it.

For the parallelism and concurrency material, these reading notes (written by the instructor) cover the same material: A Sophomoric Introduction to Shared-Memory Parallelism and Concurrency (pdf)

A Java reference is also strongly recommended. While there are a variety of sufficient references, we recommend Core Java(TM), Volume I--Fundamentals 8th Edition, Cay S. Horstmann and Gary Cornell, 2007, ISBN: 0132354764. Note this book is also recommended for CSE331.

Here are some interesting, usful, and accessible articles related to the course material. These are optional reading that you may find helpful and enriching.

Valid CSS! Valid XHTML 1.1