# CSE373 Summer 2016

# 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 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 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)

## Lecture Materials

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

- 1. June 20: Course Introduction; ADTs; Stacks and Queues pptx pdf1up
- 2. June 22: Math Review; Algorithm Analysis; Induction pptx pdf1up induction notes
- 3. June 24: Asymptotic Analysis, Reading:
**Weiss, Chapter 2**pptx pdf recurrence relation notes Big-O example - 4. June 27: Dictionaries; Binary Search Trees
**No reading**pptx pdf1up - 5. June 29:
*More BSTs; AVLTrees*, Reading:**Weiss, 4.4**pptx pdf1up AVLTree induction notes - 6. July 1: AVLTrees; Hash Tables Motivation pptx pdf
- X. July 4: Holiday!
- 7. July 6: Hash Tables, Reading:
**Weiss, 5.1 - 5.5**pptx pdf - 8. July 8: Hash Tables, continued, Reading:
**Weiss, 5.3 - 5.4**pptx pdf1up - 9. July 11: Priority Queues, Reading:
**Weiss, 6.1 - 6.2**pptx pdf - 10. July 13: More Binary Heaps; Amortized Runtime, Reading:
**Weiss, 6.3**pptx pdf1up - 11. July 15: Amortized Runtime, Disjoint Sets, Reading:
**Weiss, 8.1-8.2, 8.7**pptx pdf1up amortized resizing - 12. July 18: Union Find, Reading:
**Weiss 8.3-8.6**pptx pdf1up - 13. July 20: Midterm Review
- 14. July 22:
**Midterm (in class)** - 15. July 25: Intro to Graphs, Reading
**Weiss 9.1**pptx pdf1up - 16. July 27: Topological Sort and Graph Traversals, Dijkstra's, Reading
**Weiss 9.2, 9.3, 9.6**pptx pdf1up - 17. July 29: Dijkstra's Algorithm, Preserving Abstractions pptx pdf1up
- 18. Aug 1: Minimum Spanning Trees, Reading
**Weiss 9.5**pptx pdf1up - 20. Aug 3: Comparison Sorting, Reading
**Weiss 7.1 - 7.8**pptx pdf1up - 21. Aug 5: Beyond Comparison Sorting pptx pdf1up
- 22. Aug 8: Parallelism and Concurrency 1, Reading
**Professor Dan Grossman's Explanation**pptx pdf - 23. Aug 10: Parallelism and Concurrency 2 pptx pdf Dan's prefix sum slides
- 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. Aug 15: Problem solving
- 26. Aug 17: Course Victory Lap / Final Review pptx pdf
- X. Aug 19: Final Exam

## 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. 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. 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. July 7: More Big-O
No material

- 4. July 14: Hashing, rotations, splay trees
slides

- 5. July 21: No review session. Midterm review
**IN CLASS JULY 20**

## Homework Assignments

Dropbox turn-in for programming assignments

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

- Homework 1 due 11PM, Friday July 1
- Homework 2: docx pdf due 11PM, Friday July 8 (catalyst dropbox)
- Homework 3 due 11PM, Tuesday July 19. Required files: hw_TextAssociator.zip
- Homework 4 due 11PM, Friday August 5
- Homework 5 due 11PM, Monday August 15 (The last day for turnin is Tuesday August 16)

## Exams

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

Practice Midterms:

Final: August 19th, Friday (in class) solved

Practice Resources for final:

Old Finals