# Data Structures and Parallelism

University of Washington, Winter 2020

## HW 6: A* Search and EX 4: Society

HW 6: A* Search and EX 4: Society were released earlier today. We’ve also released HW 9: Seam Carving. It won’t be due until the end of the quarter. (Autograder not ready until later.)

The midterm exam will be graded over the weekend. For this week’s charrette, complete the Midterm Exam (Solution) in a group, discuss your problem solving process, and submit a completed version to Gradescope.

Over the last few weeks, we’ve learned how to solve problems using a variety of data structures and algorithm templates. Next week, we’ll explore how to apply these algorithm ideas through a case study of **sorting**, one of the most well-studied problems in computer science. Sorting is a critical operation in many areas of computer science with several surprising analogies and connections to the data structures concepts we’ve learned.

### **7** Comparison Sorts

## 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
- Jan 30
**Section**Beyond Trees- Jan 31
**HW 4 due**Priority Queues**HW 5 out**Point Sets**EX 3 out**Data Structures

### **5** Graph Data Type

- Feb 3
- Feb 4
**EX 2 due**Heaps- Feb 5
- Feb 6
**Section**Graphs- Feb 7
**HW 5 due**Point Sets

### **6** Midterm Exam

- Feb 10
- Feb 11
**EX 3 due**Data Structures- Feb 12
- Feb 13
**Section**Midterm Review- Feb 14
**HW 6 out**A* Search**HW 9 out**Seam Carving**EX 4 out**Society

### **7** Comparison Sorts

### **8** Optimizing Algorithms

- Feb 24
- Feb 25
**EX 4 due**Society- Feb 26
- Feb 27
**Section**Sorting Algorithms- Feb 28
Parallel Algorithm Analysis

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

### **9** Parallel Algorithms

- Mar 2
Multi-Pass Parallel Algorithms

- Mar 3
**EX 5 due**Sorting- Mar 4
Concurrency and Mutual Exclusion

- Mar 5
**Section**Parallel Algorithms- Mar 6
Race Conditions and Deadlock

**HW 8 due**Contraction Hierarchies**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