Link Search Menu Expand Document
CSE 373

Data Structures and Algorithms

University of Washington, Winter 2021

Kevin Lin he/him

kevinl@cs.uw.edu

Schedule a meeting

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).

  1. Design data structures and algorithms by implementing and maintaining invariants.
  2. Analyze the runtime and design values of data structures and algorithms.
  3. 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.

Read more…

About

Jan 4
Introduction
Jan 6
Search Trees
  1. Identify a best/worst-case height BST and TST insertion order for given elements.
  2. Describe an application where a TST is better suited than a BST, and vice-versa.
  3. Explain in plain English the TST in-order traversal algorithm.
Jan 7
SectionProgramming with Data Structures
Jan 8
Asymptotic Analysis
  1. Describe how asymptotic analysis and case analysis interact in runtime analysis.
  2. Identify big-theta, big-oh, and big-omega asymptotic bounds for a function.
  3. Given a program’s runtime plot, identify the tightest-possible asymptotic bounds.

DNA Indexing

Jan 11
Recurrence Relations
  1. Identify a closed-form expression by unrolling a single-recurrence relation.
  2. Apply 1 + 2 + 3 + 4 + ⋯ and 1 + 2 + 4 + 8 + ⋯ to simplify an expression.
  3. Create recurrence diagrams to simplify recurrences and find an asymptotic bound.
Jan 13
2-3 Trees
  1. Identify element promotions during the 2-3 tree insertion process.
  2. Identify an insertion order that will increase the height of a 2-3 tree.
  3. Analyze the best-case and worst-case height in terms of 2/3-nodes.
Jan 14
SectionAlgorithm Analysis
Jan 15
Left-Leaning Red-Black Trees
  1. Given a 2-3 tree, identify its corresponding LLRB tree (and vice-versa).
  2. Apply rotations and color flips for a single LLRB tree insertion.
  3. Using 1-1 correspondence, give the LLRB tree for a series of insertions.
Jan 18
Holiday
Jan 20
AVL Trees
  1. Compute the balance factor of a given node in a binary search tree.
  2. Identify valid AVL trees by checking the BST and AVL tree invariants.
  3. Apply rotations (line and kink cases) for a single AVL tree insertion.
Jan 21
SectionBalanced Search Trees
Jan 22
Binary Heaps
  1. Apply sink/swim operations to trace heap element insertion and removal.
  2. Given an arbitrary, unknown heap, identify possible nodes for the n-th element.
  3. Given an array index, find the parent, left child, and right child indexes.

Content Moderation

Jan 25
Affordance Analysis
  1. Describe how abstractions embody values and structure social relations.
  2. Analyze an API to identify the affordances of a programming abstraction.
  3. Evaluate the affordances through critical examination of social relations.
Jan 27
Hash Tables
  1. Explain and trace hash table algorithms such as insertion and search.
  2. Evaluate how a hash table will behave in response to a given data type.
  3. Analyze the runtime of a hash table with a given bucket data structure.
Jan 28
SectionHeaps and Hashing
Jan 29
Memory and Caching
  1. Compare CPU, RAM, cache, and disk in terms of capacity and access time.
  2. Explain why arrays tend to be better than linked lists for spatial locality.
  3. Describe how B+ trees minimize disk accesses and trace the get operation.
Feb 1
Graph Data Type
  1. Identify the features and representation for an example graph or graph problem.
  2. Analyze the runtime of a graph representation as a function of vertices and edges.
  3. Analyze the affordances of a graph interface or operation for a particular problem.
Feb 3
Graph Traversals
  1. Trace and explain each data structure in BFS and DFS graph traversal.
  2. Analyze the runtime of a graph algorithm as a function of vertices and edges.
  3. Define an appropriate graph abstraction for a given image processing problem.
Feb 4
SectionGraph Traversals
Feb 5
Shortest Paths
  1. Trace and explain each data structure in Dijkstra’s shortest path algorithm.
  2. Explain why Dijkstra’s algorithm might not work on negative edge-weighted graphs.
  3. Analyze the affordances of shortest paths problems for real-world routing.

Image Processing

Feb 8
Reduction Algorithms
  1. Explain the runtime for Dijkstra’s algorithm in terms of priority queue operations.
  2. Model a problem with nodes and edges to reduce it to a common graph problem.
  3. Give a topological sorting for a DAG and explain the DAG shortest paths algorithm.
Feb 10
Minimum Spanning Trees
  1. Identify a minimum spanning tree using both Prim’s and Kruskal’s algorithms.
  2. Compare and contrast the distTo map for Prim’s and Dijkstra’s algorithms.
  3. Analyze how applying a function to all edge weights affects the resulting MST.
Feb 11
SectionGraph Algorithms
Feb 12
Comparison Sorts
  1. Identify whether a sort is stable and give an example input for unstable sorts.
  2. Trace each iteration of selection sort, insertion sort, and heapsort.
  3. Explain the runtime for selection sort, insertion sort, and heapsort.
Feb 15
Holiday
Feb 17
Recursive Sorts
  1. Trace the recursive execution of merge sort and quicksort.
  2. Identify a valid partition and trace the in-place partitioning algorithm.
  3. Evaluate variations of quicksort pivot selection, partitioning, and subsorts.
Feb 18
SectionSorting Algorithms
Feb 19
Algorithm Bounds

Research Project

Feb 22
Career Panel