CSE 373 Autumn 2017

Data Structures and Algorithms

Announcements

Announcements

  1. [09/27] Welcome to CSE 373 -- Announcements will be posted here throughout the course. Lecture slides will be posted after each lecture.
Course Info

Course Information and Policies

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

Contact Info

Contact Information and Office Hours

Course Email List: You should automatically be subscribed to this list and receive important email. For the most part, expect to receive announcements through the course piazza page.

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

TAs:
  Kimberly Bautista : kimb3609@cs   Office hours: Tuesdays, 2:30 - 3:20, CSE 007
  Eddie Huang : yh55@cs   Office hours: Mondays, 1:30 - 2:20, CSE 021
  Fanny Huang : xh11@cs   Office hours: Mondays, 9:00 - 9:50, CSE 220
  Rashmi Mudduluru : rashmi4@cs   Office hours: Tuesdays, 10:00 - 10:50, CSE 021
  Justin Sievers: jms97@cs   Office hours: Wednesdays, 12:30 - 1:20, CSE 007
  Anran Wang : anranw@cs   Office hours: Tuesdays, 4:30 - 5:20, CSE 021
  Wenjun Wu : wenjunw@cs   Office hours: Fridays, 1:00 - 1:50, CSE 007
  Kaiyu Zheng: kaiyuzh@cs   Office hours Wednesdays, 9:00 - 9:50, 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. September 27th: Course Introduction; ADTs; Stacks and Queues   [ pptx | pdf ]
         Weiss: 3.6 - Stacks, 3.7 - Queues
  2. 2. September 29th: Stacks Queues and Testing   [ pptx | pdf ]
         Weiss: 3.6 - Stacks, 3.7 - Queues
  3. 3. October 2nd: Dictionaries   [ pptx | pdf ]
         Weiss: 4.8 Sets and Maps
         Overload Link
  4. 4. October 4th: Algorithm Analysis   [ pptx | pdf ]
         Weiss: Chapter 2
  5. 5. October 6th: Algorithm Analysis   [ pptx | pdf ]
         Weiss: Chapter 2
  6. 6. October 9th: Amortized Analysis and BSTs   [ pptx | pdf ]
         Weiss: 4.2-4.3 and 11.1
  7. 7. October 11th: Traversals and Intro to AVL   [ pptx | pdf ]
         Weiss: 4.1 and 4.4
  8. 8. October 13th: AVL Rotations and Height proof   [ pptx | pdf ]
         AVL Visualizer
  9. 9. October 16th: Hashtables   [ pptx | pdf ]
         Weiss: 5.1,5.2,5.4 Hashing
  10. 10. October 18th: Hashtables   [ pptx | pdf ]
         Weiss: 5.3,5.5 Hashing
  11. 11. October 20th: Even MORE Hashtables   [ pptx | pdf ]
         Weiss: 5.3,5.5 Hashing
  12. 12. October 23rd: Memory and Hierarchy   [ pptx | pdf ]
         Addtional Explanation
  13. 13. October 25th: B+-Trees   [ pptx | pdf ]
         B-Tree Visualizer Remember! This course covers B+ trees, not B-Trees!
  14. 14. October 27th: Priority Queues   [ pptx | pdf ]
         Heap Visualizer Weiss - 6.1-6.3
  15. 15. October 30th: Priority Queues   [ pptx | pdf ]
  16. 16. November 1st: Exam Review   [ pptx | pdf ]
  17. 17. November 3rd: Midterm Exam
  18. 18. November 6th: Midterm Recap and Sorting   [ pptx | pdf ]
        Weiss - 7.1,7.2
  19. 19. November 8th: Sorting   [ pptx | pdf ]
        Weiss - 7.5,7.6,7.7
  20. 20. November 13th: Sorting Continued   [ pptx | pdf ]
        Weiss - 7.3,7.8
  21. 21. November 15th: Non-comparison Sorting   [ pptx | pdf ]
        Weiss - 7.11
  22. 22. November 17th: Intro to Graphs   [ pptx | pdf ]
        Weiss - 9.1 - Graph Representations
  23. 23. November 20th: Topological Sort   [ pptx | pdf ]
        Weiss - 9.2,9.3.1
  24. 24. November 22nd: Dijkstra's Algorithm   [ pptx | pdf ]
        Weiss - 9.3
  25. 25. November 27th: Union Find / Up-trees   [ pptx | pdf ]
        Weiss - Chapter 8
  26. 26. November 29th: Prim's and Kruskal's   [ pptx | pdf ]
        Weiss - 9.5
  27. 27. December 1st: Cuts, Flow and Reductions   [ pptx | pdf ]
        Weiss - 9.4
  28. 28. December 4th: Algorithm Design   [ pptx | pdf ]
        Weiss - Chapter 10
  29. 29. December 6th: Complexity   [ pptx | pdf ]
  30. 30. December 8th: Final Exam Review   [ pptx | pdf ]

  31. 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. Oracle Generics Tutorial - Useful review on generics to get up to speed.   [ Tutorial ]
    3. NPath and Cyclomatic Complexity Explanation and help around two common failures from the style checker.   [ Explanation ]
    4. Visualizers Complete set of visualizers for data structures and algorithms. Note: some of these differ from the course's verstion.   [ Visualizers ]
    5. 2. B Trees (Memory Hierarchy is involved)   Ruth's Version
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: Kaiyu Zheng - 9:30 LOW 105
AB: Anran Wang - 10:30 MOR 230
AC: Fanny Huang - 11:30 DEN 258
AD: Meredith Wu - 12:30 LOW 101
AE: Justin Sievers - 2:30 EGL 001
AF: Rashmi Mudduluru - 3:30 JHN 022
AG: Kimberly Bautista and Eddie Huang - 3:30 MGH 242

TA led sections will be held weekly on Thursdays. You should expect to go to your registered weekly section. They will be incredibly helpful for review, applicable practice of the material, and hints on your homework.

  1. Section 1: Review of Client vs Implementor; Stacks and Queues; practice with Java skills.   Old Java Review Slides   Section Problems
  2. Section 2: Asymptotic runtime, Big-O definition, Heaps and Priority Queues   Section Problems Solutions
  3. Section 3: Analysis, Traversals and AVL   Section Problems Solutions Corrections
  4. Section 4: AVL and Hashtables   Section Problems Solutions Corrections
  5. Section 5: Memory and B-Trees   Section Problems Solutions
  6. Section 7: Sorting   Section Problems Solutions
  7. Section 8: Sorting II   Section Problems Solutions
  8. Section 9: Graphs   Section Problems Solutions
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.

Exams

The midterm for this course will be Friday, November 3 from 2:30-3:20 in the normal room for lecture.
A practice midterm is available here. Some additional short answer questions and solutions are here.

Historical Practice Midterms:

The final for this course will be December 12th, from 2:30-4:20 in the normal room for lecture.
Here are some practice problems with drawn solutions from Spring's exam review'
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.

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, do not use Java 9. It is unlikely to cause problems, but because it is new, insufficient testing has been completed. So if installing Java on your own machine, you can get Java 8 from https://jdk8.java.net/.

    We require use of the Eclipse IDE for all coding assignments. 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 Project 0.

    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.