CSE373 FALL 2015
Data Structures and Algorithms
Course Information and Policies
- Policies on Collaboration and Academic Integrity
- Policies on Grading
- Programming Guidelines
- Written-Homework Guidelines
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 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)
Lecture Materials
Material in the future naturally subject to change in terms of coverage or schedule
- 1. Sep 30: Course Introduction; ADTs; Stacks and Queues pptx pdf1up
- 2. Oct 2: Math Review; Algorithm Analysis pptx pdf1up
- 3. Oct 5: Asymptotic Analysis, Reading: Weiss, Chapter 2 pptx pdf
- 4. Oct 7: Dictionaries; Binary Search Trees No reading pptx pdf1up
- 5. Oct 9: AVL Trees, Reading: Weiss, 4.4 pptx pdf1up
- 6. Oct 12: Hash Tables, Reading: Weiss, 5.1 - 5.5 pptx pdf
- 7. Oct 14: Hash Collisions, Reading: Weiss, 5.3 - 5.4 pptx pdf
- 8. Oct 16: Priority Queues, Reading: Weiss, 6.1 - 6.2 pptx pdf1up
- 9. Oct 19: More Binary Heaps and Amortized Runtime, Reading: Weiss, 6.3 pptx pdf Supplmenet pptx Supplement pdf
- 10. Oct 21: Disjoing Sets, Reading: Weiss, 8.1-8.2, 8.7 pptx pdf1up
- 11. Oct 23: Union Find, Up-tree, Reading: Weiss, 8.3-8.6 pptx pdf1up
- 12. Oct 26: Introduction to Graphs, Reading: Weiss 9.1 pptx pdf1up
- 13. Oct 28: Topological Sort and Graph Traversal, Reading Weiss 9.2, 9.3.1, 9.6 pptx pdf1up
- 14. Oct 30: Djikstras Algorithm, Reading Weiss 9.3 pptx pdf1up
- 15. Nov 2: Perserving Abstractions pptx pdf1up
- 16. Nov 4: Midterm Review
- X. Nov 6: Midterm!
- 17. Nov 9: Minimum Spanning Trees, Reading Weiss 9.5 pptx pdf1up
- X. Nov 11: Veteran's Day, no class or Office hours
- 18. Nov 13: Comparison Sorting, Reading Weiss 7.1-7.8 pptx pdf1up
- 20. Nov 16: Beyond Comparison Sorting pptx pdf1up
- 21. Nov 18: Complexity (no material or reading, just sit back and enjoy!)
- 22. Nov 20: Parallelism and Concurrency, Reading Professor Dan Grossman's Explanation pptx pdf
- 23. Nov 23: Parallelism and Concurrency continued, Map and Reduce, Reading see readaing from Nov 22 pptx pdf
- 24. Nov 25: Introduction to python and the Traveling Salesman Problem, No reading
- 25. Nov 30: Introduction to Artificial Inteligence, Minimax, No Reading pptx pdf
- 26. Dec 2: Problem Solving 101, Interview Questions, Time Constraint pptx pdf problem set and solutions.pdf
- 26. Dec 4: Problem Solving 102, Interview Questions, Optimization
- 27 December 7: Locality and Memory Hierarchy pdf pptx
- 27 December 11: Course Victory Lap and Review pdf pptx
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. Oct 01: Eclipse, Java basics
Command line basics (pdf)
Java review and refresher (pdf)
Eclipse Download Link
Java 8 Download link - 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)
- 4. Oct 15: AVL Trees and Hashtables no materials
- 5. Oct 22: Homework 3, Uptrees, graphs no materials
- 7. November 5th, Midterm review, bring questions!
- 8. Nov 12: Immutabiltiy and Java Review Immutability slide deck 1 (pdf) Immutability slide deck 2 (pdf)
- 9. Dec 10. Final Review (Johnson 175 5:30 - 7:60pm) Class.java Student.java map_reduction.txt
Homework Assignments
Dropbox turn-in for programming assignments
Homework 0: on-line survey worth 0 points, "due" Friday, October 2
- Homework 1 due 11PM, Friday October 9
- Homework 2 pdf version due in the course Dropbox by Friday October 16
- Homework 3 due 11PM, Friday October 30. Required files: hw_TextAssociator.zip
- Homework 4 due 11PM, Wednesday November 18
- Homework 5 due 11PM, Monday November 30
- Homework 6 due 11PM, Friday December 11 (No late assignments accpeted for hw6!)
Exams
Midterm 1: November 6th, Friday (in class) solved
Practice Midterms:
Final exam: Tuesday December 15, 2:30-4:20PM Kane 220 solved
Practice Resources for final:
Old Finals
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.
- 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.
