# Data Structures and Algorithms

## University of Washington, Winter 2021

Data structures and algorithms are the foundational abstractions underlying all computer systems. Just as programming languages affect the way we compose programs, the design of abstractions affect the resulting values encoded within applications. In CSE 373, we will learn to **design, analyze, and critique** data structures and algorithms (and applications thereof).

- Design data structures and algorithms by implementing and maintaining invariants.
- Analyze the runtime and design values of data structures and algorithms.
- Critique the application of data structures and algorithms towards complex problems.

CSE 373 is organized around 3 motivating projects, weekly learning checkpoints, a video portfolio, and an open-ended research project.

## About

- Jan 4
**Introduction**- Jan 6
**Search Trees**- Identify a best/worst-case height BST and TST insertion order for given elements.
- Describe an application where a TST is better suited than a BST, and vice-versa.
- Explain in plain English the TST in-order traversal algorithm.

- Jan 7
**Section****Programming with Data Structures**- Jan 8
**Asymptotic Analysis**- Describe how asymptotic analysis and case analysis interact in runtime analysis.
- Identify big-theta, big-oh, and big-omega asymptotic bounds for a function.
- Given a program’s runtime plot, identify the tightest-possible asymptotic bounds.

## DNA Indexing

- Jan 11
**Recurrence Relations**- Identify a closed-form expression by unrolling a single-recurrence relation.
- Apply 1 + 2 + 3 + 4 + ⋯ and 1 + 2 + 4 + 8 + ⋯ to simplify an expression.
- Create recurrence diagrams to simplify recurrences and find an asymptotic bound.

- Jan 13
**2-3 Trees**- Identify element promotions during the 2-3 tree insertion process.
- Identify an insertion order that will increase the height of a 2-3 tree.
- Analyze the best-case and worst-case height in terms of 2/3-nodes.

- Jan 14
**Section****Algorithm Analysis**- Jan 15
**Left-Leaning Red-Black Trees**- Given a 2-3 tree, identify its corresponding LLRB tree (and vice-versa).
- Apply rotations and color flips for a single LLRB tree insertion.
- Using 1-1 correspondence, give the LLRB tree for a series of insertions.

- Jan 18
- Holiday
- Jan 20
**AVL Trees**- Compute the balance factor of a given node in a binary search tree.
- Identify valid AVL trees by checking the BST and AVL tree invariants.
- Apply rotations (line and kink cases) for a single AVL tree insertion.

- Jan 21
**Section****Balanced Search Trees**- Jan 22
**Binary Heaps**- Apply sink/swim operations to trace heap element insertion and removal.
- Given an arbitrary, unknown heap, identify possible nodes for the n-th element.
- Given an array index, find the parent, left child, and right child indexes.

## Content Moderation

- Jan 25
**Affordance Analysis**- Describe how abstractions embody values and structure social relations.
- Analyze an API to identify the affordances of a programming abstraction.
- Evaluate the affordances through critical examination of social relations.

- Jan 27
**Hash Tables**- Explain and trace hash table algorithms such as insertion and search.
- Evaluate how a hash table will behave in response to a given data type.
- Analyze the runtime of a hash table with a given bucket data structure.

- Jan 28
**Section****Heaps and Hashing**- Jan 29
**Memory and Caching**- Compare CPU, RAM, cache, and disk in terms of capacity and access time.
- Explain why arrays tend to be better than linked lists for spatial locality.
- Describe how B+ trees minimize disk accesses and trace the
`get`

operation.

- Feb 1
**Graph Data Type**- Identify the features and representation for an example graph or graph problem.
- Analyze the runtime of a graph representation as a function of vertices and edges.
- Analyze the affordances of a graph interface or operation for a particular problem.

- Feb 3
**Graph Traversals**- Trace and explain each data structure in BFS and DFS graph traversal.
- Analyze the runtime of a graph algorithm as a function of vertices and edges.
- Define an appropriate graph abstraction for a given image processing problem.

- Feb 4
**Section****Graph Traversals**- Feb 5
**Shortest Paths**- Trace and explain each data structure in Dijkstra’s shortest path algorithm.
- Explain why Dijkstra’s algorithm might not work on negative edge-weighted graphs.
- Analyze the affordances of shortest paths problems for real-world routing.

## Image Processing

- Feb 8
**Reduction Algorithms**- Explain the runtime for Dijkstra’s algorithm in terms of priority queue operations.
- Model a problem with nodes and edges to reduce it to a common graph problem.
- Give a topological sorting for a DAG and explain the DAG shortest paths algorithm.

- Feb 10
**Minimum Spanning Trees**- Identify a minimum spanning tree using both Prim’s and Kruskal’s algorithms.
- Compare and contrast the distTo map for Prim’s and Dijkstra’s algorithms.
- Analyze how applying a function to all edge weights affects the resulting MST.

- Feb 11
**Section****Graph Algorithms**- Feb 12
**Comparison Sorts**- Identify whether a sort is stable and give an example input for unstable sorts.
- Trace each iteration of selection sort, insertion sort, and heapsort.
- Explain the runtime for selection sort, insertion sort, and heapsort.

- Feb 15
- Holiday
- Feb 17
**Recursive Sorts**- Trace the recursive execution of merge sort and quicksort.
- Identify a valid partition and trace the in-place partitioning algorithm.
- Evaluate variations of quicksort pivot selection, partitioning, and subsorts.

- Feb 18
**Section****Sorting Algorithms**- Feb 19
**Algorithm Bounds**

## Research Project

- Feb 22
**Career Panel**