CSE 373 Winter 2017
Data Structures and Algorithms
Announcements
- [03/12] There will be a TA led optional review session for the final exam tomorrow, Monday the 13th, from 4:30-5:30 in ARC 147.
- [03/05] The anonymous course evaluations are open starting today. The link is here and you should also get at least one email about them to your @uw email address. Please take the time to fill them out. As a reminder, they are completely anonymous, are only about evaluating the lecture / course in general (not your TA), and I only receive them AFTER final grades have been assigned, so they will not affect your grade at all. They are very useful to help me improve -- please be as specific on them as possible. Thanks!
- [02/22]The CSE 14X TA applications are currently open. You can find more information here.
- [02/21] Riley is adding an office hour tomorrow, Wednesday, February 22nd, from 1:00-2:00 to compensate for the Monday office hour being missed due to President's day.
- [02/19] There is a deadline tomorrow for switching to S/NS grading. To help you make your decision on whether you want to consider that option, I have written a grade calculation guide.
- [02/08] Riley is adding an extra office hour, tomorrow, Thursday February 9th from 12:30-1:30pm to help with preparation for the midterm.
- [02/06] The University is closed today for snow. Class and office hours are cancelled. Riley's office hour today will be moved to Wednesday 1:00-2:00 before lecture. Enjoy the snow!
- [02/03] You can request items for the exam cheat sheet here
- [02/02] The URL for the HW regrade form is here
- [01/19] There is a symposium highlighting the accomplishments of some of the University of Washington's outstanding women scientists and engineers being offered from the UW CSE department tomorrow from 2:30-5:00pm
- [01/11] The materials for the Java review session are linked below. The comments in the files describe the material that was covered in the session.
- [01/09] There will be an optional Java review session tomorrow, Tuesday, January 10th, from 3:30-4:30pm in PAA A102. TAs will be around after the session to answer individual questions. Any materials used will be posed online.
- [01/04] The URL for the overload form is here
Course Information and Policies
Instructor: Riley Porter CSE 450
Lecture: Monday, Wednesday, Friday 2:30-3:20 BAG 131
Section: Various times on Thursday
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.
Anonymous Feedback (goes only to the instructor, although since it's anonymous you can't get a direct reply. For questions requiring a reply, either use the discussion board or directly email the instructor.)
Course Staff and Office Hours:
Instructor: Riley Porter: rileymp2@cs.washington.edu CSE 450, Mondays 3:30-4:30pm, Tuesdays 1:30pm-2:30pm, or by appointment.
TAs Organized By Office Hour Times:
Pascale Wallace Patterson : pattersp@cs.washington.edu Mondays 9:30-10:30am, CSE 220
Raquel Van Hofwegen : raqvh@cs.washington.edu Mondays 11:30-12:30pm, CSE 3rd Floor Breakout Area (area with whiteboards by stairs)
Josh Curtis : curtijd@cs.washington.edu Tuesdays 10:00-11:00am, CSE 3rd Floor Breakout Area (area with whiteboards by stairs)
Zelina Chen : zelinac@cs.washington.edu Tuesdays 2:30-3:30pm, CSE 5th Floor Breakout Area (area with whiteboards by stairs)
Trung Ly : trungly@cs.washington.edu Wednesdays 10:00-11:00am, CSE 021
Rebecca Yuen : rebyuen@cs.washington.edu Wednesdays 11:00-12:00pm, CSE 021
Hunter Zahn : hzahn93@cs.washington.edu Wednesdays 11:30-12:30pm, CSE 674
Matthew Rockett : rockettm@cs.washington.edu Wednesdays 3:30-4:30pm, CSE 5th Floor Breakout Area (area with whiteboards by stairs)
Paul Curry : paulmc@cs.washington.edu Thursdays 1:30-2:30pm, CSE 5th Floor Breakout Area (area with whiteboards by stairs)
Kyle Thayer : kthayer@cs.washington.edu Thursdays 2:00-3:00pm, CSE 5th Floor Breakout Area (area with whiteboards by stairs)
Chloe Lathe : lathec@cs.washington.edu Fridays 1:30-2:30pm, CSE 220
Lecture Materials
Material in the future naturally subject to change in terms of coverage or schedule
- 1. January 4th: Course Introduction; ADTs; Stacks and Queues pptx pdf1up
- 2. January 6th: Pseudocode; more ADTs; Priority Queues; Heap, Reading: Weiss, 6.1 - 6.2 pptx pdf1up
- 3. January 9th: Algorithm Analysis, Reading: Weiss, Chapter 2 pptx pdf
- 4. January 11th: More Algorithm Analysis; More Heaps, Reading: Weiss, Chapter 2 pptx pdf
- 5. January 13th: More Heaps (Floyd's Algorithm); Dictionaries; Binary Search Trees, Reading: Weiss, Chapter 6.1 - 6.3 pptx pdf
- 6. January 16th: MLK Day, University Holiday, No Class
- 7. January 18th: More BSTs; Amortized Analysis, Reading: Weiss Chapter 6.3 pptx pdf
- 8. January 20th: AVLTrees pptx pdf
- 9. January 23rd: More AVLTrees
pptx
pdf
Optional slides not discussed in class for AVL deletion: pptx pdf - 10. January 25th: Hash Tables, Reading: Weiss, 5.1 - 5.5 pptx pdf
- 11. January 27th: Hash Tables, continued, Reading: Weiss, 5.3 - 5.4 pptx pdf
- 12. January 30th: Preserving Abstractions pptx pdf PriorityQueue.java BinaryMinHeap.java Client.java
- 13. February 1st: Disjoint Sets, Reading: Weiss, 8.1-8.2, 8.7 pptx pdf
- 14. February 3rd: Union Find, Reading: Weiss 8.3-8.6 pptx pdf
- 15. University closed for snow Happy snow day!
- 16. February 8th: Midterm Review
- 17. February 10th: Midterm (in class)
- 18. February 13th: Intro to Graphs, Reading Weiss 9.1 pptx pdf
- 19. February 15th: Topological Sort and Graph Traversals, Reading Weiss 9.2, 9.3, 9.6 pptx pdf
- 20. February 17th: Dijkstra's Algorithm, Reading Weiss 9.2, 9.3, 9.6 pptx pdf
- 21. February 20th: President's Day; University holiday, no class
- 22. February 22nd: Minimum Spanning Trees, Reading Weiss 9.5 pptx pdf
- 23. February 24nd: (Extra Topic) Testing and JUnit
pptx
pdf
SortingUtility.java
MinTest.java
SortingTest.java
- 24. February 27th: Comparison Sorting, Reading Weiss 7.1 - 7.8 pptx pdf
- 25. March 1st: More Comparison Sorting and Beyond Comparison Sorting pptx pdf
- 26. March 3rd: More Sorting and (Extra Topic) Induction and Recurrences pptx pdf recurrences induction more recurrences
- 27. March 6th: (Extra Topic) Parallelism and Concurrency 1, Reading Professor Dan Grossman's Explanation pptx pdf Dan's prefix sum slides
- 28. March 8th: (Extra Topic) Interviewing and Problem Solving unsolved pptx pdf
- 29. March 10th: Course Victory Lap / What's Next / Final Review pptx pdf
Extra Extra Material:
- 1. Locality and Memory Hierarchy Kevin's Version: pdf Kevin's Version: pptx
- 2. B Trees (Memory Hierarchy is involved) Ruth's Version
- 3. P vs. NP: Efficient Reductions and Problem Complexity Ruth's Version: part 1 pdf Ruth's Version: part 2 pdf Adam's Version: pdf with ink
- 4. Parallelism and Concurrency: Synchronization and Data Races Adam's Version: pdf
- 5. Parallel Reductions: Map and Reduce Kevin's Version: pdf
- 6. Introduction to Artificial Intelligence and Game Theory Kevin's Version: pdf
Sections
TA led sections will be held weekly on Thursdays. Section problems will be posted on Wednesdays before section. Section solutions will only be available in person in your section on Thursdays. If you have to miss a section, you can contact your TA to see if they have extra solution handouts. However, 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
- Section 3: More Heaps, BSTs, and Amortized Runtime Analysis Section Problems
- Section 4: AVL Trees, Hashing Section Problems
- Section 5: More Hashing Section Problems
- Section 6: Midterm Review Section Problems
- Section 7: Graphs, Union-Find Section Problems
- Section 8: More Graphs Section Problems
- Section 9: Sorting (Includes Solutions) Section Problems
- Section 10: Final Review Section Problems
Topic Summaries
We will be releasing topic summaries so you can gauge your mastery of the material.
- Amortized Runtime. Alternative, but very similar explanation of Amortized Runtime
- AVL Trees
- Hashing
- Intro To Graphs
Homework Assignments
Turn in your assignments through the Canvas course page.
Some students have concerns on what is allowed for the homework or how to write pseudocode for the written homework assignments. The following guidelines will hopefully answer those questions for you, but if you're still concerned, please use the Course Discussion Board.
Homework 0: on-line survey worth 0 points, "due" Monday, January 9th
- Homework 1 due 11PM, Tuesday, January 17th
- Homework 2 due 11PM, Friday, January 27th
- Homework 3 due 11PM, Friday, February 10th
- Homework 4 due 11PM, Wednesday, February 22nd
- Homework 5 due 11PM, Friday, March 3rd
- Homework 6 due 11PM, Friday, March 10th
Exams
Midterm: February 10th, Friday (in class)
Regrade Policy: You can ask for a regrade up through Friday, February 25th. To ask for a regrade, please write up a note of what points you deserve back on your exam and give it to Riley or slip it under the door of CSE 450. Note: if you ask for a regrade, your entire exam will be regraded. Your score could go down from a regrade, so please be certain that you want one.
You can request items for the exam cheat sheet here. You have until Tuesday, February 7th to submit requests.
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
The exams listed below in the final exam prep can also be used (other versions of this class had 2 midterms, the exams below are either the 2nd midterm or the final exam). Most of those exams have hashing problems, some have abstraction problems, some runtime, some heaps, and some short answer questions you could tackle. It is worth looking through them, at least for hashing practice. Ignore the exam problems to do with graphs, union-find, or any of the other topics listed above in the section for what will not be on the exam.
Final: Tuesday, March 14th, 2017, 2:30-4:20, BAG 131
Regrade Policy: You can pick up your exam from the CSE front desk. Bring your husky ID to identify yourself. You can ask for a regrade up through the second Friday of Spring quarter, April 7th. To ask for a regrade, please write up a note of what points you deserve back on your exam and give it to Riley or slip it under the door of CSE 450. Note: if you ask for a regrade, your entire exam will be regraded. Your score could go down from a regrade, so please be certain that you want one. That being said, we do make mistakes, so please do ask for a regrade if you think you deserve one.
Exam Policies- Please bring your Husky Card / Student ID
- Closed book
- Closed notes
- No calculators or other electronic devices
- Begins promptly at 2:30 and ends promptly at 4:20 on Tuesday, March 14th
- If an emergency happens, contact Riley as soon as possible. You must receive permission from Riley before the start of the exam in order for the option of an alternative.
- Any open exams (writing, reading, erasing, etc) before the exam starts or after the time is called will result in a 10 point deduction.
The final exam is not technically cumulative but so many of the topics have been course long topics (analysis of asymptotic runtime, pseudocode, choosing the correct ADT, design decisions, abstraction between client and implementor, etc), that you may feel like it is cumulative and you may want to study topics introduced before the midterm to feel completely prepared.
Fair Game Exam Topics:
- Union-Find
- Graphs
- Traversals, shortest cost path, Topological sort
- Minimum Spanning Trees
- Sorting
- Writing Pseudocode
- Analysis of runtime of pseudocode and ADT operations
- Any ADT we covered
- Preserving abstraction of client vs implementor: deep copy, immutability, copy-in and copy-out
- Anything from the homework assignments.
Not on Exam:
- Proof of lower bound for comparison sorting
- Proof of average case runtime for quick sort
- Proof by Induction
- Recurrence Relations
- BST or AVL deletion
- Calculating number of nodes in a tree (total number or number at a level).
- Skew Heaps
- B Trees
- Memory and Locality
- Concurrency or Parallelism
- Complexity Theory
- Mini-Max Search
- Testing theory or JUnit
Exam Format and Sample Exams
Our exam will consist of various types of short-answer questions. You may be asked to write or read Java code or pseudocode. It will be similar in style to the midterm, but covering different topics and with the potential for slightly different styles of questions. In particular, the midterm was a very breadth based exam (lots of topics, high level questions, mechanical questions), whereas the final exam will be a depth based exam (few topics at a much deeper level).
Please understand these caveats:
- Topics covered on these exams may not be the exact same topics covered on our exam; please see above for the topics covered on our exam.
- The sample exams are provided as a study guide, not as any guarantee of the format of our actual midterm in terms of length or type of questions. In particular, they are all from different instructors, and every instructor brings a certain style to exam-writing.
Historical Practice Resources for final:
Additional Study Suggestions
- Re-work problems from lecture and homework.
- Do additional problems from the textbook.
- Review your notes and all lecture materials.
- Review any pseudocode and any algorithms we covered in lecture.
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.
Here are some interesting, useful, and accessible articles related to the course material. These are optional reading that you may find helpful and enriching.
- The Data-Structure Canon, George V. Neville-Neil
- Bubble Sort: An Archaeological Algorithmic Analysis, Owen Astrachan
- Wikipedia: Comparison Sort (follow links to different sorting algorithms to see animations of the algorithms in action)
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, Kevin Quinn, and Hunter Zahn.