CSE373 Summer 2017
Data Structures and Algorithms
Course Information and Policies
- Policies on Collaboration and Academic Integrity
- Policies on Grading
- Programming Guidelines
- Written-Homework Guidelines
| Lectures: | Monday, Wednesday, Friday 10:50-11:50 THO 101 |
| Sections: | Thursday 10:50-11:50 THO 101, or |
| Thursday 12:00-1:00 JHN 075 |
Office Hours: hosted in the 3rd floor breakout in CSE (whiteboard area by the staircase)
- Dorothy Truong: Monday 2:00-3:00pm
- Vlad Shamalov: Tuesday 10:30-11:30am
- Lilian de Greef: Tuesday 2:00-3:00pm
- Kyle Thayer: Wednesday 1:30-2:30pm & Friday 9:30-10:30am
- Ben Jones: Thursday 1:00-3:00pm
- Anupam Gupta: Friday 1:00-2:00pm
Contact Information
Question on homework or course material? Find or start a post on Piazza!
When posting to the class, leave out any code or parts of a solution to the homework (even if it’s incomplete). For private questions (e.g. grades, code- or solution-specific questions, etc.), post to the instructors only. If you're feeling shy about posting something to the class, you can always post anonymously.
Because Piazza is highly catered to getting you help fast and efficiently from classmates, TAs, and the instructor, you’ll get a faster response there than if you email any of us individually. This is also true for private posts, as both TAs and instructors can see them.
https://piazza.com/washington/summer2017/cse373
For Lilian's eyes only? Email me with "[CSE 373]" at the beginning of the subject line. I will check my email at least once a day, so you can expect a response to instructor-only emails (addressed to ldegreef [at] cs.washington.edu) within 24 hours.
Course Email List: You should receive email sent to the course mailing list regularly. Any important announcements will be sent to this list. More info
Anonymous Feedback (goes only to the instructor)
Lecture Materials
Material in the future naturally subject to change in terms of coverage or schedule
-
June 19: Course Introduction, ADTs, Stacks and Queues
[ pptx ] [ pdf ] [ Annotated pdf ] -
June 21: Finish up Queues, Start Asymptotic Analysis
[ pptx ] [ pdf ] [ Annotated pdf ] -
June 23: Asymptotic Analysis: Math Review, Induction, Recusive Functions (Reading: Weiss Ch2)
[ pptx ] [ pdf ] [ Annotated pdf ] [ Recurrence Relation Example ] -
June 26: Code Style; Asymptotic Analysis: Recurrence Relations; Big- and little- O, Omega, and Theta. (Reading: Weiss Ch2)
[ pptx ] [ pdf ] [ Annotated pdf ] -
June 28: Big- and little- O, Omega, and Theta; Asymptotic Analysis: Average Case using Amortized Analysis
[ pptx ] [ pdf ] [ Annotated pdf ] -
June 30: Finish Amortized Analysis; Dictionary ADT; Intro to Hash Tables (Reading: Weiss Ch5.1 - 5.2)
[ pptx ] [ pdf ] [ Annotated pdf ] - July 3: Unofficial extended July 4th weekend 🇺🇸 🎉 Go have fun!
- July 5: Hash Table Collisions (Reading: Weiss Ch5.3 - 5.4.2)
[ pptx ] [ pdf ] [ Annotated pdf ] - July 7: Finish Hash Table Collisions (Weiss Ch5.4.3 - 5.5), Intro to Trees (Weiss Ch4.1 - 4.2)
[ pptx ] [ pdf ] [ Annotated pdf ] [ Quadratic Probing Proof ] - July 10: Binary Search Trees (Reading: Weiss Ch4.3)
[ pptx ] [ pdf ] [ Annotated pdf ] - July 12: AVL Trees (Reading: Weiss Ch4.4)
[ pptx ] [ pdf ] [ Annotated pdf ] - July 14: Finish BSTs; Priority Queues; Begin Binary Heaps (Reading: Weiss Ch6.1 - 6.2)
[ pptx ] [ pdf ] [ Annotated pdf ] [ Minimum nodes in an AVL Tree ] - July 17: Binary Heaps (Reading: Weiss Ch6.3)
[ pptx ] [ pdf ] [ Annotated pdf ] - July 19: Finish Binary Heaps (Reading: Weiss Ch6.3)
[ pptx ] [ pdf ] [ Annotated pdf ] - July 21: Midterm Exam
-
July 24: Intro to Graphs (Reading: Weiss Ch9.1)
[ pptx ] [ pdf ] [ Annotated pdf ] -
July 26: Graph Traversals: (BFS, DFS, Topological Sort) (Reading: Weiss Ch9.2, 9.3.1, 9.6)
[ pptx ] [ pdf ] [ Annotated pdf ] -
July 28: Dijkstra's Algorithm (shortest path in graphs)(Reading: Weiss Ch9.3)
[ pptx ] [ pdf ] [ Annotated pdf ] -
July 31: Finish Dijkstra's Algorithm; Preserving Abstractions (Software Design)
[ pptx ] [ pdf ] [ Annotated pdf ] -
Aug 2: Minimum Spanning Trees (Prim's and Kruskal's Algorithms) (Reading: Weiss Ch9.5)
[ pptx ] [ pdf ] [ Annotated pdf ] -
Aug 4: Comparison Sorting (Reading: Weiss Ch7.1 - 7.6)
[ pptx ] [ pdf ] [ Annotated pdf ] -
Aug 7: More Sorting (Reading: Weiss Ch7.7 - 7.8, 7.11 - 7.12)
[ pptx ] [ pdf ] [ Annotated pdf ] -
Aug 9: Finish Sorting; P vs NP (Reading: Weiss Ch9.7)
[ pptx ] [ pdf ] [ Annotated pdf ] -
Aug 11: Begin Parallelism (Reading: Prof Dan Grossman's explanation)
[ pptx ] [ pdf ] [ Annotated pdf ] -
Aug 14: Parallelism part 2: Map, Reduce, Analysis (Reading: Prof Dan Grossman's explanation)
[ pptx ] [ pdf ] [ Annotated pdf ] -
Aug 16: Course Victory Lap, Practice with Design Decisions & Algorithm Solving
[ pptx ] [ pdf ] [ Annotated pdf ] - Aug 18: Final Exam (Good luck everyone!)
Materials from TA Review Sessions
Sections (i.e. TA Review Sessions) are optional but highly encouraged, and will be held weekly. They cover certain topics more in depth from the lectures, are an additional opportunity to practice or ask questions about material, and may or may not have postable material. When possible, review sheets and practice problems will be posted here. Solutions to the problems are covered in Section.
There are two section offerings on Thursdays.
Choose to attend either the Section at 11:00-11:50 in JHN 026 *or* the Section at 12:00-12:50 in JHN 075.
| Sections: | Thursday 11:00-11:50 JHN 026, or |
| Thursday 12:00-12:50 JHN 075 |
-
June 22: CSE 143 Refresher (Java, Stacks, Queues, and Trees)
- 143 Review Document
- Practice Problems (solutions covered in section)
-
June 29: Asymptotic Analysis
- Practice Problems (solutions covered in section)
-
July 6th: Hash Tables
- Practice Problems (solutions covered in section)
-
July 13th: AVL Trees and BSTs
- Practice Problems (solutions covered in section)
-
July 20th: Midterm Review
- Practice Problems (solutions covered in section)
- Materials we've covered so far (note: it is not an exhaustive list)
-
July 27th: Graphs
- Practice Problems (solutions covered in section)
-
July 27th: More Graphs - Shortest Paths, Minimum Spanning Trees, and General Review
- Practice Problems (solutions covered in section)
-
August 10th: Sorting Algorithms
- Practice Problems (solutions covered in section)
-
August 17th: Final Review
- Practice Problems (solutions covered in section)
- (pdf) Materials we've covered (3 pages. Note: it is not an exhaustive list)
- (doc) Materials we've covered (3 pages. Note: it is not an exhaustive list)
- (pdf) Practice Data Structures Design Decision Problems (Note: answers included but not complete, and these problems do not practice choosing algorithms)
- (doc) Practice Data Structures Design Decision Problems (Note: answers included but not complete, and these problems do not practice choosing algorithms)
Homework Assignments
Dropbox turn-in for homework assignments
- Homework 0: Self Introductions (takes 5 minutes, ungraded), due 11:00pm, Monday June 19
- Reading: the first 10 pages of Code Complete chapter 32 (only required reading! Book also available in UW libraries) due 10:50am, Monday June 26
- Homework 1: Sound Blaster! due 5:00pm, Wednesday June 28
- Homework 2: Asympotic Analysis [ docx ] [ pdf ] due 5:00pm, Thursday July 6 (also via catalyst dropbox)
- Homework 3: Text Associator [assignment] [code] [partners survey] due 5:00pm, Friday July 14
- Homework 4: Graphs and Shortest Paths [partners survey] due 5:00pm, Friday August 4
- Homework 5: Sort Explorer due 5:00pm, Friday August 11
Exams
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
Practice Resources for final:
Old Midterm 2's Old FinalsSoftware and Textbook Information
Software
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.
Data Structures and Algorithms Textbook
Readings from the textbook, although not required, often provide a second explanation for material covered in class. Relevant chapters are posted on the course website under lecture materials with each week.
The textbook is Data Structures and Algorithm Analysis in Java, Mark Allen Weiss, 3rd Edition, 2011, ISBN: 0132576279.
Here are links to the Errata
and Code from the book
You may also reference the 2nd Edition (possibly with misaligned chapters/sections for readings), ISBN: 0321370139.
Here are links to the 2nd edition's Errata
and Code from the book
The textbook is also available for 4 hour loan at the Engineering library.
Java Resources
Here are slides from a previous quarter which go through your expected Java knowledge prior to taking this course.
You can find a lot of great Java resources online!
- API Reference - used by programmers all the time when coding!
- General Documetation
- CodingBat/Java - a browser-based way to practice and get comfortable with Java
- An "intro to the Java language" tutorial
- One favorite Java syntax reference
- Wikipedia's Java syntax reference
There are a variety of (more than) sufficient book-style references. One recommended option is Core Java(TM), Volume I--Fundamentals 9th Edition, Cay S. Horstmann and Gary Cornell, 2002, ISBN: 0137081898.
Other Reference Materials
For the material on parallelism for their lectures in August (and much more we don't have time for), see these notes written by UW Professor, Dan Grossman. In lecture, we aim to cover 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)
Access and Accommodations
Your experience in this class is important to me. If you have already established accommodations with Disability Resources for Students (DRS), please communicate your approved accommodations to me at your earliest convenience so we can discuss your needs in this course.
If you have not yet established services through DRS, but have a temporary health condition or permanent disability that requires accommodations (conditions include but not limited to; mental health, attention-related, learning, vision, hearing, physical or health impacts), you are welcome to contact DRS at 206-543-8924 or uwdrs@uw.edu or disability.uw.edu. DRS offers resources and coordinates reasonable accommodations for students with disabilities and/or temporary health conditions. Reasonable accommodations are established through an interactive process between you, your instructor(s) and DRS. It is the policy and practice of the University of Washington to create inclusive and accessible learning environments consistent with federal and state law.
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, Lauren Milne, and Hunter Zahn.
