CSE 373 Spring 2017

Data Structures and Algorithms



  1. [03/26] Welcome to CSE 373 -- Announcements will be posted here throughout the course. Lecture slides will be posted after each lecture.
  2. [03/27] Here is the link for overload/waitlist students. The 'secret code' will be given in lecture.
  3. [03/29] The first homework assignment is posted. Also, TA assignments for sections are at the bottom of the page.
  4. [06/02] Course Evaluations are available until Sunday night! Please take 5 minutes to complete them.
Course Info

Course Information and Policies

Instructor: Evan McCarty CSE 214
Lecture: Monday, Wednesday, Friday 2:30-3:20 SMI 120

Contact Info

Contact Information and Office Hours

Course Email List: You should automatically be subscribed to this list and receive email every once in a while. Any important announcements will be sent to this list. Important announcements will also be posted to the webpage above.

Course Staff and Office Hours:
  Instructor: Evan McCarty: ejmcc@cs.washington.edu   Mondays, 11:00-11:50 and Wednesdays, 3:30-4:20 or by appointment; Room CSE 214

  Jack Armstrong : jackarms@cs.washington.edu   Tuesdays, 2:30-3:20; Room CSE 021
  Kimberly Bautista: kimb3609@cs.washington.edu   Fridays, 3:30-4:20; Room CSE 220 and Fridays, 4:30-5:20 in CSE 021
  Autumn Blackburn : kblack37@cs.washington.edu   Fridays, 12:30-1:20; Room CSE 220 and Wednesdays, 5:30-6:20 in CSE 220
  Chloe Lathe: lathec@cs.washington.edu   Mondays, 12:00-12:50; Room CSE 021
  Matthew Rockett : rockettm@cs.washington.edu   Mondays, 10:30-11:20; Room CSE 220
  Mert Saglam : saglam@cs.washington.edu   Tuesdays, 11:00-11:50; Room CSE 220
  Justin Sievers : jms97@cs.washington.edu   Fridays, 1:30-2:20; Room CSE 007
  Dorothy Truong : dotruong@cs.washington.edu   Mondays, 3:30-4:20; Room CSE 021
  Kevin Vong: kevong@cs.washington.edu   Wednesdays, 11:30-12:20; Room CSE 220
  James Wang: jamesw96@cs.washington.edu   Tuesdays, 12:00-1:20; Room CSE 220
  Hunter Zahn : hzahn93@cs.washington.edu   Wednesdays, 12:30-1:20; Room CSE 220
  Marina Zhou : rainran@cs.washington.edu   Mondays, 1:00 - 1:50; Room CSE 021


Lecture Materials

By end of day, lecture slides will be posted here from the day's lecture. Topics for the following lecture will be uploaded along with that day's slides', along with relevant chapters from the Weiss textbook. Readings that are required before lecture will be indicated in bold.
  1. 1. March 27th: Course Introduction; ADTs; Stacks and Queues   [ pptx | pdf ]
         Weiss: 3.6 - Stacks, 3.7 - Queues
  2. 2. March 29th: Circular Queues, Testing and Priority Queues   [ pptx | pdf ]
         6.1 - Priority Queues
  3. 3. March 31st: Trees, Heaps and Data Structure Properties   [ pptx | pdf | doc notes ]
        6.2,6.3 - Priority Queues (Heaps)
  4. 4. April 3rd: Algorithm Analysis   [ pptx | pdf ]
        Chapter 2 - Algorithm Analysis
  5. 5. April 5th: Algorithm Analysis, cont   [ pptx | pdf ]
        Additional Big O Explanation
  6. 6. April 7th: buildHeap; Floyd's Method   [ pptx | pdf ]
        6.3.4 - BuildHeap
  7. 7. April 10th: Dictionary ADT   [ pptx | pdf ]
         No readings
  8. 8. April 12th: Dictionary ADT, Binary Search Trees   [ pptx | pdf ]
         4.8 - Sets and Maps
  9. 9. April 14th: Tree Traversals   [ pptx | pdf ]
         4.1-4.2 - Trees
  10. 10. April 17th: Tree Balance and AVL   [ pptx | pdf ]
         4.3-4.4 - Binary Trees
  11. 11. April 19th: AVL cont   [ pptx | pdf ]
         4.4 - AVL Trees - Additional AVL resource.
  12. 12. April 21tst: AVL and Memory Analysis   [ pptx | pdf ]
         No new readings
  13. 13. April 24th: Hash Tables   [ pptx | pdf ]
         5.1-5.2 and 5.4 Hash Tables
  14. 14. April 26th: Exam Review   [ pptx | pdf ]
  15. 15. April 28th: Midterm Exam
  16. 16. May 1st: Hashing   [ pptx | pdf ]
         No new readings
  17. 17. May 3rd: Graphs   [ pptx | pdf ]
         9.1 - Representation of Graphs
  18. 18. May 5th: More Graphs   [ pptx | pdf ]
         9.2 - Topological Sort
         Here is a good tutorial on exception throwing which should help with HW4
  19. 19. May 8th: Dijskstra's Algorithm   [ pptx | pdf ]
         9.3.1-9.3.2 - Dijkstras Algorithm
  20. 20. May 10th: Spanning Trees and Union Find   [ pptx | pdf ]
         Ch 8 - Disjoint Set
  21. 21. May 12th: Minimum Spanning Trees   [ pptx | pdf ]
         9.5 - Minimum Spanning Tree
  22. 22. May 15th: Iterators   [ pptx | pdf ]
         3.3.2 - Iterators
  23. 23. May 17th: Sorting   [ pptx | pdf ]
         7.1-7.4 Simple Sorting
  24. 24. May 19th: Sorting   [ pptx | pdf ]
         7.3,7.5 Sorting
  25. 25. May 22nd: Sorting   [ pptx | pdf ]
         7.6,7.7 Sorting
  26. 26. May 24th: Sorting   [ pptx | pdf ]
         7.8 - Lower bound
  27. 27. May 26th: Algorithm Design   [ pptx | pdf ]
         10.1,10.2,10.4 - Algorithm Design
  28. 28. May 31st: Randomization and Memory Features   [ pptx | pdf ]
  29. 29. June 2nd: Exam Review   [ pptx | pdf | Topics List | Practice Final ]

  30. Extra Material:

      Occasionally, I may post additional slides or information that you may find informative or interesting. This is additional material and you will not be responsible for it on exams.
    1. Java Review - Here are some slides from a previous quarter which go through expected knowledge from last quarter.   [ Slides ]
    2. Here is some information on amortized runtime for those of you who are doing the writeup as their extra assignment. . Alternative, but very similar explanation of Amortized Runtime
    3. Here is a good tutorial on exception throwing which should help with HW4
    4. Here is an okay starting point for iterators if you do this for extra credit.


Section material distributed to TAs will be made available here. Solutions to problems posted here must be gotten in section from the TA.
Sections (All times on Thursdays):
AA: Kimberly Bautista and Kevin Vong - 9:30 LOW 105
AB: Mert Saglam - 10:30 MGH 242
AC: Justin Sievers - 12:30 PCAR 293
AD: Chloe Lathe - 1:30 MGH 271
AE: Marina Zhou - 2:30 MUE 154
AF: James Wang - 3:30 SAV 130
AG: Jack Armstrong - 12:30 LOW 106
  • Section 2: Asymptotic runtime, Big-O definition, Heaps and Priority Queues   Section Problems
  • Section 3: More Heaps, BSTs   Section Problems
  • Section 4: AVL Trees, Traversals   Section Problems
  • Section 5: Midterm Review
  • Section 6: Hashing   Section Problems
  • Section 7: Dijkstra and Graphs   Section Problems
  • Section 8: Minimum Spanning Trees and Iterators   Section Problems
  • Homeworks

    Homework Assignments

    Turn in your assignments through the Canvas course page. Homework will be posted on Wednesdays and due the following Wednesday at midnight.

    If you think there was an error in the grading of your submission, please fill out the following regrade request form. Please do so by the Monday after grades are returned. No regrades for assignments 1-3 will be given after the midterm.


    The midterm for this course will be April 28th, from 2:30-3:20 in the normal room for lecture. Here is the practice midterm. Many of the problems are similar to problems from previous quarters midterms which are copied below. Pay attention to the final question on the exam as it is the most unlike questions posed in previous quarters. Here are the solutions to the practice midterm.

    Historical Practice Midterms:

    The midterm for this course will be June 6th, from 2:30-4:20 in the normal room for lecture.
    Here are the drawn notes from the first review session on Wednesday.
    Here are the slides from the review session on Friday.
    Here is list of topics for the final exam.
    Here is the practice exam, remember that in class, I announced that this practice exam, unlike the practice midnterm, is likely to be easier than the actual final.
    Expect some tricks and to need clever solutions. Many of the problems are similar to problems from previous quarters midterms which are copied below. Pay attention to the final question on the exam as it is the most unlike questions posed in previous quarters. Keep in mind, that you will not be required to write code on the exam, but that you may be required to analyze Java code during the exam.
    Here are the solutions to the non-technical questions
    Here is a great set of tools which will help you understand and verify solutions to the technical portions

    Historical Practice Resources for final:

    cse373 Winter 2017 final exam solved

  • cse373 Fall 2010 midterm 2 unsolved / solved
  • cse373 Spring 2010 midterm 2 unsolved /solved
  • cse373 Fall 2011 midterm 2 unsolved /solved
  • cse373 Fall 2012 midterm 2 unsolved /solved
  • cse373 Winter 2012 midterm 2 unsolved /solved
  • cse373 Fall 2013 midterm 2 unsolved /solved
  • cse373 Winter 2014 Exam unsolved / solved
  • cse373 Winter 2013 Exam unsolved/ solved
  • cse373 Sp 2012 Exam Solved (sorry no unsolved version)
  • Software/Books

    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.

    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 you can search for most of this information on the web, 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.

    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 Riley Porter, Ruth Anderson, Dan Grossman, Kevin Quinn, and Hunter Zahn.