CSE373: Data Structures and Algorithms, Fall 2013

Course Info

Course Information and Policies

Lecture: Monday, Wednesday, Friday 2:30-3:20 EEB 105

Optional TA-led meetings: Tuesdays 3:30-4:30 EEB 037 and Thursdays 4:30-5:30 EEB 037
Optional TA-led meetings will be held most but not all weeks and will be announced in advance

Office Hours:
  Dan Grossman, Allen Center 574, Tuesdays 9-10AM + by appointment + try stopping by

  Sam Wilson, Allen Center 220, Mondays 11:30AM-12:30PM
  Nicholas Shahan, Allen Center 021 (basement), Tuesdays 1:30-2:30PM
  Sam Wilson, Allen Center 220, Wednesdays 11:30AM-12:30PM
  Conrad Nied, Allen Center 220, Thursdays 9:30-10:30AM
  Jasmine Singh, Allen Center 220, Thursdays 2:30-3:30PM
  Conrad Nied, Allen Center 218, Fridays 10:30-11:30AM
  Luyi Lu, Allen Center 218, Fridays 1:30-2:30PM

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.

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

Course staff:
  All staff: cse373-staff@cs.washington.edu (not @u...)
  Instructor: Dan Grossman, djg@cs.washington.edu, not @u...
  TA: Luyi Lu, luluyi@cs.washington.edu, not @u...
  TA: Conrad Nied, anied@cs.washington.edu, not @u...
  TA: Nicholas Shahan, nshahan@cs.washington.edu, not @u...
  TA: Jasmine Singh, jsingh4@cs.washington.edu, not @u...
  TA: Sam Wilson, samw11@cs.washington.edu, not @u...

Course Discussion Board (optional but encouraged)

Anonymous Feedback (goes only to the instructor)


Lecture Materials

Material in the future naturally subject to change in terms of coverage or schedule

  1. 1. Sep 25: Course Introduction; ADTs; Stacks and Queues   pptx   pdf1up   pdf6up
  2. 2. Sep 27: Math Review; Algorithm Analysis   pptx   pdf1up   pdf6up   xlsx
  3. 3. Sep 30-Oct 2: Asymptotic Analysis   pptx   pdf1up   pdf6up   xlsx
  4. 4. Oct 4-7: Dictionaries; Binary Search Trees   pptx   pdf1up   pdf6up
  5. 5. Oct 9-11: AVL Trees   pptx   pdf1up   pdf6up   xlsx
    Optional slides not discussed in class for AVL deletion:   pptx   pdf1up   pdf6up
  6. 6. Oct 11-14: Priority Queues   pptx   pdf1up   pdf6up
  7. 7. Oct 14-16: More Binary Heaps   pptx   pdf1up   pdf6up
  8. X. Oct 18: Midterm 1
  9. 8. Oct 16-21: Amortized Analysis   pptx   pdf1up   pdf6up
  10. 9. Oct 21-23: Disjoint Sets and Union-Find   pptx   pdf1up   pdf6up
  11. 10. Oct 23-25: Implementing Union-Find   pptx   pdf1up   pdf6up
  12. 11. Oct 25-28: Hash Tables   pptx   pdf1up   pdf6up
  13. 12. Oct 30: Hash Collisions   pptx   pdf1up   pdf6up   xslx   txt
  14. 13. Nov 1-4: Introduction to Graphs   pptx   pdf1up   pdf6up
  15. 14. Nov 6: Topological Sort and Graph Traversals   pptx   pdf1up   pdf6up
  16. 15. Nov 8: Shortest Paths   pptx   pdf1up   pdf6up
  17. 16. Nov 13: Software-Design Interlude -- Preserving Abstractions   pptx   pdf1up   pdf6up
  18. X. Nov 15: Midterm 2
  19. 17. Nov 18: Minimum Spanning Trees   pptx   pdf1up   pdf6up
  20. 18. Nov 20, 25: Comparison Sorting   pptx   pdf1up   pdf6up
  21. 19. Nov 22: Locality   pdf6up-with-ink-fromclass
  22. 20. Nov 27: Beyond Comparison Sorting   pptx   pdf1up   pdf6up
  23. 21. Dec 2, 4: Introduction to Multithreading and Fork-Join Parallelism   pptx   pdf1up   pdf6up
  24. 22. Dec 4, 6: Parallel Reductions, Maps, and Algorithm Analysis   pptx   pdf1up   pdf6up
  25. 23. Dec 6: Course Victory Lap   pptx   pdf1up   pdf6up
TA Sessions

Materials from TA Sessions

Optional sections that cover certain topics more in depth from the lectures and may or may not have postable items.

  1. 1. Oct 01: Eclipse, Java basics, and Sox   no pdf   JavaClassHierarchy.jpg
  2. 2. Oct 03: Proof by Induction   no materials
  3. 3. Oct 08 / 09: Asymptotic Analysis   pptx   pdf   java
  4. 4. Oct 10: AVL Trees   no materials
  5. 5. Oct 17: Midterm 1 Review   no materials
  6. 6. Oct 24: Pair Programming   no materials
  7. 7. Oct 31 / Nov 5: Union Find and Maze Builder   pptx   pdf
  8. 8. Nov 12: Java Collections   pptx   pdf
  9. 9. Nov 14: Midterm 2 Review   no materials
  10. 10. Nov 19: Abstraction   code:   zip
  11. 11. Nov 21: JUnit Tests   no materials
  12. 12. Dec 09: Final Review   notes:   docx   pdf

Homework Assignments

Electronic turn-in for programming assignments

Homework 0: on-line survey worth 0 points, "due" Friday September 29


Midterm 1: Friday October 18   information   unsolved   solved

Midterm 2: Friday November 15   information   unsolved   solved

Final exam: Tuesday December 10, 2:30-4:20PM   information   unsolved   solved


Software and Textbook Information

The programming assignments will use Java. We will use Java 7, the most recent version of the language. So if installing Java on your own machine, you can get Java 7 from http://jdk7.java.net/.

We strongly encourage 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. Some guidance on getting started with Eclipse is included in Homework 1.

The textbook is Data Structures and Algorithm Analysis in Java, Mark Allen Weiss, 3rd Edition, 2011, ISBN: 0132576279. Errata is here. Code from the book is here. We will also do our best to support the 2nd Edition, ISBN: 0321370139. Errata for the 2nd edition is here. Code for the 2nd edition is here. The textbook is also available for 4 hour loan at the Engineering library. The textbook often provides a second explanation for material covered in class.

A Java reference is also strongly recommended. While there are a variety of (more than) sufficient references, we recommend Core Java(TM), Volume I--Fundamentals 9th Edition, Cay S. Horstmann and Gary Cornell, 2002, ISBN: 0137081898.

For the material on parallelism in lectures 21 and 22 (and much more we did not have time for), see these notes written by the instructor. We covered the material in Sections 2.1-2.3, 3.1-3.3, 3.5 and 4.1-4.3 (except the last two paragraphs of 4.1.3).

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

Acknowledgments: Many of the materials posted here and used in the course have been shared and refined by many other instructors and TAs in previous offerings of CSE373, CSE332, and CSE326. This version of the course was particularly based on previous offerings by Ruth Anderson.

Valid CSS! Valid XHTML 1.1