UW CSE332, Spring 2012 (original) (raw)

CSE332: Data Abstractions, Spring 2012

Course Info

Course Information and Policies

• Policies on Collaboration and Academic Integrity
• Policies on Grading
• Programming Guidelines
• Written-Homework Guidelines
• Gradebook

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)

Lectures

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

Sections

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

Assignments

Projects and Homework Assignments

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

Dropbox for project turn-in

• Project 1: Sound Blaster Phase A due April 4, 11PM Phase B due April 9, 11PM
• Project 2: Shake-n-Bacon Phase A due April 25, 11PM Phase B due May 8, 11PM
• Project 3: Where are the People? Code due May 29, 11PM Write-up due May 31, 11PM
• Homework 1 due April 6, beginning of class <homework1.pdf>
• Homework 2 due April 13, beginning of class <homework2.pdf>
• Homework 3 due April 20, beginning of class <homework3.pdf>
• Homework 4 due May 4, beginning of class <homework4.pdf>
• Homework 5 due May 11, beginning of class <homework5.pdf>
• Homework 6 due May 18, beginning of class <homework6.pdf>
• Homework 7 due May 25, beginning of class <homework7.pdf>
• Homework 8 due June 1, beginning of class <homework8.pdf>

Software

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.

Books+

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.

• The Data-Structure Canon, George V. Neville-Neil
• Bubble Sort: An Archaeological Algorithmic Analysis, Owen Astrachan
• Wikipedia: Comparison Sort (follow links to different sorting algorithms to see animations of the algorithms in action)
• You Don't Know Jack About Shared Variables or Memory Models, Hans-J. Boehm, Sarita V. Adve