Link

Data Structures and Parallelism

University of Washington, Winter 2020

Jan 17

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.

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!

All Announcements

3 Optimizing Trees

Jan 22

B-Trees

Reading, Handout

Jan 23

Section Search Trees

Jan 24

Priority Queues and Heaps

Reading, Handout

HW 3 due Autocomplete

HW 4 out Priority Queues

EX 2 out Heaps


Calendar

3 Optimizing Trees

Jan 22

B-Trees

Reading, Handout

Jan 23

Section Search Trees

Jan 24

Priority Queues and Heaps

Reading, Handout

HW 3 due Autocomplete

HW 4 out Priority Queues

EX 2 out Heaps

4 Beyond Trees

Jan 27

Left-Leaning Red-Black Trees

Reading, Handout

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

Web App

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

Computational Literacy for All

Optional Reading

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