*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 2:30-3:20 EEB 037

Section AA: Thursday 1:30-2:20 EEB 042

Section AB: Thursday 2:30-3:20 EEB 042

Policy on Collaboration and Academic Integrity

Policy on Grading

Programming Guidelines

Written-Homework Guidelines

Message Board (optional)

Give Anonymous Feedback

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

Instructor: Dan Grossman, djg followed by @ and then cs.washington.edu,

Office hours: Tuesday 12:30-1:30 and by appointment, CSE556 *(please do come by!)*

TA: Tyler Robison, trobison followed by @ and then cs.washington.edu

Office hours: Thursday 3:30-4:30, CSE216

TA: Brent Sandona, sandona1 followed by @ and then cs.washington.edu

Office hours: Wednesday 1:00-2:00, CSE216

- 1. Mar 29: Introduction; Stacks & Queues pdf pptx
- 2. Mar 31: Math Review; Algorithm Analysis pdf pptx xlsx
- 3. Apr 2: Asymptotic Analysis pdf pptx xlsx
- 4. April 5: Priority Queues pdf pptx
- 5. April 7: More Binary Heaps pdf pptx
- 6. April 9: Dictionaries; Binary Search Trees pdf pptx
- 7. April 12: AVL Trees pdf pptx xlsx
- 8. April 14: AVL Delete; Memory Hierarchy pdf pptx
- 9. April 16: B Trees pdf pptx xlsx
- 10. April 19: More B Trees; Hashing pdf pptx java
- 11. April 21: More Hashing pdf pptx xlsx
- 12. April 23: (Finish Hashing); Introduction to Sorting pdf pptx
- 13. April 26: Comparison Sorting pdf pptx
- 14. April 28: Beyond Comparison Sorting pdf pptx
- X. April 30: Midterm
- 15. May 3: Introduction to Graphs pdf pptx
- 16. May 5: Topological Sort; Graph Traversals pdf pptx
- 17. May 7: Shortest Paths pdf pptx
- 18. May 10: Introduction to Multithreading and Fork-Join Parallelism pdf pptx
- 19. May 12: Analysis of Fork-Join Parallel Programs pdf pptx
- 20. May 14: Parallel Prefix and Parallel Sorting pdf pptx
- 21. May 17: Amortized Analysis pdf pptx
- 22. May 19: Shared-Memory Concurrency and Mutual Exclusion pdf pptx
- 23. May 21: Programming with Locks and Critical Sections pdf pptx
- 24. May 24: Remaining Topics in Shared-Memory Concurrency pdf pptx
- 25. May 26: (Finish Concurrency); Some Project 3 Notes pdf pptx
- 26. May 28: Minimum Spanning Trees pdf pptx
- 27. June 2: A Few Words on NP (*) pdf pptx
- 28. June 4: Course Wrap-Up / Victory Lap pdf pptx

(*) NP does *not* belong in CSE332. It is a primary topic in
CSE312. However, students taking CSE332 in Spring 2010 have all taken
CSE321, which means they will not take CSE312.

- Project 1: Sound Blaster Phase A due April 7, 11PM Phase B due April 12, 11PM
- Project 2: Shake-n-Bacon Phase A due April 28, 11PM Phase B due May 10, 11PM
- Project 3: Where are the People? Code due June 1, 11PM Write-up due June 3, 11PM

- Homework 1 due April 9, beginning of class
- Homework 2 due April 16, beginning of class
- Homework 3 due April 23, beginning of class
- Homework 4 due May 7, beginning of class
- Homework 5 due May 14, beginning of class
- Homework 6 due May 21, beginning of class
- Homework 7 due May 28, beginning of class
- Homework 8 due June 4, beginning of class

Exam Information

Midterm: Friday, April 30, in class
exam unsolved
exam solved

Final: **Tuesday**, June 8, 2:30-4:20, EEB037
exam unsolved
exam solved

The textbook is
*Data Structures and Algorithm Analysis in Java 2nd Edition*,
Mark Allen Weiss, Addison Wesley: 2007, ISBN: 0-321-37013-9.

Errors in the textbook

The textbook often provides a second explanation for material covered in class and we will likely assign some homework problems from it.

The book
*Core Java(TM), Volume I--Fundamentals 8th Edition*, Cay S. Horstmann and Gary Cornell, Prentice Hall: 2007, ISBN: 0-132-35476-4,
is recommended as a Java programming reference. Note this book is also recommended for
CSE331.

Several topics in the course, particularly the entirety of parallelism and concurrency, are not covered by the textbook. Therefore, we have prepared the following supplemental notes:

Course Email List (mandatory)

Homework 0, "due" Thursday April 1, 0 points

*Thoroughly read the course policies and refer back to them as necessary*

Approximately 75% of CSE332 evolved from CSE326, which was taught well by many instructors over many years. CSE332 borrowed heavily from these courses for lectures, homeworks, and projects. The parallelism and concurrency parts of the course are new, developed by Dan Grossman with excellent feedback from Tyler Robison and Brent Sandona. Dan credits Guy Blelloch and Charles Leiserson for many of the ideas/topics related to teaching fork-join parallelism and doing so before concurrency. While developing the course, Dan had conversations with many helpful colleagues, notably Ruth Anderson, James Fogarty, Hal Perkins, and Larry Snyder.