# Data Structures and Algorithms

University of Washington, Autumn 2019

## Welcome to CSE 373

Complete the Welcome Survey by noon Wed, Sep 25 before lecture for one extra credit point.

Note that all course information is subject to change through the first week of instruction.

## Calendar

### **1** Abstract Data Types

- Sep 25
**HW 1 out**LinkedIntList- Sep 26
**Section**Abstract Data Types- Sep 27
Stacks and Queues

### **2** Correctness and Efficiency

- Sep 30
Testing and Debugging

- Oct 1
**HW 1 due**LinkedIntList**HW 2 out**Deques- Oct 2
Algorithm Analysis I

- Oct 3
**Section**Algorithm Analysis- Oct 4
Algorithm Analysis II

### **3** Optimizing Trees

- Oct 7
Sets, Maps, and BSTs

- Oct 8
**HW 2 due**Deques**HW 3 out**Autocomplete- Oct 9
B-Trees

- Oct 10
**Section**Trees- Oct 11
Red-Black Trees

### **4** Beyond Trees

- Oct 14
Priority Queues and Heaps

- Oct 15
**HW 3 due**Autocomplete**HW 4 out**Heap- Oct 16
Hashing

- Oct 17
**Section**Heaps and Hashing- Oct 18
Prefix Operations and Tries

### **5** Midterm Exam

- Oct 21
Multi-Dimensional Data

- Oct 22
**HW 4 due**HeapMidterm Exam Study Guide

- Oct 23
Midterm Review

- Oct 24
**Section**Midterm Review- Oct 25
Midterm Exam

### **6** Graph Data Type

- Oct 28
Tree and Graph Traversals

- Oct 29
**HW 5 out**k-d Tree- Oct 30
Graph Implementations

- Oct 31
**Section**Graphs- Nov 1
Shortest Paths

### **7** Graph Algorithms

- Nov 4
Minimum Spanning Trees

- Nov 5
**HW 5 due**k-d Tree**HW 6 out**A* Search- Nov 6
Disjoint Sets

- Nov 7
**Section**Graph Algorithms- Nov 8
Software Engineering I

### **8** Comparison Sorts

- Nov 12
**HW 6 due**A* Search**HW 7 out**HuskyMaps Server- Nov 13
Comparison Sorts

- Nov 14
**Section**Comparison Sorts- Nov 15
Quicksort

### **9** Beyond Comparison Sorts

- Nov 18
Optimizing Quicksort

- Nov 19
**HW 7 due**HuskyMaps Server**HW 8 out**Seam Carving- Nov 20
Sorting and Algorithm Bounds

- Nov 21
**Section**Faster Sorts- Nov 22
Radix Sorts

### **10** Theoretical Foundations

- Nov 25
Reductions and Decomposition

- Nov 27
Computational Complexity

### **11** The Real World

- Dec 2
Data Structures vs. Algorithms

- Dec 3
**HW 8 due**Seam CarvingFinal Exam Study Guide

- Dec 4
Software Engineering II

- Dec 5
**Section**Final Review- Dec 6
Summary