CSE373 FALL 2015

Data Structures and Algorithms

Course Info

Course Information and Policies

Lecture: Monday, Wednesday, Friday 2:30-3:20 KNE 220

Optional TA-led meetings: TBD Optional TA-led meetings will be held most but not all weeks and will be announced in advance

Office Hours:
  Instr: Kevin Quinn, Monday, 3:30-4:30 CSE 212
  TA: Eden Ghirmai : Wednesday 4:30 - 5:30 CSE 021
  TA: Megan Hopp : Thursday, 11:00 - 12:00 CSE 021
  TA: Andy Li : Tuesday, 9:30 - 11:30 CSE 218
  TA: Rahul Nadkarni : Tuesday, 2:00 - 3:00 CSE 218
  TA: Hunter Schafer : Thursday, 12:30 - 1:30 CSE 220
  TA: Rocne Scribner : Monday, 1:30 - 2:30 CSE 218
  TA: Yunyi Song : Friday, 9:30 - 10:30, CSE 218
  TA: Mauricio Vinagre Hernandez : Monday, 10:30 - 11:30 CSE 218
  TA: Hunter Zahn : Wednesday, 12:30 - 1:30pm CSE 218
  TA: Johnson Goh : Wednesday, 10:30 - 11:30pm CSE 021

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: Kevin Quinn: kchq@cs.washington.edu

  TA: Eden Ghirmai : ghirme@cs.washington.edu
  TA: Megan Hopp : hoppm@cs.washington.edu
  TA: Andy Li : boruil@cs.washington.edu
  TA: Rahul Nadkarni : rahuln@cs.washington.edu
  TA: Hunter Schafer : hschafer@cs.washington.edu
  TA: Rocne Scribner : rocnes@cs.washington.edu
  TA: Yunyi Song : bessieyy@cs.washington.edu
  TA: Mauricio Vinagre Hernandez : mvh92@cs.washington.edu
  TA: Hunter Zahn : hzahn93@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. Sep 30: Course Introduction; ADTs; Stacks and Queues   pptx   pdf1up
  2. 2. Oct 2: Math Review; Algorithm Analysis   pptx   pdf1up
  3. 3. Oct 5: Asymptotic Analysis, Reading: Weiss, Chapter 2   pptx   pdf
  4. 4. Oct 7: Dictionaries; Binary Search Trees No reading   pptx   pdf1up
  5. 5. Oct 9: AVL Trees, Reading: Weiss, 4.4   pptx   pdf1up
  6. 6. Oct 12: Hash Tables, Reading: Weiss, 5.1 - 5.5   pptx   pdf
  7. 7. Oct 14: Hash Collisions, Reading: Weiss, 5.3 - 5.4   pptx   pdf
  8. 8. Oct 16: Priority Queues, Reading: Weiss, 6.1 - 6.2   pptx   pdf1up
  9. 9. Oct 19: More Binary Heaps and Amortized Runtime, Reading: Weiss, 6.3   pptx   pdf   Supplmenet pptx   Supplement pdf
  10. 10. Oct 21: Disjoing Sets, Reading: Weiss, 8.1-8.2, 8.7   pptx   pdf1up
  11. 11. Oct 23: Union Find, Up-tree, Reading: Weiss, 8.3-8.6   pptx   pdf1up
  12. 12. Oct 26: Introduction to Graphs, Reading: Weiss 9.1   pptx   pdf1up
  13. 13. Oct 28: Topological Sort and Graph Traversal, Reading Weiss 9.2, 9.3.1, 9.6   pptx   pdf1up
  14. 14. Oct 30: Djikstras Algorithm, Reading Weiss 9.3   pptx   pdf1up
  15. 15. Nov 2: Perserving Abstractions   pptx   pdf1up
  16. 16. Nov 4: Midterm Review
  17. X. Nov 6: Midterm!
  18. 17. Nov 9: Minimum Spanning Trees, Reading Weiss 9.5   pptx   pdf1up
  19. X. Nov 11: Veteran's Day, no class or Office hours
  20. 18. Nov 13: Comparison Sorting, Reading Weiss 7.1-7.8   pptx   pdf1up
  21. 20. Nov 16: Beyond Comparison Sorting   pptx   pdf1up
  22. 21. Nov 18: Complexity (no material or reading, just sit back and enjoy!)
  23. 22. Nov 20: Parallelism and Concurrency, Reading Professor Dan Grossman's Explanation   pptx   pdf
  24. 23. Nov 23: Parallelism and Concurrency continued, Map and Reduce, Reading see readaing from Nov 22   pptx   pdf
  25. 24. Nov 25: Introduction to python and the Traveling Salesman Problem, No reading
  26. 25. Nov 30: Introduction to Artificial Inteligence, Minimax, No Reading   pptx   pdf
  27. 26. Dec 2: Problem Solving 101, Interview Questions, Time Constraint   pptx   pdf   problem set and solutions.pdf
  28. 26. Dec 4: Problem Solving 102, Interview Questions, Optimization
  29. 27 December 7: Locality and Memory Hierarchy   pdf   pptx
  30. 27 December 11: Course Victory Lap and Review   pdf   pptx
TA Sessions

Materials from TA Sessions

Optional sections that cover certain topics more in depth from the lectures and may or may not have postable items.

  1. 1. Oct 01: Eclipse, Java basics   Command line basics (pdf)
      Java review and refresher (pdf)
      Eclipse Download Link
      Java 8 Download link
  2. 2. Oct 08: Proof by Induction and Asymptotic Analysis   Asymptotic Runtimes questions (.txt)
      Asymptotic Runtimes answers (.txt)
      Example induction (pt1) (.jpg) Example induction (pt2 continued) (.jpg)
  3. 4. Oct 15: AVL Trees and Hashtables   no materials
  4. 5. Oct 22: Homework 3, Uptrees, graphs   no materials
  5. 7. November 5th, Midterm review, bring questions!
  6. 8. Nov 12: Immutabiltiy and Java Review   Immutability slide deck 1 (pdf)   Immutability slide deck 2 (pdf)
  7. 9. Dec 10. Final Review (Johnson 175 5:30 - 7:60pm)   Class.java   Student.java   map_reduction.txt
Homeworks

Homework Assignments

Dropbox turn-in for programming assignments

Homework 0: on-line survey worth 0 points, "due" Friday, October 2

Exams

Midterm 1: November 6th, 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 exam: Tuesday December 15, 2:30-4:20PM Kane 220   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