# Data Structures and Parallelism

University of Washington, Winter 2020

## HW 3: Autocomplete and EX 1: Asymptotics

HW 3: Autocomplete and EX 1: Asymptotics were released earlier today. Autocomplete marks the first of five data structures and algorithms that we’ll be building for HuskyMaps.

For additional practice on week 2 concepts, refer to the Extra Practice Problems from section and the study guides that accompany each lecture.

- Iterative Algorithm Analysis Study Guide
- Recursive Algorithm Analysis Study Guide
- Sets, Maps, and BSTs Study Guide

Next week, we’ll apply the **Algorithm Design Process** to optimize binary search trees and avoid worst-case runtime. We’ll start by reinventing B-trees, a family of search trees that grow from the root rather than the leaves!

### **3** Optimizing Trees

- Jan 22
- Jan 23
**Section**Search Trees- Jan 24
**HW 3 due**Autocomplete**HW 4 out**Priority Queues**EX 2 out**Heaps

## Calendar

### **1** Abstract Data Types

- Jan 6
**HW 1 out**LinkedIntList- Jan 8
- Jan 9
**Section**Abstract Data Types- Jan 10
**HW 1 due**LinkedIntList**HW 2 out**Deques

### **2** Algorithm Analysis

- Jan 13
- Jan 15
- Jan 16
**Section**Algorithm Analysis- Jan 17
**HW 2 due**Deques**HW 3 out**Autocomplete**EX 1 out**Asymptotics

### **3** Optimizing Trees

- Jan 22
- Jan 23
**Section**Search Trees- Jan 24
**HW 3 due**Autocomplete**HW 4 out**Priority Queues**EX 2 out**Heaps

### **4** Beyond Trees

- Jan 27
- Jan 28
**EX 1 due**Asymptotics- Jan 29
Multi-Dimensional Data

- Jan 30
**Section**Beyond Trees- Jan 31
Hashing

**HW 4 due**Priority Queues**HW 5 out**Point Sets**EX 3 out**Data Structures

### **5** Graph Data Type

- Feb 3
Tree and Graph Traversals

- Feb 4
**EX 2 due**Heaps- Feb 5
Graph Implementations

- Feb 6
**Section**Graphs- Feb 7
Minimum Spanning Trees

**HW 5 due**Point Sets

### **6** Midterm Exam

- Feb 10
Shortest Paths

- Feb 11
**EX 3 due**Data Structures- Feb 12
Reductions and Decomposition

- Feb 13
**Section**Midterm Review- Feb 14
Software Engineering

Midterm Exam

**HW 6 out**A* Search**EX 4 out**Society

### **7** Comparison Sorts

- Feb 19
Comparison Sorts

- Feb 20
**Section**Comparison Sorts- Feb 21
Quicksort

**HW 6 due**A* Search**HW 7 out**HuskyMaps Server**EX 5 out**Sorting

### **8** Optimizing Algorithms

- Feb 24
Sorting and Algorithm Bounds

- Feb 25
**EX 4 due**Society- Feb 26
Parallel Algorithms

- Feb 27
**Section**Optimizing Algorithms- Feb 28
Parallel Contraction

**HW 7 due**HuskyMaps Server**HW 8 out**Contraction Hierarchies**EX 6 out**Parallelism

### **9** Parallel Algorithms

- Mar 2
Parallel Algorithm Analysis

- Mar 3
**EX 5 due**Sorting- Mar 4
Parallel Sorting

- Mar 5
**Section**Parallel Algorithms- Mar 6
Synchronization Issues

**HW 8 due**Contraction Hierarchies**HW 9 out**Seam Carving**EX 7 out**Concurrency

### **10** Unsolved Problems

- Mar 9
Programming the World

- Mar 10
**EX 6 due**Parallelism- Mar 11
Computational Complexity

- Mar 12
**Section**Final Review- Mar 13
Final Review

**HW 9 due**Seam Carving

### **11** Final Exam

- Mar 17
**EX 7 due**Concurrency- Mar 19
Final Exam