CSE 373: Data Structures and Algorithms, Spring 2014

Course Info

Course Information and Policies

Lecture: Monday, Wednesday, Friday 2:30-3:20 JHN 102

Optional TA-led sections: Tuesday/Thursday 4.30-5.20pm, MUE 153
Optional TA-led sections will be held most but not all weeks and will be announced in advance

Office Hours:
  Nicki Dell, Tuesdays 10:30-11:20AM Allen Center 214 + by appointment + try stopping by at my office (Allen Center 214 or 606)

  Nicholas Shahan, Wednesdays 11.30-12.20 Allen Center 218
  Rama Gokhale, Thursdays 11.30-12.20 Allen Center 218
  Luyi Lu, Fridays 11.30-12.20 Allen Center 220
  Megan Hopp, Mondays 10:00-10:50 Allen Center 220
  David Swanson, Wednesdays 3.30-4.20 Allen Center 220
  Sam Wilson, Tuesdays 2.30-3.20 Allen Center 220
  Yuanwei Liu, Thursdays 10.30-11.20 Allen Center 218

Contact Info

Contact Information

Course Email List (mandatory): 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: Nicki Dell, nixdell@cs.washington.edu

  TA: Luyi Lu, luluyi@cs.washington.edu
  TA: Nicholas Shahan, nshahan@cs.washington.edu
  TA: Rama Gokhale, ramag@cs.washington.edu
  TA: Megan Hopp, hoppm@cs.washington.edu
  TA: David Swanson, swansond@cs.washington.edu
  TA: Sam Wilson, samw11@cs.washington.edu
  TA: Yuanwei Liu, yuanwl@cs.washington.edu

Course Discussion Board (optional but encouraged)

Anonymous Feedback (goes only to the instructor)

Link to course evaluation

Calendar

Calendar

View the course calendar here.
Lectures

Lecture Materials

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

  1. March 31: Course Introduction; ADTs; Stacks and Queues (Weiss 3.6, 3.7)   pptx   pdf
  2. April 2: Proof by Induction (Weiss 1.2, another explanation here, Khan academy video here)   pptx   pdf
  3. April 2: Powers of Two (interesting (old but cool!) video on exponential growth here)   pptx   pdf
  4. April 4: Math Review; Start Algorithm Analysis (Weiss 1.2, 2.1-2.3)   pptx   pdf   excel data to play with (xlsx)
  5. April 7: Asymptotic Analysis (Weiss 2.1-2.4)   pptx   pdf
  6. April 9: Dictionaries; Binary Trees (Weiss 4.8; 4.1-4.3)   pptx   pdf
  7. April 11: Binary Search Trees (Weiss 4.1-4.3)   pptx   pdf
  8. April 14: AVL Trees (Weiss 4.4)   pptx   pdf
  9. April 16: AVL Trees and Priority Queues (Weiss 6.1-6.4)   pptx   pdf
  10. April 18: Binary Heaps (Weiss 6.1-6.4)   pptx   pdf
  11. April 21: Disjoint Sets and Union-Find (Weiss 8.1-8.7)   pptx   pdf
  12. April 23: Union Find (Weiss 8.3-8.6)   pptx   pdf
  13. April 25: Amortized Analysis and Memory Hierarchy   pptx   pdf
  14. April 28: Hash Tables (Weiss 5.1-5.6)   pptx   pdf
  15. April 30: Hash Collisions (Weiss 5.1-5.6)   pptx   xlsx   txt
  16. May 2: Introduction to Graphs (Weiss 9.1)   pptx   pdf
  17. May 5: Topological Sort and Graph Traversals (Weiss 9.2, 9.3.1, 9.6)   pptx   pdf
  18. May 7: Dijkstra's Algorithm (Weiss 9.3)   pptx   pdf
  19. May 9: Midterm
  20. May 12: More Dijkstra's Algorithm (Weiss 9.5)   pptx   pdf
  21. May 14: Dijkstra's Algorithm and Spanning Trees (Weiss 9.5)   pptx   pdf
  22. May 16: Minimum Spanning Trees (Prim's and Kruskal's Algorithms) (Weiss 9.5)   pptx   pdf
  23. May 19: Comparison Sorting (Weiss 7.1-7.8)   pptx   pdf
  24. May 21: More Sorting (Weiss 7.1-7.8)   pptx   pdf   visualizations
  25. May 23: Beyond Comparison Sorting and More (Weiss 7.9, 7.11-7.12)   pptx   pdf
  26. May 26: No Class, Memorial Day
  27. May 28: P vs. NP and NP-Completeness (Weiss 9.4, 9.7, 10.3, 10.4)   pptx   pdf
  28. May 30: Programming Languages   pptx   pdf
  29. June 2: Multithreading and Fork-Join Parallelism (Sections 2, 3 of these notes)   pptx   pdf
  30. June 4: Parallel Reductions, Maps, and Algorithm Analysis (Sections 3, 4 of these notes)   pptx   pdf
  31. June 6: Final exam review, Course Victory Lap   pptx   pdf
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. April 3rd: Eclipse, Java basics, and Sox (Led by David and Nicholas)
  2. April 8th: More help with Homework 1 (eclipse, java and sox) (Led by Megan and Rama)
  3. April 10: Proof by Induction and Asymptotic Analysis   pptx   pdf
  4. April 15th: More help with Homework 2   Worksheet   Solutions   (excluding problem 6 which was too similar to a homework question)
  5. April 17th: Binary Search Trees and AVL Trees   Worksheet   Solutions
  6. April 22nd: Priority Queues and Binary Heaps   docx
  7. April 24th: Disjoint Sets and Union Find
  8. April 29th: Extra help with Homework 3
  9. May 1st: Hashing   Worksheet
  10. May 6th: Midterm Review   pdf
  11. May 8th: Midterm Review
  12. May 13th: Extra help with Homework 4   Extra Help Notes
  13. May 15th: More Homework 4 help
  14. May 20th: Dijkstra's Algorithm and Minimum Spanning Trees   Unsolved   Solved
  15. May 22nd: Comparison Sorting
  16. May 27th: Extra help with Homework 5
  17. June 3rd: Extra help with Homework 6
  18. June 5th: Final exam review
Homeworks

Homework Assignments

Electronic turn-in for programming assignments

Exams

Midterm: Friday May 9 in class   information

Final exam: Tuesday, June 10, 2014, 2.30-4.20 pm, JHN 102   information

Software/Books

Software and Textbook Information

The programming assignments will use Java. We will use Java 7, the most recent version of the language. So if installing Java on your own machine, you can get Java 7 from http://jdk7.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.

Here are some interesting, usful, 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 and Dan Grossman.

Valid CSS! Valid XHTML 1.1