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

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
Notes:
• Notes on Generic Arrays in Java
• Notes on ForkJoin Framework
• Dan Grossman's excellent notes on parallelism and concurrency
  • The notes are, as of yet, incomplete, but Dan will be updating them and adding to them over the course of time
  • These notes are in draft form, and Dan said he'd be happy to get your feedback on them; you can find his contact information here

Projects

Dropbox for course project submissions
• Project 1: Sound Blaster! due June 30th at 11pm
• Project 2: Shake-n-Bacon due in 2 parts: Part A due July 14th, part B due July 26th
• Project 3: Where are the People? due in 2 parts: Code due August 16th, Writeup due August 18th

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

• Homework 1 due July 2nd
• Homework 2 due July 9th
• Homework 3 due July 16th
• Homework 4 due July 23rd
• Homework 5 due July 30th
• Homework 6 due August 6th
• Homework 7 due August 13th

Exams

• Midterm: July 19th in class
• Final exam: August 20th in class

Course Information and Policies

• Give Anonymous Feedback: Thoughts & suggestions welcome
• Course Gradebook
• Message Board: Ask questions and discuss
• Course mailing list: cse332a_su10 at u.washington.edu
• Textbooks
  • The course's primary 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
  • An optional book for the course is Core Java(TM), Volume I--Fundamentals 8th Edition, Cay S. Horstmann and Gary Cornell, Prentice Hall: 2007, ISBN: 0-132-35476-4, and is useful as a Java programming reference.
• Course Policies
  • Policy on Collaboration and Academic Integrity
  • Policy on Grading
  • Programming Guidelines
  • Written-Homework Guidelines