Important People in Data Structures

Designed the Pascal language and wrote Algorithms + Data Structures = Programs (1976).

The title of the book sums up the central idea of this course: a program is an algorithm working on a well-chosen data structure.

In the course: Chapter 1 · Introduction

Introduced the abstract data type (ADT) with Stephen Zilles in 1974 and made it the foundation of the CLU language. She received the 2008 Turing Award.

An ADT separates what the operations do from how they are implemented, which is exactly how the course defines stacks, queues, lists, maps, and sets.

In the course: Chapter 1 · Introduction

Wrote The Art of Computer Programming and made the mathematical analysis of algorithms standard practice, together with O, Ω, and Θ notation.

His systematic treatment of searching, sorting, trees, and hashing turned implementation techniques into an engineering discipline. The expected probe counts for linear probing are also his results.

In the course: Chapter 2 · Algorithm Analysis, Chapter 12 · Maps and Hash Tables

Described merge sort in 1945, making it one of the first algorithms written for a stored-program computer.

Merge sort is the standard example of divide and conquer and of a stable O(n log n) sort.

In the course: Chapter 3 · Sorting Algorithms

Developed quicksort in 1959–1961 and later created Hoare logic for proving programs correct.

Quicksort brings together partitioning, recursion, in-place rearrangement, and the effect of the pivot choice on average and worst-case cost.

In the course: Chapter 3 · Sorting Algorithms

First used linked lists in the Information Processing Language (IPL), which they developed in 1955–1956.

Nodes connected by references made structures that grow and shrink at run time possible. Linked lists, linked stacks, queues, and trees all build on this idea.

In the course: Chapter 5 · Linked Lists

The tortoise-and-hare cycle detection algorithm is attributed to him. His Treesort 3 algorithm (1964) builds a heap bottom-up.

Two pointers moving at different speeds find a cycle in O(n) time with O(1) extra space. Bottom-up heap construction takes O(n) instead of O(n log n).

In the course: Chapter 5 · Linked Lists, Chapter 11 · Priority Queues and Heaps

Designed the Java Collections Framework introduced in Java 1.2 (1998).

The List, Set, Map, and Iterator interfaces, with classes such as ArrayList, LinkedList, and HashMap, separate the ADT from the data structure that implements it, just as the course does.

In the course: Chapter 6 · The List ADT and Java Collections

Formulated the stack principle (Kellerprinzip, 1955–1957) for translating and evaluating arithmetic formulas.

The last-in, first-out (LIFO) stack became the standard tool for expression evaluation, compilers, and managing method calls.

In the course: Chapter 7 · Stacks

Introduced Polish notation, that is, prefix notation, in the 1920s. Reverse Polish notation, or postfix notation, is derived from it.

Prefix and postfix expressions need no parentheses and can be evaluated with a single stack in one pass.

In the course: Chapter 7 · Stacks

Developed the shunting-yard algorithm (1961), which converts infix expressions to postfix, and the shortest-path algorithm for weighted graphs (1959).

Shunting-yard works with an operator stack and precedence rules. The shortest-path algorithm combines relaxation with a priority queue that returns the element with the smallest key.

In the course: Chapter 7 · Stacks, Chapter 14 · Graphs

Introduced the AVL tree, the first self-balancing binary search tree, in 1962.

A balance factor and single or double rotations keep the height at O(log n), so search, insertion, and deletion stay logarithmic.

In the course: Chapter 10 · Search Trees

Introduced the red-black tree in 1978, building on Rudolf Bayer's symmetric binary B-trees (1972).

Node colors and a few rotations keep the tree balanced. Java's TreeMap and TreeSet are implemented as red-black trees.

In the course: Chapter 10 · Search Trees

Introduced the splay tree in 1985.

A splay tree keeps no balance information. It moves every accessed node to the root, which makes operations run in amortized O(log n) time and speeds up access to recently used keys.

In the course: Chapter 10 · Search Trees

Developed the B-tree at Boeing Scientific Research Labs (1970; published 1972).

A high fan-out, with many children per node, keeps the tree shallow, so each search reads only a few disk blocks. B-trees and B+ trees are the basis of database and file-system indexes.

In the course: Chapter 10 · Search Trees

Introduced the binary heap and the heapsort algorithm in 1964.

A complete binary tree stored in an array supports insertion and removal of the minimum (or maximum) in O(log n) time. The same structure also gives an in-place O(n log n) sort.

In the course: Chapter 11 · Priority Queues and Heaps

Introduced the Fibonacci heap in 1984.

Its amortized O(1) decrease-key operation shows how a specialized heap can speed up graph algorithms such as shortest paths.

In the course: Chapter 11 · Priority Queues and Heaps

Proposed hashing with chaining in an internal IBM memorandum in 1953.

Mapping a key directly to a bucket brings lookup down to expected O(1) time. Separate chaining is still one of the standard ways to resolve collisions.

In the course: Chapter 12 · Maps and Hash Tables

Introduced the disjoint-set forest representation in 1964.

Each set is a tree whose root is the set's representative, so union and find need nothing but parent links.

In the course: Chapter 13 · Sets and Disjoint Sets

Proved in 1975 that with union by rank and path compression together, m operations take O(m·α(n)) time.

The inverse Ackermann function α(n) grows so slowly that each operation takes constant time for all practical purposes.

In the course: Chapter 13 · Sets and Disjoint Sets

Published breadth-first search (BFS) in 1959 as a way to find the shortest path through a maze.

BFS uses a queue to visit vertices level by level and finds shortest paths in unweighted graphs in O(n + m) time.

In the course: Chapter 14 · Graphs

Published the topological sorting algorithm based on in-degrees in 1962.

Repeatedly removing vertices of in-degree zero puts the vertices of a directed graph in topological order; if the graph is not a directed acyclic graph (DAG), the procedure exposes the cycle.

In the course: Chapter 14 · Graphs

Published his minimum spanning tree (MST) algorithm in 1956.

Kruskal's algorithm sorts the edges by weight and uses a disjoint-set (union-find) structure to reject edges that would form a cycle.

In the course: Chapter 14 · Graphs

While at Bell Labs, published the minimum spanning tree algorithm that grows the tree from a single vertex, in “Shortest connection networks and some generalizations” (1957). Vojtěch Jarník (1930) and Edsger W. Dijkstra (1959) gave the same method independently.

At each step Prim's algorithm adds the lightest edge between the tree and the vertices outside it; the cut property guarantees that this edge belongs to a minimum spanning tree. With the candidate edges kept in a min-priority queue, the algorithm runs in O(m log n) time.

In the course: Chapter 14 · Prim's Algorithm, Chapter 14 · Kruskal vs. Prim