CSE332: Data Abstractions, Summer 2010

Catalog Description: Covers abstract data types and structures including dictionaries, balanced trees, hash tables, priority queues, and graphs; sorting; asymptotic analysis; fundamental graph algorithms including graph search, shortest path, and minimum spanning trees; concurrency and synchronization; and parallelism.

Lecture: MWF 10:50-11:50 EEB 026
Section: Thursday 10:50-11:50 EEB 037

To reach the entire course staff, email cse332-staff followed by @ and then cs.washington.edu

Instructor: Tyler Robison, trobison followed by @ and then cs.washington.edu,
   Office hours: Wednesday 2:00-3:00 & by appointment, Room: CSE 212
TA: Sandra Fan, sbfan followed by @ and then cs.washington.edu
   Office hours: Thursday 12:00-1:00, Room: CSE 206

Lecture Slides & Notes

Approximate schedule for this quarter.

  1. June 21st: Introduction; Stacks & Queues: pptx pdf
  2. June 21st: Math review; Algorithm analysis: pptx pdf xlsx
  3. June 23rd: Algorithm analysis: pptx pdf xlsx
  4. June 25th: Priority Queues: pptx pdf
  5. June 25th, June 28th: Binary Heaps, continued: pptx pdf
  6. June 28th: Dictionaries & Binary Search Trees: pptx pdf
  7. June 30th: AVL Trees: pptx pdf
  8. July 2nd: Memory Hierarchy: pptx pdf
  9. July 2nd: B-Trees: pptx pdf
  10. July 2nd-July 7th: B-Trees, continued: pptx pdf
  11. July 9th-July 12th: Hashing: pptx pdf
  12. July 14th: Intro to Sorting: pptx pdf
  13. July 16th: Comparison Sorting: pptx pdf
  14. July 21st: Beyond Comparison Sorting: pptx pdf
  15. July 23rd: Introduction to Graphs: pptx pdf
  16. July 26th: Topological Sort: pptx pdf
  17. July 26th, July 28th: Shortest Paths: pptx pdf
  18. July 28th: Minimum Spanning Trees: pptx pdf
  19. July 30th: Introduction to Multithreading & ForkJoin Parallelism: pptx pdf
  20. August 2nd: Analysis of ForkJoin Parallel Programs: pptx pdf
  21. August 4th, August 6th: Parallel Prefix & Parallel Sorting: pptx pdf
  22. August 6th: Shared Memory Concurrency and Mutual Exclusion: pptx pdf
  23. August 9th: Programming with Locks and Critical Sections: pptx pdf
  24. August 9th: Readers/writer Locks and Condition Variables: pptx pdf
  25. August 11th, August 13th: Deadlocks and Additional Concurrency Issues: pptx pdf
  26. August 13th: Amortized Analysis: pptx pdf
  27. August 16th: A Few Words on NP (not on final): pptx pdf
  28. August 18th: Course Wrap-up: pptx pdf
  29. Notes:


    Dropbox for course project submissions

    Section Materials

    1. Week 1 - June 24
    2. Week 2 - July 1
    3. Week 3 - July 8
    4. Week 4 - July 15
    5. Week 5 - July 22
    6. Week 6 - July 29
    7. Week 7 - August 5
    8. Week 8 - August 12
    9. Week 9 - August 19

    Written Homeworks


    Course Information and Policies