Important People in Data Structures and Algorithms with C
Most of the structures and algorithms in this course carry the names of the people who found or popularized them: the AVL tree, the Kruskal and Prim algorithms, Dijkstra's shortest path, Shell sort, Floyd's cycle detection. The books the course builds on also belong to pioneers of the C language and of teaching data structures.
Each card gives the person's years, institution, the contribution that matches something in the course, and links to the slides where that contribution appears. The cards can be filtered by topic, searched, and sorted by surname or by year of contribution.
Leonhard Euler
The bridges of Königsberg · 1736
He asked whether a walk exists that crosses each of the seven bridges of Königsberg exactly once. By treating the land masses as vertices and the bridges as edges, he showed that the answer depends only on the connections, not on the shape of the map, and proved that no such walk exists. This 1736 work is regarded as the beginning of graph theory; a closed Euler walk cannot exist unless every vertex has even degree.
William George Horner
Horner's method · 1819
He is known for a method of approximating the roots of polynomials, which had appeared earlier in Ruffini's work. Today his name is attached mostly to the nested way of evaluating a polynomial: written as a₀ + x(a₁ + x(a₂ + …)), a polynomial of degree n takes only n multiplications. The course uses the same pattern in two places: finding the relative position of an element in an n-dimensional array, and hashing a string with the loop h = h * 31 + c.
Arthur Cayley
Number of labeled trees · 1889
In a short note published in 1889 he stated that n labeled vertices can form nⁿ⁻² different trees. The result first appears in Borchardt's 1860 work, but it is known today as Cayley's formula. The same number counts the spanning trees of the complete graph on n vertices: 4² = 16 for K₄.
Wilhelm Ackermann
Ackermann function · 1928
This logician, a student of Hilbert, defined a function that is computable but not primitive recursive. The two-variable form used in textbooks today is a simplification by Rózsa Péter and Raphael Robinson. The function grows astonishingly fast; its inverse α(n) grows so slowly that the cost of disjoint-set operations using the weighting rule and the collapsing rule is treated as practically constant.
Vojtěch Jarník
Growing a single tree for the minimum spanning tree · 1930
This Czech mathematician, whose main field was number theory, published in Czech in 1930 an algorithm that simplified Borůvka's result: the tree starts from a single vertex, and at each step the cheapest edge joining the tree to the rest of the graph is added. The algorithm was rediscovered by Prim (1957) and Dijkstra (1959), which is why it is also called the DJP algorithm or the Prim–Jarník algorithm.
Otakar Borůvka
The first minimum spanning tree algorithm · 1926
Prompted by the power-grid problem of an electric company in western Moravia, he published the first known minimum spanning tree algorithm in 1926. In each round every component picks the cheapest edge leaving it; since the number of components at least halves in every round, at most log n rounds suffice. His paper, written in Czech, went unnoticed for a long time; when Sollin rediscovered the method in 1965, the algorithm also became widely known as Sollin's algorithm. Because the rounds are independent of each other, it suits parallel computation.
John von Neumann
Merge sort · 1945
In 1945 he wrote a routine for the EDVAC computer that merges two sorted arrays into one sorted array; this routine was part of what is today called merge sort. The manuscript is the oldest surviving example of von Neumann's code. The algorithm is the standard example of the divide-and-conquer approach and of a stable sort that runs in O(n lg n) even in the worst case.
H. S. M. Coxeter
Magic square rule · Coxeter groups
One of the leading geometers of the century, he worked on higher-dimensional polytopes and reflection groups. He prepared the editions of W. W. Rouse Ball's Mathematical Recreations and Essays that appeared after 1939; the textbook bases its magic square rule for odd n on him. The rule finishes in n² steps, whereas trying all 25! arrangements by brute force would take millions of centuries. In the course this difference is used to show that a good algorithm matters more than a faster machine.
Richard Bellman and Lester R. Ford Jr.
Bellman–Ford algorithm · 1956, 1958
Ford in 1956 and Bellman in 1958 published the single-source shortest path method that allows negative edge weights; the same idea also appears in Shimbel (1955) and Moore. All edges are relaxed for n − 1 rounds; if an edge can still be relaxed in round n, the graph contains a negative cycle. Bellman is one of the founders of dynamic programming, and Ford, together with Fulkerson, of maximum-flow theory.
Robert C. Prim
Prim's algorithm · 1957
Working at Bell Laboratories at about the same time as Kruskal, he published in 1957 the algorithm that grows a single tree for the minimum spanning tree, rediscovering Jarník's 1930 method independently. Because it always picks the cheapest edge joining a vertex in the tree to one outside it, no cycle check is needed. The algorithm runs in O(n²) with arrays and drops to O(e log n) with a heap, which is faster on sparse graphs.
Georgy Adelson-Velsky and Evgenii Landis
AVL tree · 1962
In their 1962 paper “An algorithm for the organization of information” they defined the first self-balancing binary search tree, which keeps the height difference of the two subtrees of every node at most 1; the structure takes its name from the initials of their surnames. When the balance is broken, a single or double rotation restores it, and the height never exceeds ≈ 1.44 lg n. Adelson-Velsky was also one of the authors of the Kaissa chess program; Landis's main field was partial differential equations.
Alan J. Perlis
Threaded trees · 1960
One of the designers of ALGOL, he received the first Turing Award in 1966. In 1960, together with C. Thornton, he proposed that the null pointers of a binary tree could be used to point to the inorder predecessor and successor; these pointers are called threads. In a threaded tree, inorder traversal needs neither a stack nor recursion. The short maxims often quoted in the course also come from his “Epigrams on Programming,” published in 1982.
Donald L. Shell
Shell sort · 1959
He published his paper “A High-Speed Sorting Procedure” in Communications of the ACM in 1959. Insertion sort is applied to elements that are h positions apart, and h is reduced down to 1; because distant exchanges remove inversions quickly, the Ω(n²) bound of algorithms that exchange only neighbors is broken. The running time depends on the gap sequence, and the sort is not stable because of the distant exchanges.
Joseph B. Kruskal
Kruskal's algorithm · 1956
In 1956 he published the method that finds a minimum spanning tree by sorting the edges by cost and adding to the tree every edge that does not form a cycle. The chosen edges first form a forest, which eventually merges into a single tree. The cycle check is done with disjoint sets: if the two ends of an edge are in different sets, the edge is taken and the sets are merged; the total time is O(e log e). He is also known in statistics for his work on multidimensional scaling.
Edsger W. Dijkstra
Shortest path algorithm · 1959
In a two-page note published in 1959 he gave both the single-source shortest path algorithm and the Jarník–Prim method for the minimum spanning tree. The shortest path algorithm is greedy: the vertex with the smallest distance is finalized, and the distances of its neighbors are updated through it. This choice is correct only for non-negative edge weights. A pioneer of structured programming, Dijkstra received the Turing Award in 1972.
C. A. R. (Tony) Hoare
Quicksort · 1961–1962
He devised quicksort in 1959 in Moscow while working on a dictionary translation; he published the algorithm in Communications of the ACM in 1961 and its detailed analysis in The Computer Journal in 1962. Partitioning around a pivot and sorting the two parts recursively gives an in-place sort that runs in O(n lg n) on average. He also developed Hoare logic for program correctness and received the Turing Award in 1980. He died in Cambridge on 5 March 2026.
Stephen Warshall
Transitive closure · 1962
In 1962 he published the algorithm that computes the transitive closure of a Boolean matrix in O(n³) time: for each k, the rule “if there is a path from i to k and from k to j, then there is a path from i to j” is applied to all pairs. Floyd carried the same scheme over to path lengths in the same year; the algorithm that finds shortest paths between all pairs is therefore called Floyd–Warshall.
Robert W. Floyd
Floyd–Warshall · cycle detection
In 1962 he published the Floyd–Warshall algorithm, which finds the shortest paths between all pairs of vertices. The “tortoise and hare” method, which finds a cycle in a linked list with two pointers (one advancing one step, the other two), is also attributed to him through Knuth's account; it works with O(1) extra memory. In 1964 he gave the method that builds a heap bottom-up in O(n) time. He received the Turing Award in 1978 for his contributions to program verification.
Donald E. Knuth
The Art of Computer Programming · since 1968
With the series The Art of Computer Programming, whose first volume appeared in 1968, he made the mathematical analysis of algorithms a discipline; he received the Turing Award in 1974. Many results in the course rest on him: the expected probe counts for linear probing, the constant A ≈ (√5 − 1)/2 suggested for the multiplication method, the gap sequence 1, 4, 13, 40, … for Shell sort, and the account of Floyd's cycle detection. He is also a co-author of the Knuth–Morris–Pratt string search algorithm. Sedgewick is his doctoral student.
Rudolf Bayer and Edward M. McCreight
B-tree · 1970–1972
Working together at Boeing, they designed the B-tree to keep large sorted indexes on disk; the paper was circulated as a report in 1970 and published in Acta Informatica in 1972. In this balanced m-way tree each node holds many keys and all leaves are on the same level; a node that overflows splits in two, sending its middle key up to its parent. The symmetric binary B-trees that Bayer defined in 1972 are the forerunners of red-black trees.
Robert E. Tarjan
Analysis of disjoint sets · 1975, 1984
In 1975 he proved that disjoint-set operations using the weighting rule together with path compression are bounded by the inverse Ackermann function α. His 1984 paper with Jan van Leeuwen (b. 1946, Utrecht University) gave a joint worst-case analysis of union and find methods of this kind. With Sleator he defined splay trees, and with Fredman Fibonacci heaps; he received the Turing Award in 1986.
Dennis M. Ritchie
The C language · Unix
He developed the C language around 1972 at Bell Laboratories in order to write the Unix operating system; he designed Unix with Ken Thompson and shared the 1983 Turing Award with him. Every structure in the course is built with the tools C provides: struct for records, pointers for links, and malloc and free for run-time memory. The C Programming Language (1978), which he wrote with Kernighan, is the constant companion of the course.
Brian W. Kernighan
The C Programming Language · 1978
The C Programming Language (1978; second edition for ANSI C in 1988), which he wrote with Ritchie, is known as “K&R” after its authors' initials and became the de facto definition of C. With its short, readable examples, the book also set the model for how a programming language book should be written. He is a co-author of the AWK language (the K in its name is his); he has taught at Princeton since 2000.
Ellis Horowitz
Fundamentals of Data Structures · 1976
Fundamentals of Data Structures (1976) and Fundamentals of Computer Algorithms (1978), which he wrote with Sahni, were among the most widely used textbooks in the world for many years. The C edition, Fundamentals of Data Structures in C, appeared in 1993 with the participation of Anderson-Freed and is the main textbook of this course; references on the slides such as “Horowitz 2.2” point to sections of this book. He chaired the computer science department at USC from 1990 to 1999.
Sartaj Sahni
The Horowitz–Sahni books
He wrote the data structures and algorithms books together with Horowitz; the textbook's treatment of the system life cycle, the definition of an algorithm, and ADTs comes from this joint work. As a distinguished professor at the University of Florida he worked on parallel computing, NP-completeness, and approximation algorithms. In 1997 he received the IEEE Taylor L. Booth Education Award.
Susan Anderson-Freed
Fundamentals of Data Structures in C · 1993
The third author, who adapted Horowitz and Sahni's book to the C language; Fundamentals of Data Structures in C, published in 1993, was translated into five languages. She began as a sociology faculty member at Illinois Wesleyan University and went on to teach programming courses; in 1986 she founded the university's computer science department and became its first chair. She died on 4 November 2012.
Robert Sedgewick
Analysis of quicksort · Algorithms in C
Under Knuth's supervision he wrote his 1975 doctoral thesis on quicksort; the analysis of improvements such as median-of-three and finishing small partitions with insertion sort comes from this work. Algorithms in C is among the supplementary sources of the course; the code in the quicksort chapter is taken from this book. With Guibas he defined red-black trees, and he became the founding chair of the computer science department at Princeton.
H. C. von Warnsdorff
Warnsdorff's rule for the knight's tour · 1823
In 1823 he proposed the oldest known heuristic for the knight's tour: at each step the knight moves to the square from which the fewest empty squares can be reached next. This order, which uses up the most cramped squares first, usually finds a complete tour on an 8×8 board without ever backtracking. Solving the same problem with plain backtracking takes far longer. The rule is a classic example of how much work good ordering of candidates saves in backtracking.
Jan Łukasiewicz
Polish (prefix) notation · 1924
A Polish logician. In 1924 he invented prefix notation, which puts the operator before its operands so that logical formulas can be written without parentheses, and he used it in his publications from 1929 on. The notation is therefore called Polish notation; the postfix form, in which the operator is written last, is called reverse Polish notation. A postfix expression is evaluated from left to right with a single stack, needing neither parentheses nor precedence rules.
Harold H. Seward
Counting sort · 1954
In his 1954 master's thesis at MIT he described counting sort and proposed using it in every pass of radix sort. The algorithm does not compare elements with each other: it first counts how many times each value occurs, then uses the prefix sums of these counts to find each element's place in the output. It sorts n integers in the range 0…k in O(n + k) time and does so stably.
John McCarthy
LISP · 1958
He designed the LISP language, which appeared in 1958 and was published in Communications of the ACM in 1960. In LISP, data are represented by generalized lists whose elements may be atoms or other lists; the head of a list is taken with car and its tail with cdr. He also invented garbage collection, which reclaims the memory of list nodes that can no longer be reached, for LISP. He is known as the person who coined the term artificial intelligence and received the Turing Award in 1971.
Arthur B. Kahn
Topological sort · 1962
In his paper “Topological sorting of large networks” (1962) he gave the algorithm that finds a topological order of a directed acyclic graph by repeatedly removing vertices of in-degree zero. For each removed vertex, the in-degrees of its successors are decreased by one; a vertex whose in-degree drops to zero joins those waiting. When the waiting vertices are kept in a queue, the method is called Kahn's algorithm. It runs in O(n + e) time; if not all vertices can be removed, the graph contains a cycle.
J. W. J. Williams
Binary heap and heap sort · 1964
He invented the binary heap and heap sort in 1963 while working at Elliott Brothers, and published the algorithm in 1964 in Communications of the ACM as “Algorithm 232: Heapsort.” A heap stores a complete binary tree in an array without gaps; parents and children are found by index arithmetic. Heap sort sorts n elements in O(n lg n) in the worst case without an extra array. The same year Floyd added the method that builds a heap bottom-up in O(n) time.
Joseph M. Morris
Morris traversal · 1979
In his paper “Traversing binary trees simply and cheaply” (1979) he showed how to traverse a binary tree inorder without a stack, recursion, or a flag field. A temporary thread is written into the empty right pointer of a node's inorder predecessor; the traversal returns along this thread and erases it. The tree is changed temporarily during the traversal and restored at the end. Extra memory is O(1) and time is O(n).
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
Introduction to Algorithms · 1990
The authors of Introduction to Algorithms, known as CLRS after their initials. The first edition appeared in 1990 under the names of Cormen, Leiserson, and Rivest; Stein joined the authors in the second edition in 2001. The book is among the supplementary sources of the course: asymptotic notation, recurrence relations, heaps, hash tables, graph algorithms, and the lower bound for comparison sorting are given here with proofs. Rivest shared the 2002 Turing Award with Shamir and Adleman for the RSA cryptosystem.
David R. Musser
Introsort · 1997
He introduced introsort in his 1997 paper “Introspective Sorting and Selection Algorithms.” The algorithm starts with quicksort and tracks the recursion depth; when the depth exceeds about 2⌊lg n⌋, it finishes that part with heap sort. This keeps the average speed of quicksort while holding the worst case at O(n lg n). The method was developed for the C++ standard library and is common in std::sort implementations. Musser worked with Alexander Stepanov on generic programming and the STL.
Tim Peters
Timsort · 2002
In 2002 he wrote Timsort for Python. The algorithm finds the already sorted stretches in the data (runs), extends short runs with insertion sort, and merges the runs with merge sort. It is stable, runs in O(n lg n) in the worst case, and in O(n) on already sorted data. It was Python's standard sort from version 2.3 through 3.11; Java SE 7 (for object arrays), Android, and V8 also adopted Timsort.
No names match the search and filter.
Years and contributions are based on original publications and encyclopedic sources. “b.” marks the year of birth and is used for living people; “d.” marks a person for whom only the year of death is known. Edward McCreight's birth year could not be found in published sources, so it is not given. For people whose life dates could not be found in reliable sources, or who share a combined card, only the year of the contribution and the place of publication are given.
Sercan KÜLCÜ, All rights reserved.