CSE373: Data Structures and Algorithms, Winter 2014

Course Info

Course Information and Policies

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

Optional TA-led meetings: Tuesdays 4:30-5:30 and Thursdays 4:30-5:20 in Bagley 154
Optional TA-led meetings will be held most but not all weeks and will be announced in advance

Office Hours:
  Aaron Bauer, Allen Center 220, Thursdays 10:30-11:30AM + by appointment + try stopping by at my shared office (Allen Center 324)

  Nicholas Shahan, Allen Center 220, Mondays 11:30AM-12:30PM
  Shuo Wang, Allen Center 220, Mondays 1:30PM-2:30PM
  Yuanwei Liu, Allen Center 220, Tuesdays 9:30AM-10:30AM
  Rama Gokhale, Allen Center 220, Tuesdays 12:30PM-1:30PM
  Luyi Lu, Allen Center 218, Thursdays 11:30AM-12:30PM
  Yunyi Song, Allen Center 220, Thursdays 3:30PM-4:30PM
  Iris Jianghong Shi, Allen Center 220, Fridays 4:30PM-5: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: Aaron Bauer, awb@cs.washington.edu, not @u...
  TA: Luyi Lu, luluyi@cs.washington.edu, not @u...
  TA: Iris Jianghong Shi, jhshi@cs.washington.edu, not @u...
  TA: Nicholas Shahan, nshahan@cs.washington.edu, not @u...
  TA: Yuanwei Liu, yuanwl@cs.washington.edu, not @u...
  TA: Rama Gokhale, ramag@cs.washington.edu, not @u...
  TA: Shuo Wang, wangs5@cs.washington.edu, not @u...
  TA: Yunyi Song, bessieyy@cs.washington.edu, not @u...

Course Discussion Board (optional but encouraged)

Anonymous Feedback (goes only to the instructor)



View the course calendar here.

Lecture Materials

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

  1. Jan 6: Course Introduction; ADTs; Stacks and Queues (Weiss 3.6, 3.7)   pptx   pdf
  2. Jan 8: Math Review; Algorithm Analysis (Weiss 1.2, 2.1-2.3)   pptx   pdf   xlsx
  3. Jan 10: More Induction   pptx   pdf
  4. Jan 10: Asymptotic Analysis (Weiss 2.1-2.4)   pptx   pdf
  5. Jan 13: Asymptotic Analysis cont. (Weiss 2.1-2.4)   pptx   pdf
  6. Jan 15: Dictionaries; Binary Search Trees (Weiss 4.8; 4.1-4.3)   pptx   pdf
  7. Jan 17: Binary Search Trees continued (Weiss 4.1-4.3)   pptx   pdf
  8. Jan 22: AVL Trees (Weiss 4.4)   pptx   pdf
  9. Jan 24: Priority Queues (Weiss 6.1-6.4)   pptx   pdf
  10. Jan 27: Binary Heaps continued (Weiss 6.1-6.4)   pptx   pdf
  11. Jan 28: Midterm 1
  12. Jan 31: Amortized Analysis; Disjoint Sets (Weiss 8.1-8.2, 8.7)   pptx   pdf
  13. Feb 3: Union Find (Weiss 8.3-8.6)   pptx   pdf
  14. Feb 5: Hash Tables (Weiss 5.1-5.6)   pptx   pdf
  15. Feb 7: Hash Collisions (Weiss 5.1-5.6)   pptx   pdf   xlsx   txt
  16. Feb 10: Introduction to Graphs (Weiss 9.1)   pptx   pdf
  17. Feb 12: Topological Sort and Graph Traversals (Weiss 9.2, 9.3.1, 9.6)   pptx   pdf
  18. Feb 14: Dijkstra's Algorithm (Weiss 9.3)   pptx   pdf
  19. Feb 19: More Dijkstra's and Minimum Spanning Trees (Weiss 9.5)   pptx   pdf
  20. Feb 21: Network Flow, NP-Completeness, and More (Weiss 9.4, 9.7, 10.3, 10.4)   pptx   pdf
  21. Feb 24: Interlude: Preserving Abstractions   pptx   pdf
  22. Feb 26: Midterm 2
  23. Feb 28: Comparison Sorting (Weiss 7.1-7.8)   pptx   pdf
  24. March 3: More Comparison Sorting (Weiss 7.1-7.8)   pptx   pdf   visualizations
  25. March 5: Beyond Comparison Sorting (Weiss 7.9, 7.11-7.12)   pptx   pdf
  26. March 7: Interlude: Programming Languages   pptx   pdf
  27. March 10: Memory Hierarchy and Data Locality   pptx   pdf
  28. March 12: Multithreading and Fork-Join Parallelism (Sections 2, 3 of these notes)   pptx   pdf
  29. March 14: Parallel Reductions, Maps, and Algorithm Analysis (Sections 3, 4 of these notes)   pptx   pdf
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. Jan 14: Eclipse, Java basics, and Sox   pptx   pdf
  2. Jan 16: Proof by Induction (and other math)   pptx   pdf
  3. Jan 23: AVL Trees   pptx   pdf
  4. Jan 28: Midterm Review
  5. Feb 13: Union-Find and Homework 4   pptx   pdf
  6. Feb 18: JUnit   pptx   pdf   code
  7. Feb 25: Midterm Review
  8. Feb 27: Java Collections   pptx   pdf
  9. March 11: Final Exam Review

Homework Assignments

Electronic turn-in for programming assignments

Homework 0: on-line survey worth 0 points, "due" Friday January 10


Midterm 1: Wednesday January 29   information   unsolved   solved

Midterm 2: Wednesday February 26   information   unsolved   solved

Final exam: Tuesday March 18, 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.

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 and Dan Grossman.

Valid CSS! Valid XHTML 1.1