Readings and other resources in module order

This page collects together all of the “readings” associated with individual modules.

In this site, readings represent “passive” learning opportunities, as opposed to experiences, which represent “active” learning opportunities. In many courses, readings and experiences together constitute the “assignments”.

Module: Analysis examples

Insertion Sort

Insertion sort example

Screencast Suthers 8 min

Loop Invariant

Loop invariant example

Screencast Suthers 6 min

Insertion sort analysis

Insertion sort analysis

Screencast Suthers 28 min

Merge Sort

Merge sort example

Screencast Suthers 11 min

Merge Sort Analysis

Merge sort analysis

Screencast Suthers 21 min

CLRS 2 - Getting started

Getting started with analysis of algorithms

Textbook 26 pages

Introduction to algorithms, Lecture 1

Analysis of algorithms-insertion sort, asymptotic analysis, merge sort, recurrences

Screencast Leiserson 80 min

Chapter 2 Notes

Modeling a problem, loop invariants, analysis

Notes

Module: Growth of functions

Asymptotic notations

Notations for this analysis

Screencast Suthers 12 min

Omega and Theta

The omega and theta notations

Screencast Suthers 17 min

little-o and omega

The little guys, properties, and use in equations

Screencast Suthers 16 min

Common Functions

Common functions and useful identities

Screencast Suthers 9 min

CLRS 3 - Growth of functions

Asymptotic notation, standard notation, and common functions.

Textbook 22 pages

Chapter 3 Notes

Introduction to asymptotic analysis

Notes

Introduction to algorithms, Lecture 2

Asymptotic notation, recurrences, substitution, master method (start at 16 min)

Screencast Demaine 71 min

Module: Abstract data types

Stacks, queues, and lists

Basic abstract data types.

Screencast Suthers 28 min

Trees and dynamic sets

More on abstract data types.

Screencast Suthers 16 min

CLRS 10 - Elementary Data Structures

Stacks, queues, linked lists, pointers and objects, rooted trees.

Textbook 21 pages

Chapter 4 Notes

Introduction to abstract data types

Notes

Module: Probabilistic Analysis

Indicator random variables

Indicator random variables.

Screencast Suthers 18 min

Example analysis: inversions

Inversions

Screencast Suthers 14 min

Randomized algorithms and skip lists

Randomized algorithms and skip lists

Screencast Suthers 17 min

Analysis of skip lists

Analysis of skip lists

Screencast Suthers 8 min

Skip Lists

Skip Lists

Screencast Demaine 85 min

CLRS 5 - Probabilistic Analysis and Randomized Algorithms

The hiring problem, indicator random variable, randomized algorithms

Textbook 16 pages

Skip Lists in Java

Skip lists, from Goodrich and Tamassia’s Data Structures and Algorithms in Java

Textbook 10 pages

Chapter 5 Notes

Probabilistic analysis and randomized algorithms

Notes

Module: Hash Tables

Hash tables: introduction and chaining

Introduction to hash tables

Screencast Suthers 8 min

Hash tables: analysis of chaining

Analysis of chaining

Screencast Suthers 20 min

Hash tables: Hash functions

Examples of hash functions and universal chaining

Screencast Suthers 13 min

Hash table: open addressing

Using open addressing to avoid the overhead of linked lists.

Screencast Suthers 16 min

CLRS 11 - Hash tables

Direct address tables, hash tables, hash functions, and open addressing

Textbook 23 pages

Chapter 6 Notes

Notes on hash tables

Notes

Hash tables I

Hash tables and the symbol table problem

Screencast Leiserson 77 min

Hash tables II

Universal hashing

Screencast Leiserson 79 min

Module: Divide and conquer

Divide and conquer and recurrence relations

Introduction to the divide and conquer algorithm

Screencast Suthers 14 min

Solving recurrence relations: substitution

How to perform substitution.

Screencast Suthers 8 min

Solving recurrence relations: recursion trees

How to generate a guess for the form of the solution to the recurrence.

Screencast Suthers 19 min

Solving recurrence relations: master method

Find solutions to recurrence relations of form T(n) = aT(n/b) + h(n), where a and b are constants, a ≥ 1 and b > 1

Screencast Suthers 17 min

CLRS 4 - Divide and conquer

The maximum subarray problem, strassen’s algorithm for matrix multiplication, substitution method, recursion tree method, and the master method.

Textbook 30 pages

Chapter 7 Notes

Notes on divide and conquer

Notes

Divide and conquer

Divide and conquer: binary search, powering a number, fibonacci numbers, matrix multiplication

Screencast Demaine 68 min

Module: Binary Search Trees

Introduction to binary search trees

Basic qualitative facts about BSTs

Screencast Suthers 15 min

BST Queries

How to perform queries on BSTs

Screencast Suthers 22 min

Modifying BSTs

How to modify binary search trees.

Screencast Suthers 21 min

Analyzing BSTs

Determine the height of binary search trees.

Screencast Suthers 5 min

CLRS 12 - Binary search trees

What is a binary search tree; querying, insertion, and deletion.

Textbook 13 pages

Chapter 8 Notes

Notes on binary search trees

Notes

Module: Heapsort

Introduction to heaps

Basic ideas about heaps

Screencast Suthers 14 min

Building heaps

Understanding how to build heaps

Screencast Suthers 14 min

Analyzing heap building

Correctness and run time analysis of heaps

Screencast Suthers 9 min

Applications of heaps

Heapsort and priority queues

Screencast Suthers 14 min

CLRS 6 - Heapsort

Heapsort, heaps, maintaining the heap property, building a heap, priority queues

Textbook 19 pages

Chapter 9 Notes

Notes on heaps and heapsort.

Notes

Module: Quicksort

Introduction to quicksort

Basic ideas about quicksort

Screencast Suthers 24 min

Quicksort: Randomization and analysis

Randomizing and analyzing quicksort

Screencast Suthers 23 min

Bounds on sorting

Lower bounds on comparison sorts, and O(n) sorts

Screencast Suthers 20 min

CLRS 7 - Quicksort

Description and performance of quicksort, a randomized version, and analysis.

Textbook 20 pages

CLRS 8 - Sorting in linear time

Lower bounds for sorting, counting sort, radix sort, bucket sort.

Textbook 22 pages

Notes on Quicksort

Notes on quicksort

Notes

Module: Balanced Trees

Introduction to (2,4) Trees

Basic ideas about balanced trees

Screencast Suthers 11 min

Insertion and deletion in (2,4) Trees

Conceptual overview of balanced tree operations

Screencast Suthers 14 min

Red-Black Trees

Red-Black trees as 2-4 and BSTs

Screencast Suthers 15 min

Red-Black Tree Mutation

Red-Black tree insertion and deletion

Screencast Suthers 21 min

CLRS 13 - Red-Back Trees

Properties, rotations, insertion, and deletion

Textbook 31 pages

Sedgewick 15 - Balanced Trees

Top-down 2-3-4 trees, red-black trees, other algorithms

Textbook 14 pages

Notes on balanced trees

Balanced trees and operations on them

Notes

Module: Dynamic Programming

Introduction to dynamic programming

Example of dynamic programming using the cut rod problem.

Screencast Suthers 24 min

Dynamic programming using steps and LCS

Example of dynamic programming using steps and LCS.

Screencast Suthers 17 min

Dynamic programming using LCS (continued)

Example of dynamic programming using LCS.

Screencast Suthers 18 min

Dynamic programming applications, substructure, and summary

Summary of dynamic programming.

Screencast Suthers 18 min

CLRS 15 - Dynamic Programming

Rod cutting, matrix-chain multiplication, elements of DP, longest common subsequence, optimal BSTs

Textbook 55 pages

Sedgewick 37 - Dynamic Programming

Knapsack problem, matrix chain product, optimal BSTs, shortest paths, time and space requirements

Textbook 14 pages

Notes on dynamic programming

Derivations of dynamic programming

Notes

Module: Greedy Algorithms

Greedy algorithms and dynamic programming

Dynamic programming and greedy algorithsm.

Screencast Suthers 8 min

Greedy algorithms and activity scheduling

Illustration of the greedy strategy.

Screencast Suthers 23 min

Huffmann Codes

Design and implementation of Huffman Codes.

Screencast Suthers 17 min

CLRS 16 - Greedy algorithms

Activity selection problems, elements of the greedy algorithm strategy, huffman codes (16.1 -16.3)

Textbook 23 pages

Notes on greedy algorithms

Greedy algorithms, the activity selection problem, greedy strategy, and Huffman codes.

Notes

Module: Graphs

Graph definitions

Graph definitions

Screencast Suthers 13 min

Graph ADT and representations

Methods in the graph ADT

Screencast Suthers 23 min

Breadth first search

Breadth first search and applications to finding the shortest path

Screencast Suthers 16 min

Depth first search

Depth first search and its asymptotic complexithy

Screencast Suthers 10 min

Depth first search: example and properties

Depth first search trace.

Screencast Suthers 17 min

Topological sort

Topological sort and strongly connected components

Screencast Suthers 26 min

CLRS 22 - Elementary graph algorithms

Representations of graphs, breadth-first search, depth-first search, topological sort, strongly connected components

Textbook 24 pages

Sedgewick 32 - Directed graphs

Depth first search, transitive closure, topological sorting, strongly connected components

Textbook 12 pages

Sedgewick and Wayne 4 - Graphs

Undirected graphs, directed graphs, minimum spanning trees, shortest paths

Textbook 12 pages

Goodrich and Tommassia 13 - Graphs

The graph ADT, data structures for graphs, graph traversals, directed graphs, weighted graphs, shortest paths, minimum spanning trees

Textbook 70 pages

Notes on graphs

Graph definitions, examples, the ADT, representations, breadth first seach, depth first search, topological sort, strongly connected components

Notes

Module: Amortized analysis

Introduction to amortized analysis

Aggregate, accounting, and potential methods

Screencast Suthers 23 min

Amortized analysis example

aggregate analysis of dynamic tables

Screencast Suthers 16 min

CLRS 17 - Amortized analysis

aggregate analysis, the accounting method, the potential method, dynamic tables

Textbook 30 pages

Notes on amortized analysis

The general idea, multipop example, aggregate analysis, accounting method, potential method, dynamic tables.

Notes

Module: Disjoint sets

Sets and union-find

Introduction to disjoint sets

Screencast Suthers 27 min

CLRS 21 - Data structures for disjoint sets

disjoint set operations, linked-list representation of disjoint sets, disjoint-set forests, analysis of union by rank with path compression

Textbook 25 pages

Notes on disjoint sets

Disjoint sets, finding connected components, linked list representations, and forest representations

Notes

Module: Minimum spanning tree

Introduction to minimum spanning trees

Including the generic algorithm and the safe edge theorem

Screencast Suthers 17 min

Kruskal's algorithm

Kruskal’s minimum spanning tree algorithm, with example and analysis.

Screencast Suthers 13 min

Prim's algorithm

Prim’s minimum spanning tree algorithm, with example and analysis.

Screencast Suthers 15 min

CLRS 23 - Minimum spanning trees

Growing a minimum spanning tree, the algorithms of Kruskal and Prim.

Textbook 19 pages

Sedgewick 31 - Weighted graphs

Minimum spanning trees, shortest path, dense paths, geometric problems

Textbook 14 pages

Notes on minimum spanning trees

Minimum spanning trees, the generic algorithm, Kruskal’s and Prim’s algorithms

Notes

Module: Single source shortest paths

Introduction to single source shortest paths

Properties of the problem, supporting algorithms

Screencast Suthers 19 min

Bellman-Ford and DAGS shortest paths

The Bellman-Ford algorithm

Screencast Suthers 20 min

Dijkstra's algorithm for single source shortest paths

Dijkstra’s algorithm

Screencast Suthers 20 min

CLRS 24 - Single Source Shortest Paths (24.1 - 24.3)

Bellman-Ford algorithm, SSSP in directed acyclic graphs, Dijkstra’s algorithm

Textbook 20 pages

Sedgewick 31 - Weighted graphs

Minimum spanning trees, shortest path, dense paths, geometric problems

Textbook 14 pages

Notes on single source shortest paths

Shortest paths problem, Bellman-Ford algorithm, Shortest paths in a DAG, Dijkstra’s algorithm

Notes

Module: All pairs shortest paths

Introduction to all pairs shortest paths

Introduction.

Screencast Suthers 10 min

Johnson's algorithm for all pairs shortest paths

Johnson’s algorithm

Screencast Suthers 24 min

Floyd-Warshall algorithm for all pairs shortest paths

Floyd-Warshall’s algorithm

Screencast Suthers 20 min

CLRS 25 - All Pairs Shortest Paths

Shortest paths and matrix multiplication, Floyd-Warshall algorithm, Johnson’s algorithm for sparse graphs

Textbook 22 pages

Notes on all pairs shortest paths

All pairs shortest paths problem, using single source algorithms, Johnson’s bright idea, Floyd-Warshall: dynamic programming for dense graphs, transitive closure

Notes

Module: Maximum flow

Introduction to maximum flow

Flow networks and the maximum flow problem

Screencast Suthers 12 min

Residuals, augmenting flows.

Residual graphs, augmenting flows, and the min cut max flow theorem

Screencast Suthers 20 min

Flow algorithms and applications

Ford-Fulkerson, Edmonds-Karp and Bipartite Matching.

Screencast Suthers 14 min

CLRS 26 - Maximum flow (26.1 - 26.3)

Flow networks, Ford-Fulkerson method, Maximum bipartite matching.

Textbook 29 pages

Notes on maximum flow

Flow networks, maximum flow problem, Ford-Fulkerson algorithm, Edmonds-Karp algorithm, maximum bipartite matching

Notes

Module: Linear programming

Sedgewick 5 - Gaussian Elimination

A simple example, outline of the method, variations and extensions

Textbook 10 pages

Sedgewick 38 - Linear programming

Linear programs, geometric interpretation, simplex method

Textbook 15 pages

CLRS 29 - Linear programming (29.0 - 29.3)

Standard and slack forms, formulating problems as linear programs, the simplex algorithm.

Textbook 35 pages

Notes on linear programming

Introduction, formulating problems as linear programs, foundations in gaussian elimination, the simplex method

Notes

Module: Multithreading

CLRS 27 - Multithreading

The basics of dynamic multithreading, multithreaded matrix multiplication, multithreaded merge sort.

Textbook 36 pages

Notes on multithreading

Concepts of dynamic multithreading, modeling and measuring dynamic multithreading, analysis of multithreaded algorithms, matrix multiplication example, merge sort example

Notes

Module: String matching

CLRS 32 - String matching

The naive string matching algorithm, the Robin-Karp algorithm, string matching with finite automata, the Knuth-Morris-Pratt algorithm

Textbook 29 pages

Notes on string matching

Naive (brute force) string matching, matching with finite state automata, Knuth-Morris-Pratt algorithm, Rabin-Karp algorithm

Notes

Module: NP-completeness

Introduction to NP-completeness

very informal

Screencast Suthers 19 min

An NP-complete problem

Show that circuit satisfiability is NP-Complete

Screencast Suthers 12 min

NP Complete problems

Examples of problems from logic, graph theory, and arithmetic

Screencast Suthers 25 min

Notes on np-completeness

P and NP classes, encoding problems and polynomial time verification, constructing NPC

Notes

Module: Approximation algorithms

Approximation algorithms

Heuristic approximations for NP-hard problems

Screencast Suthers 19 min

Approximation strategies

Randomization and relaxed linear programming

Screencast Suthers 18 min

Notes on approximation algorithms

Vertex cover example, TSP example, randomization and linear programming strategies

Notes