CSE 373 Autumn 2017
Data Structures and Algorithms
Announcements
- [09/27] Welcome to CSE 373 -- Announcements will be posted here throughout the course. Lecture slides will be posted after each lecture.
Course Information and Policies
Instructor: Evan McCarty CSE 214
Lecture: Monday, Wednesday, Friday 2:30-3:20 KNE 220
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
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. September 27th: Course Introduction; ADTs; Stacks and Queues [ pptx | pdf ] Weiss: 3.6 - Stacks, 3.7 - Queues
- 2. September 29th: Stacks Queues and Testing [ pptx | pdf ] Weiss: 3.6 - Stacks, 3.7 - Queues
- 3. October 2nd: Dictionaries [ pptx | pdf ] Weiss: 4.8 Sets and Maps Overload Link
- 4. October 4th: Algorithm Analysis [ pptx | pdf ] Weiss: Chapter 2
- 5. October 6th: Algorithm Analysis [ pptx | pdf ] Weiss: Chapter 2
- 6. October 9th: Amortized Analysis and BSTs [ pptx | pdf ] Weiss: 4.2-4.3 and 11.1
- 7. October 11th: Traversals and Intro to AVL [ pptx | pdf ] Weiss: 4.1 and 4.4
- 8. October 13th: AVL Rotations and Height proof [ pptx | pdf ] AVL Visualizer
- 9. October 16th: Hashtables [ pptx | pdf ] Weiss: 5.1,5.2,5.4 Hashing
- 10. October 18th: Hashtables [ pptx | pdf ] Weiss: 5.3,5.5 Hashing
- 11. October 20th: Even MORE Hashtables [ pptx | pdf ] Weiss: 5.3,5.5 Hashing
- 12. October 23rd: Memory and Hierarchy [ pptx | pdf ] Addtional Explanation
- 13. October 25th: B+-Trees [ pptx | pdf ] B-Tree Visualizer Remember! This course covers B+ trees, not B-Trees!
- 14. October 27th: Priority Queues [ pptx | pdf ] Heap Visualizer Weiss - 6.1-6.3
- 15. October 30th: Priority Queues [ pptx | pdf ]
- 16. November 1st: Exam Review [ pptx | pdf ]
- 17. November 3rd: Midterm Exam
- 18. November 6th: Midterm Recap and Sorting [ pptx | pdf ] Weiss - 7.1,7.2
- 19. November 8th: Sorting [ pptx | pdf ] Weiss - 7.5,7.6,7.7
- 20. November 13th: Sorting Continued [ pptx | pdf ] Weiss - 7.3,7.8
- 21. November 15th: Non-comparison Sorting [ pptx | pdf ] Weiss - 7.11
- 22. November 17th: Intro to Graphs [ pptx | pdf ] Weiss - 9.1 - Graph Representations
- 23. November 20th: Topological Sort [ pptx | pdf ] Weiss - 9.2,9.3.1
- 24. November 22nd: Dijkstra's Algorithm [ pptx | pdf ] Weiss - 9.3
- 25. November 27th: Union Find / Up-trees [ pptx | pdf ] Weiss - Chapter 8
- 26. November 29th: Prim's and Kruskal's [ pptx | pdf ] Weiss - 9.5
- 27. December 1st: Cuts, Flow and Reductions [ pptx | pdf ] Weiss - 9.4
- 28. December 4th: Algorithm Design [ pptx | pdf ] Weiss - Chapter 10
- 29. December 6th: Complexity [ pptx | pdf ]
- 30. December 8th: Final Exam Review [ pptx | pdf ]
- Java Review - Here are some slides from a previous quarter which go through expected knowledge from last quarter. [ Slides ]
- Oracle Generics Tutorial - Useful review on generics to get up to speed. [ Tutorial ]
- NPath and Cyclomatic Complexity Explanation and help around two common failures from the style checker. [ Explanation ]
- Visualizers Complete set of visualizers for data structures and algorithms. Note: some of these differ from the course's verstion. [ Visualizers ]
- 2. B Trees (Memory Hierarchy is involved) Ruth's Version
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.
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 242TA 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.
- Section 1: Review of Client vs Implementor; Stacks and Queues; practice with Java skills. Old Java Review Slides Section Problems
- Section 2: Asymptotic runtime, Big-O definition, Heaps and Priority Queues Section Problems Solutions
- Section 3: Analysis, Traversals and AVL Section Problems Solutions Corrections
- Section 4: AVL and Hashtables Section Problems Solutions Corrections
- Section 5: Memory and B-Trees Section Problems Solutions
- Section 7: Sorting Section Problems Solutions
- Section 8: Sorting II Section Problems Solutions
- Section 9: Graphs Section Problems Solutions
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.
- Programming Guidelines
- Written-Homework Guidelines
- Course Piazza page. Please check here to post questions or clarifications.
- Project 1. Part 1 due October 4th, 11:30 pm, Part 2 due October 11, 11:30 pm Here is the eclipse file you will need to complete the project. Part 0 is meant to help you setting up the IDE and JDK and familiarizing yourself with running the tests.
- Homework. Written Assignment Due individually October 18th, 11:30 pm
- Project 3 Here is the eclipse file you will need to complete the project. Part 1 due November 15th, 11:30 pm, Part 2 due November 22nd, 11:30 pm Part 3 due November 29th, 11:30 pm
- Written Assignment. Written Assignment Due individually December 6th, 11:30 pm. NO LATE DAYS
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:
- cse373 Fall 2010 midterm unsolved / solved
- cse373 Spring 2010 midterm unsolved /solved
- cse373 Fall 2011 midterm unsolved /solved
- cse373 Fall 2012 midterm unsolved /solved
- cse373 Winter 2012 midterm unsolved /solved
- cse373 Fall 2013 midterm unsolved /solved
Historical Practice Resources for final:
cse373 Winter 2017 final exam solved
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.