CSE373 Summer 2016

Data Structures and Algorithms

Course Info

Course Information and Policies

Lecture: Monday, Wednesday, Friday 10:50-11:50 EXED 110

Office Hours:
  Instr: Hunter Zahn: Monday and Wednesday 12:10-1:10pm in CSE 220

  TA office hours will be in the 4th floor breakout in CSE (whiteboard area by the stairs)/elevators

  TA: Dan Butler : Thursday 5:00-6:00pm and Friday 4:00-5:00pm
  TA: Lilian de Greef : Thursday 3:00-5:00pm
  TA: Alon Milchgrub : Tuesday 12:00-2:00pm

Contact Info

Contact Information

Course Email List: You should receive email sent to the course mailing list regularly, roughly at least once a day. Any important announcements will be sent to this list.

Email sent to cse373-staff@cs.washington.edu (not @u...) will reach the instructor and all the TAs. For questions multiple staff members can answer, please use this email so that you get a quicker reply and the whole staff is aware of points of confusion.

Course staff:
  All staff: cse373-staff@cs.washington.edu (not @u...)
  Instructor: Hunter Zahn: hzahn93@cs.washington.edu

  TA: Dan Butler : djbutler@cs.washington.edu
  TA: Lilian de Greef : ldegreef@cs.washington.edu
  TA: Alon Milchgrub : alonmil@cs.washington.edu

Course Discussion Board (optional but encouraged)

Anonymous Feedback (goes only to the instructor)

Lectures

Lecture Materials

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

  1. 1. June 20: Course Introduction; ADTs; Stacks and Queues   pptx   pdf1up
  2. 2. June 22: Math Review; Algorithm Analysis; Induction   pptx   pdf1up   induction notes
  3. 3. June 24: Asymptotic Analysis, Reading: Weiss, Chapter 2   pptx   pdf   recurrence relation notes   Big-O example
  4. 4. June 27: Dictionaries; Binary Search Trees No reading   pptx   pdf1up
  5. 5. June 29: More BSTs; AVLTrees , Reading: Weiss, 4.4   pptx   pdf1up   AVLTree induction notes
  6. 6. July 1: AVLTrees; Hash Tables Motivation   pptx   pdf
  7. X. July 4: Holiday!
  8. 7. July 6: Hash Tables, Reading: Weiss, 5.1 - 5.5   pptx   pdf
  9. 8. July 8: Hash Tables, continued, Reading: Weiss, 5.3 - 5.4   pptx   pdf1up
  10. 9. July 11: Priority Queues, Reading: Weiss, 6.1 - 6.2   pptx   pdf
  11. 10. July 13: More Binary Heaps; Amortized Runtime, Reading: Weiss, 6.3   pptx   pdf1up
  12. 11. July 15: Amortized Runtime, Disjoint Sets, Reading: Weiss, 8.1-8.2, 8.7   pptx   pdf1up   amortized resizing
  13. 12. July 18: Union Find, Reading: Weiss 8.3-8.6   pptx   pdf1up
  14. 13. July 20: Midterm Review
  15. 14. July 22: Midterm (in class)
  16. 15. July 25: Intro to Graphs, Reading Weiss 9.1   pptx   pdf1up
  17. 16. July 27: Topological Sort and Graph Traversals, Dijkstra's, Reading Weiss 9.2, 9.3, 9.6   pptx   pdf1up
  18. 17. July 29: Dijkstra's Algorithm, Preserving Abstractions   pptx   pdf1up
  19. 18. Aug 1: Minimum Spanning Trees, Reading Weiss 9.5   pptx   pdf1up
  20. 20. Aug 3: Comparison Sorting, Reading Weiss 7.1 - 7.8   pptx   pdf1up
  21. 21. Aug 5: Beyond Comparison Sorting   pptx   pdf1up
  22. 22. Aug 8: Parallelism and Concurrency 1, Reading Professor Dan Grossman's Explanation   pptx   pdf
  23. 23. Aug 10: Parallelism and Concurrency 2   pptx   pdf   Dan's prefix sum slides
  24. 24. Aug 12: Problem Solving   unsolved   pptx   pd (with solution explanation) - note there are many ways to solve these problems, depending on the constraints. Keep in mind some of these answers would require further explanation of the algorithm on an exam.
  25. 25. Aug 15: Problem solving
  26. 26. Aug 17: Course Victory Lap / Final Review   pptx   pdf
  27. X. Aug 19: Final Exam
TA Sessions

Materials from TA Sessions

  • (Optional) TA review session will be held weekly on Thursdays from 2:00-3:00pm in EEB 125. Materials will be posted online.
  • Optional sections that cover certain topics more in depth from the lectures and may or may not have postable items.

    1. 1. June 23: Eclipse, Induction, Command line   Command line basics (pdf)
        Eclipse Download Link
        Java 8 Download link
        Induction review
        Simple Queue
        Smarter Queue
        Note, these classes are not adequately commented.
    2. 2. June 30: Asymptotic Analysis   Analysis review
        CountNodes note: should be T(n) = 1 + T(n-1)/2 instead of 1 + T(n/2), as we omit the root node.
    3. 3. July 7: More Big-O   No material
    4. 4. July 14: Hashing, rotations, splay trees   slides
    5. 5. July 21: No review session. Midterm review IN CLASS JULY 20
    Homeworks

    Homework Assignments

    Dropbox turn-in for programming assignments

    Homework 0: on-line survey worth 0 points, "due" Friday, June 24

    Exams

    Midterm: July 22nd, Friday (in class)   solved

    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
  • Final: August 19th, Friday (in class)   solved

    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
  • Old Finals

  • 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, the most recent version of the language. So if installing Java on your own machine, you can get Java 7 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 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.

    For the material on parallelism in lectures 21 and 22 (and much more we did not have time for), see these notes written by UW Professor, Dan Grossman. We covered the material in Sections 2.1-2.3, 3.1-3.3, 3.5 and 4.1-4.3 (except the last two paragraphs of 4.1.3).

    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.

    Valid CSS! Valid XHTML 1.1