CSE 373 Winter 2017

Data Structures and Algorithms

Announcements

Announcements

  1. [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.
  2. [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!
  3. [02/22]The CSE 14X TA applications are currently open. You can find more information here.
  4. [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.
  5. [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.
  6. [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.
  7. [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!
  8. [02/03] You can request items for the exam cheat sheet here
  9. [02/02] The URL for the HW regrade form is here
  10. [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
  11. [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.
  12. [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.
  13. [01/04] The URL for the overload form is here
Course Info

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

Homework Regrade Request Form

Course Discussion Board

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

Lectures

Lecture Materials

Material in the future naturally subject to change in terms of coverage or schedule

  1. 1. January 4th: Course Introduction; ADTs; Stacks and Queues   pptx   pdf1up
  2. 2. January 6th: Pseudocode; more ADTs; Priority Queues; Heap, Reading: Weiss, 6.1 - 6.2   pptx   pdf1up
  3. 3. January 9th: Algorithm Analysis, Reading: Weiss, Chapter 2   pptx   pdf
  4. 4. January 11th: More Algorithm Analysis; More Heaps, Reading: Weiss, Chapter 2   pptx   pdf
  5. 5. January 13th: More Heaps (Floyd's Algorithm); Dictionaries; Binary Search Trees, Reading: Weiss, Chapter 6.1 - 6.3   pptx   pdf
  6. 6. January 16th: MLK Day, University Holiday, No Class
  7. 7. January 18th: More BSTs; Amortized Analysis, Reading: Weiss Chapter 6.3   pptx   pdf
  8. 8. January 20th: AVLTrees   pptx   pdf
  9. 9. January 23rd: More AVLTrees   pptx   pdf
    Optional slides not discussed in class for AVL deletion:   pptx   pdf
  10. 10. January 25th: Hash Tables, Reading: Weiss, 5.1 - 5.5   pptx   pdf
  11. 11. January 27th: Hash Tables, continued, Reading: Weiss, 5.3 - 5.4   pptx   pdf
  12. 12. January 30th: Preserving Abstractions   pptx   pdf   PriorityQueue.java   BinaryMinHeap.java   Client.java
  13. 13. February 1st: Disjoint Sets, Reading: Weiss, 8.1-8.2, 8.7   pptx   pdf
  14. 14. February 3rd: Union Find, Reading: Weiss 8.3-8.6   pptx   pdf
  15. 15. University closed for snow Happy snow day!
  16. 16. February 8th: Midterm Review
  17. 17. February 10th: Midterm (in class)
  18. 18. February 13th: Intro to Graphs, Reading Weiss 9.1   pptx   pdf
  19. 19. February 15th: Topological Sort and Graph Traversals, Reading Weiss 9.2, 9.3, 9.6   pptx   pdf
  20. 20. February 17th: Dijkstra's Algorithm, Reading Weiss 9.2, 9.3, 9.6   pptx   pdf
  21. 21. February 20th: President's Day; University holiday, no class
  22. 22. February 22nd: Minimum Spanning Trees, Reading Weiss 9.5   pptx   pdf
  23. 23. February 24nd: (Extra Topic) Testing and JUnit   pptx   pdf   SortingUtility.java   MinTest.java   SortingTest.java
  24. 24. February 27th: Comparison Sorting, Reading Weiss 7.1 - 7.8   pptx   pdf
  25. 25. March 1st: More Comparison Sorting and Beyond Comparison Sorting   pptx   pdf
  26. 26. March 3rd: More Sorting and (Extra Topic) Induction and Recurrences   pptx   pdf   recurrences   induction   more recurrences
  27. 27. March 6th: (Extra Topic) Parallelism and Concurrency 1, Reading Professor Dan Grossman's Explanation   pptx   pdf   Dan's prefix sum slides
  28. 28. March 8th: (Extra Topic) Interviewing and Problem Solving   unsolved   pptx   pdf
  29. 29. March 10th: Course Victory Lap / What's Next / Final Review   pptx   pdf

Extra Extra Material:

  1. 1. Locality and Memory Hierarchy   Kevin's Version: pdf   Kevin's Version: pptx
  2. 2. B Trees (Memory Hierarchy is involved)   Ruth's Version
  3. 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. 4. Parallelism and Concurrency: Synchronization and Data Races   Adam's Version: pdf
  5. 5. Parallel Reductions: Map and Reduce   Kevin's Version: pdf
  6. 6. Introduction to Artificial Intelligence and Game Theory   Kevin's Version: pdf
Sections

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.

  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
  3. Section 3: More Heaps, BSTs, and Amortized Runtime Analysis   Section Problems
  4. Section 4: AVL Trees, Hashing   Section Problems
  5. Section 5: More Hashing   Section Problems
  6. Section 6: Midterm Review   Section Problems
  7. Section 7: Graphs, Union-Find   Section Problems
  8. Section 8: More Graphs   Section Problems
  9. Section 9: Sorting (Includes Solutions)   Section Problems
  10. Section 10: Final Review   Section Problems
Topic Summaries

Topic Summaries

We will be releasing topic summaries so you can gauge your mastery of the material.

  1. Amortized Runtime. Alternative, but very similar explanation of Amortized Runtime
  2. AVL Trees
  3. Hashing
  4. Intro To Graphs
Homeworks

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 Regrade Request Form

Homework 0: on-line survey worth 0 points, "due" Monday, January 9th

Exams

Midterm: February 10th, Friday (in class)

Solution

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:

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

Solution

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

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:

Not on Exam:

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:

Historical Practice Resources for final:

  • 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)

    • Additional Study Suggestions

    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.

    Here are some interesting, useful, and accessible articles related to the course material. These are optional reading that you may find helpful and enriching.

    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.