CSE 373 Spring 2017

Data Structures and Algorithms

Announcements

Announcements

  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.
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

TAs:
  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

Lectures

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. 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.
Sections

Sections

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.

    Exams

    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:

    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.