CSE373 Summer 2017

Data Structures and Algorithms

Course Info

Course Information and Policies

Lectures:  Monday, Wednesday, Friday 10:50-11:50 THO 101
Sections:  Thursday 10:50-11:50 THO 101,  or
Thursday 12:00-1:00 JHN 075
I encourage students to take notes on paper instead of electronic devices. If you intend to use a phone or laptop, please sit in the back of the lecture room so you don’t distract fellow students.

Office Hours: hosted in the 3rd floor breakout in CSE (whiteboard area by the staircase)

Lilian's additional office hours in a more private setting: Monday & Tuesday 1:30-2:00pm and by appointment in CSE 220

Contact Info

Contact Information

Question on homework or course material? Find or start a post on Piazza!

When posting to the class, leave out any code or parts of a solution to the homework (even if it’s incomplete). For private questions (e.g. grades, code- or solution-specific questions, etc.), post to the instructors only. If you're feeling shy about posting something to the class, you can always post anonymously.

Because Piazza is highly catered to getting you help fast and efficiently from classmates, TAs, and the instructor, you’ll get a faster response there than if you email any of us individually. This is also true for private posts, as both TAs and instructors can see them.


For Lilian's eyes only? Email me with "[CSE 373]" at the beginning of the subject line. I will check my email at least once a day, so you can expect a response to instructor-only emails (addressed to ldegreef [at] cs.washington.edu) within 24 hours.

Course Email List: You should receive email sent to the course mailing list regularly. Any important announcements will be sent to this list. More info

Anonymous Feedback (goes only to the instructor)


Lecture Materials

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

  1. June 19: Course Introduction, ADTs, Stacks and Queues
              [ pptx ]   [ pdf ]  [ Annotated pdf ]
  2. June 21: Finish up Queues, Start Asymptotic Analysis
              [ pptx ]   [ pdf ]   [ Annotated pdf ]
  3. June 23: Asymptotic Analysis: Math Review, Induction, Recusive Functions (Reading: Weiss Ch2)
              [ pptx ]   [ pdf ]   [ Annotated pdf ]   [ Recurrence Relation Example ]

  4. June 26: Code Style; Asymptotic Analysis: Recurrence Relations; Big- and little- O, Omega, and Theta. (Reading: Weiss Ch2)
              [ pptx ]   [ pdf ]   [ Annotated pdf ]
  5. June 28: Big- and little- O, Omega, and Theta; Asymptotic Analysis: Average Case using Amortized Analysis
              [ pptx ]   [ pdf ]   [ Annotated pdf ]
  6. June 30: Finish Amortized Analysis; Dictionary ADT; Intro to Hash Tables (Reading: Weiss Ch5.1 - 5.2)
              [ pptx ]   [ pdf ]   [ Annotated pdf ]

  7. July 3: Unofficial extended July 4th weekend 🇺🇸 🎉  Go have fun!
  8. July 5: Hash Table Collisions (Reading: Weiss Ch5.3 - 5.4.2)
              [ pptx ]   [ pdf ]   [ Annotated pdf ]
  9. July 7: Finish Hash Table Collisions (Weiss Ch5.4.3 - 5.5), Intro to Trees (Weiss Ch4.1 - 4.2)
              [ pptx ]   [ pdf ]   [ Annotated pdf ]   [ Quadratic Probing Proof ]

  10. July 10: Binary Search Trees (Reading: Weiss Ch4.3)
              [ pptx ]   [ pdf ]   [ Annotated pdf ]
  11. July 12: AVL Trees (Reading: Weiss Ch4.4)
              [ pptx ]   [ pdf ]   [ Annotated pdf ]
  12. July 14: Finish BSTs; Priority Queues; Begin Binary Heaps (Reading: Weiss Ch6.1 - 6.2)
              [ pptx ]   [ pdf ]   [ Annotated pdf ]   [ Minimum nodes in an AVL Tree ]

  13. July 17: Binary Heaps (Reading: Weiss Ch6.3)
              [ pptx ]   [ pdf ]   [ Annotated pdf ]
  14. July 19: Finish Binary Heaps (Reading: Weiss Ch6.3)
              [ pptx ]   [ pdf ]   [ Annotated pdf ]
  15. July 21: Midterm Exam

  16. July 24: Intro to Graphs (Reading: Weiss Ch9.1)
              [ pptx ]   [ pdf ]   [ Annotated pdf ]
  17. July 26: Graph Traversals: (BFS, DFS, Topological Sort) (Reading: Weiss Ch9.2, 9.3.1, 9.6)
              [ pptx ]   [ pdf ]   [ Annotated pdf ]
  18. July 28: Dijkstra's Algorithm (shortest path in graphs)(Reading: Weiss Ch9.3)
              [ pptx ]   [ pdf ]   [ Annotated pdf ]

  19. July 31: Finish Dijkstra's Algorithm; Preserving Abstractions (Software Design)
              [ pptx ]   [ pdf ]   [ Annotated pdf ]
  20. Aug 2: Minimum Spanning Trees (Prim's and Kruskal's Algorithms) (Reading: Weiss Ch9.5)
              [ pptx ]   [ pdf ]   [ Annotated pdf ]
  21. Aug 4: Comparison Sorting (Reading: Weiss Ch7.1 - 7.6)
              [ pptx ]   [ pdf ]   [ Annotated pdf ]

  22. Aug 7: More Sorting (Reading: Weiss Ch7.7 - 7.8, 7.11 - 7.12)
              [ pptx ]   [ pdf ]   [ Annotated pdf ]
  23. Aug 9: Finish Sorting; P vs NP (Reading: Weiss Ch9.7)
              [ pptx ]   [ pdf ]   [ Annotated pdf ]
  24. Aug 11: Begin Parallelism (Reading: Prof Dan Grossman's explanation)
              [ pptx ]   [ pdf ]   [ Annotated pdf ]

  25. Aug 14: Parallelism part 2: Map, Reduce, Analysis (Reading: Prof Dan Grossman's explanation)
              [ pptx ]   [ pdf ]   [ Annotated pdf ]
  26. Aug 16: Course Victory Lap, Practice with Design Decisions & Algorithm Solving
              [ pptx ]   [ pdf ]   [ Annotated pdf ]
  27. Aug 18: Final Exam (Good luck everyone!)

Materials from TA Review Sessions

Sections (i.e. TA Review Sessions) are optional but highly encouraged, and will be held weekly. They cover certain topics more in depth from the lectures, are an additional opportunity to practice or ask questions about material, and may or may not have postable material. When possible, review sheets and practice problems will be posted here. Solutions to the problems are covered in Section.

There are two section offerings on Thursdays.
Choose to attend either the Section at 11:00-11:50 in JHN 026 *or* the Section at 12:00-12:50 in JHN 075.

Sections:  Thursday 11:00-11:50 JHN 026,  or
Thursday 12:00-12:50 JHN 075
  1. June 22: CSE 143 Refresher (Java, Stacks, Queues, and Trees)
  2. June 29: Asymptotic Analysis
  3. July 6th: Hash Tables
  4. July 13th: AVL Trees and BSTs
  5. July 20th: Midterm Review
  6. July 27th: Graphs
  7. July 27th: More Graphs - Shortest Paths, Minimum Spanning Trees, and General Review
  8. August 10th: Sorting Algorithms
  9. August 17th: Final Review

Homework Assignments

Dropbox turn-in for homework assignments


Practice Midterms:

Practice Resources for final:

Old Midterm 2's Old Finals

Software and Textbook Information


The programming assignments will use Java. We will use Java 8, the most recent version of the language. So if installing Java on your own machine, you can get Java 8 from https://jdk8.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.

Data Structures and Algorithms Textbook

Readings from the textbook, although not required, often provide a second explanation for material covered in class. Relevant chapters are posted on the course website under lecture materials with each week.

The textbook is Data Structures and Algorithm Analysis in Java, Mark Allen Weiss, 3rd Edition, 2011, ISBN: 0132576279.
Here are links to the Errata and Code from the book

You may also reference the 2nd Edition (possibly with misaligned chapters/sections for readings), ISBN: 0321370139.
Here are links to the 2nd edition's Errata and Code from the book

The textbook is also available for 4 hour loan at the Engineering library.

Java Resources

Here are slides from a previous quarter which go through your expected Java knowledge prior to taking this course.

You can find a lot of great Java resources online!

There are a variety of (more than) sufficient book-style references. One recommended option is Core Java(TM), Volume I--Fundamentals 9th Edition, Cay S. Horstmann and Gary Cornell, 2002, ISBN: 0137081898.

Other Reference Materials

For the material on parallelism for their lectures in August (and much more we don't have time for), see these notes written by UW Professor, Dan Grossman. In lecture, we aim to cover 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, useful, and accessible articles related to the course material. These are optional reading that you may find helpful and enriching.


Access and Accommodations

Your experience in this class is important to me. If you have already established accommodations with Disability Resources for Students (DRS), please communicate your approved accommodations to me at your earliest convenience so we can discuss your needs in this course.

If you have not yet established services through DRS, but have a temporary health condition or permanent disability that requires accommodations (conditions include but not limited to; mental health, attention-related, learning, vision, hearing, physical or health impacts), you are welcome to contact DRS at 206-543-8924 or uwdrs@uw.edu or disability.uw.edu. DRS offers resources and coordinates reasonable accommodations for students with disabilities and/or temporary health conditions.  Reasonable accommodations are established through an interactive process between you, your instructor(s) and DRS.  It is the policy and practice of the University of Washington to create inclusive and accessible learning environments consistent with federal and state law.

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, Dan Grossman, Lauren Milne, and Hunter Zahn.

Valid CSS! Valid XHTML 1.1