Foundations of Computer Science PDF Download – Aho & Ullman (C Edition) BSCS

BSCS students taking a Discrete Mathematics or Data Structures (CS2) course — or anyone who wants one classic text covering both — can read the complete “Foundations of Computer Science” (C Edition) by Alfred V. Aho and Jeffrey D. Ullman, free from its official source on Stanford’s InfoLab site. It’s a 14-chapter, university-level text built directly from the authors’ own Stanford CS109 course, covering induction and recursion, running-time analysis, combinatorics and probability, the tree, list, set, relational and graph data models, automata and regular expressions, context-free grammars, and both propositional and predicate logic.

Originally published in 1994 by W. H. Freeman after an earlier 1992 Pascal-based edition, this C Edition has since been taken out of print by its publisher; the authors now host every chapter as a free PDF directly on their own site, with no formal open licence but their own stated welcome to use it. Its mathematical content — everything from induction proofs through NP-hardness of the tautology problem and Gödel’s Incompleteness Theorem — remains standard curriculum unchanged by time; only its ANSI C code examples carry the visible age of a pre-C99 book, making it both a complete first-year course text and a lasting reference for the mathematical foundations every later CS course builds on.

Book Overview

Chapter List

Chapter 1: Computer Science: The Mechanization of Abstraction

Difficulty: Easy · Discrete Math · Course Introduction · Key topics: abstraction, data models, data structures, algorithms, the C data model, programming style

Opens by defining computer science as “a science of abstraction” — creating the right model for a problem and devising mechanizable techniques to solve it — illustrated by modeling final-exam scheduling as a graph-coloring problem solved by repeatedly removing maximal independent sets. Introduces the book’s three problem-solving tools: data models (abstractions like graphs, trees, and logic), data structures (C constructs such as structures and pointers that implement data models), and algorithms. Surveys C’s own built-in data model — integers, floating-point numbers, structures, pointers — as only an approximation of the corresponding mathematical objects, and closes with programming-style guidelines and the C conventions (NULL, TRUE/FALSE, BOOLEAN) used throughout the rest of the book.

Key Points:

• Computer science is defined as “a science of abstraction” — creating the right model for a problem and devising mechanizable techniques to solve it.
• The book’s three problem-solving tools: data models (abstractions), data structures (language constructs that realize data models), and algorithms.
• The exam-scheduling example models courses as graph nodes and shared-student conflicts as edges, solved by repeatedly removing maximal independent sets.
• C’s own data model (integers, floats, structures, pointers) only approximates the corresponding mathematical objects, because of limited machine precision.
• NULL, TRUE/FALSE, and the BOOLEAN typedef are conventions defined here and assumed by every later chapter’s code.
• Good programming style: meaningful names, defined constants instead of magic numbers, avoiding global variables, and maintaining a test suite.

Memory Tip: Tie every new data structure you meet later in the book back to this chapter’s three-word chain — data model, then data structure, then algorithm — it is the lens the whole book uses.

Common Mistake: Treating this chapter’s C conventions (NULL, TRUE/FALSE, BOOLEAN, the DefCell macro) as optional — later chapters’ code listings assume these definitions are already in scope, so skipping Section 1.6 causes real confusion once linked-list code appears in Chapter 2.

Important Questions:

• What are the three problem-solving tools this book organizes itself around? Data models (abstractions such as graphs, trees, and logic used to describe a problem), data structures (the language constructs, such as C’s structures and pointers, used to represent those data models in a program), and algorithms (the techniques used to manipulate the data to obtain a solution).
• How does the exam-scheduling example use graph abstraction to solve a real problem? Courses become nodes and an edge connects two courses whenever some student takes both; each time slot is assigned to one maximal independent set of the remaining graph (a set of course nodes with no edges between them), and those nodes plus their incident edges are removed before finding the next maximal independent set, repeating until no nodes remain.

Chapter 2: Iteration, Induction, and Recursion

Difficulty: Medium · Discrete Math · Proof Technique · Key topics: iteration, inductive proofs, complete induction, recursive definitions, recursive functions, merge sort, program correctness

Covers three closely related ideas that recur throughout the book: iteration (looping), induction (a proof technique with a basis and an inductive step), and recursion (a function or definition that refers to itself). Works through selection sort as the iterative example and merge sort as the recursive, divide-and-conquer example, proving each correct by induction on the length of the list being sorted. Introduces complete induction, where the inductive step may assume the statement holds for every smaller value rather than just the immediately preceding one, needed for merge sort’s proof since it splits a list into two roughly half-sized pieces. Also proves properties of recursive C functions such as a linked-list constructor and the sum/find0 functions.

Key Points:

• Basis-induction: every inductive proof, recursive definition, and recursive program needs a basis (smallest case) and an inductive step (building larger cases from smaller ones).
• Complete induction lets the inductive step assume the statement holds for all smaller values, not just the one immediately before it — needed for merge sort’s proof.
• Selection sort is a simple O(n²) iterative sort; merge sort is a faster O(n log n) recursive, divide-and-conquer sort, fully analyzed in Chapter 3.
• A list can be defined recursively: the empty list is a list (basis), and an element followed by a list is a list (induction).
• Proving a recursive function like MakeList correct means proving a statement S(n) by induction on the length n of its input, using the recursive call as the inductive hypothesis.
• Expressions are classified by operator arity (unary, binary, k-ary) and position (infix, prefix, postfix).

Practice Tip: Trace the recursive sum and find0 functions from Fig. 2.32 by hand on a 3-element list before reading their inductive correctness proofs — watching the recursive call actually shrink the list to nothing makes the basis/induction split concrete instead of abstract.

Common Mistake: Assuming an inductive proof always needs a basis of exactly one value — the merge sort proof in this chapter needs both S(0) and S(1) as its basis, since splitting a list of length 0 or 1 has no recursive case at all.

Important Questions:

• Why does proving merge sort correct require complete induction rather than ordinary induction? Merge sort splits a list of length n into two sublists of roughly n/2 elements each, so its correctness proof for a list of length n+1 must assume the statement already holds for every smaller length up to n, not just for length n — exactly what complete induction allows and ordinary (weak) induction does not.
• What are the basis and inductive step of the proof that the sum of 1 through n equals n(n+1)/2? The basis is S(1): the sum 1 equals 1×2/2, that is, 1=1. The inductive step assumes S(n) — that the sum from 1 to n equals n(n+1)/2 — and shows it implies S(n+1), that the sum from 1 to n+1 equals (n+1)(n+2)/2, by adding n+1 to both sides of S(n).

Chapter 3: The Running Time of Programs

Difficulty: Medium · Discrete Math · Algorithm Analysis · Key topics: benchmarking vs analysis, Big-Oh notation, analyzing loops and function calls, recurrence relations, divide-and-conquer running time

Addresses how to measure and compare the efficiency of programs, contrasting benchmarking (running on representative sample inputs) with analysis (mathematically bounding running time as a function of input size). Introduces Big-Oh notation to state upper bounds on running time without needing machine-dependent constants, and gives rules for analyzing loops, conditionals, and function calls, building up to full C programs. Extends the analysis to recursive functions using recurrence relations, working merge sort’s O(n log n) bound as the central example, and closes with general rules of thumb for solving recurrences that arise from divide-and-conquer algorithms, plus the “90-10 rule” of profiling.

Key Points:

• Two ways to evaluate performance: benchmarking (representative sample inputs) and analysis (mathematically bounding running time as a function of input size n).
• Big-Oh notation gives an upper bound on running time, T(n) is O(f(n)), while hiding machine-dependent constants that are nearly impossible to pin down exactly.
• The “90-10 rule”: most programs spend about 90% of their running time in about 10% of their code, so profiling and optimizing only the hot spots gives the biggest speedup for the least effort.
• Recurrence relations model the running time of recursive functions; merge sort’s recurrence T(n) = 2T(n/2) + O(n) solves to O(n log n).
• Rule of thumb: O(1) work plus one recursive call on a subproblem of size n-1 gives O(n) total; two recursive calls with recursion depth log₂ n (as in merge sort) gives O(n log n).
• If a function calls itself twice and the recursion continues for n levels (as in the naive Fibonacci program), the running time is exponential in n.

Practice Tip: Take the selection-sort and merge-sort programs from Chapter 2 and actually count basic operations for n=4, 8, 16 by hand or with a counter variable in the code — watching O(n²) and O(n log n) diverge on real numbers makes Big-Oh notation feel concrete rather than symbolic.

Common Mistake: Treating Big-Oh upper bounds as exact running times — O(n²) only bounds the growth rate from above; two different O(n²) programs can run at very different actual speeds, so Big-Oh alone never tells you which one is faster in practice.

Important Questions:

• Why is Big-Oh notation useful for comparing algorithms even though it hides constant factors? Constants like the exact number of machine instructions a compiler generates per line are essentially impossible to determine and vary across machines and compilers, so Big-Oh notation focuses on how running time grows as input size n grows, a property of the algorithm itself rather than of any specific implementation or hardware.
• What is merge sort’s running time, and how is the recurrence that gives that answer set up? Merge sort’s running time is O(n log n), from the recurrence T(n) = 2T(n/2) + O(n): splitting and merging a list of length n takes O(n) work outside the two recursive calls, each on a list of about half the length; solving this recurrence, with the recursion running for log₂ n levels and O(n) work per level, gives O(n log n).

Chapter 4: Combinatorics and Probability

Difficulty: Medium · Discrete Math · Counting & Probability · Key topics: counting assignments, permutations, ordered/unordered selections, binomial coefficients, probability spaces, conditional probability, Monte Carlo algorithms

Introduces combinatorics (counting) and probability theory through paradigm problems: counting assignments of colors to houses (k^n), permutations of n distinct items (n!), ordered selections such as horse-race finishers, and unordered selections such as poker hands (binomial coefficients). Extends to arrangements with repeated items (anagrams) and distributing objects into bins, then turns to probability spaces, events, conditional probability, and independence, using the rules of sums and products to reason about compound events. Closes with applications to computer science, including why comparison-based sorting needs at least n log n comparisons, random number generators, and Monte-Carlo algorithms that trade a small, controllable error probability for guaranteed speed.

Key Points:

• The number of ways to assign one of k values to each of n items (painting n houses in k colors) is k^n; there are n! ways to order n distinct items.
• Selecting k items out of n and arranging them in order can be done in n!/(n-k)! ways; selecting m items out of n without regard to order (the binomial coefficient) can be done in n!/(m!(n-m)!) ways.
• A probability space consists of outcomes, each with a nonnegative probability summing to 1; an event is a subset of outcomes, and its probability is the sum of the probabilities of its outcomes.
• Event E is independent of event F if the conditional probability of E given F equals the plain probability of E.
• Any comparison-based sorting algorithm needs at least on the order of n log n comparisons to sort n items, since there are n! possible orderings to distinguish.
• Monte-Carlo algorithms use randomness to produce either a correct “true” answer or no answer at all; repeating the algorithm drives the probability of an incorrect “false” conclusion arbitrarily low, though never exactly to zero.

Memory Tip: Anchor each counting formula to the book’s own paradigm problem instead of memorizing it in isolation — k^n is “painting houses,” n! is “ordering horses,” n!/(n-k)! is “win-place-show,” and the binomial coefficient is “dealing a poker hand.”

Common Mistake: Using the permutation formula n!/(n-k)! when a problem actually calls for the combination formula n!/(k!(n-k)!), or vice versa — the test is whether order matters: horse-race finishing positions matter (permutation), but the five cards in a poker hand do not come in any order (combination).

Important Questions:

• How many ways can you select and arrange k items out of n, versus just selecting m items out of n? Selecting k items out of n and arranging them in order (the paradigm problem is picking win, place, and show horses in a race of n horses) can be done in n!/(n-k)! ways; selecting m items out of n without regard to order, such as dealing a poker hand, can be done in n!/(m!(n-m)!) ways — the second formula divides out the m! orderings of the selected items themselves, since their order does not matter.
• What is a Monte-Carlo algorithm, and how does repetition improve its reliability? A Monte-Carlo algorithm uses random choices to produce either the correct answer (“true”) or no definite answer at all (“false”), never a wrong “true.” By repeating the algorithm a fixed number of times and concluding “false” only if every repetition says “false,” the probability of wrongly concluding “false” when the answer is actually “true” can be driven as low as desired by choosing enough repetitions, though never to exactly zero.

Chapter 5: The Tree Data Model

Difficulty: Medium · Data Structures · Trees · Key topics: nodes, edges, root, parent/child, structural induction, binary trees, binary search trees, priority queues, heaps, heapsort

Introduces trees as the data model for hierarchical information, defining the standard vocabulary (root, parent, child, leaf, height, depth) both pictorially and by an equivalent recursive definition, then introduces structural induction as the proof technique matched to trees. Covers the two main tree-node representations (leftmost-child-right-sibling, and the array-of-pointers trie), then specializes to binary trees and binary search trees, which implement the dictionary abstract data type (insert, delete, lookup) efficiently. The chapter’s other major thread is the priority queue (insert, deletemax), implemented by a partially ordered tree and, concretely, by the array-based heap, leading to the O(n log n) heapsort algorithm with a full worked C implementation.

Key Points:

• A tree can be defined pictorially (nodes and edges satisfying connectivity properties) or recursively: a single node is a tree (basis), and a new root connected to the roots of one or more existing trees is a tree (induction).
• Structural induction proceeds on the number of nodes in a tree rather than on an integer n, the natural proof technique for tree-based algorithms.
• The binary search tree property: every label in a node’s left subtree precedes the node’s own label, and every label in its right subtree follows it, making dictionary operations efficient.
• A priority queue supports insert and deletemax; a partially ordered tree keeps every node’s label at least as great as its children’s labels.
• A heap is a balanced partially ordered tree implemented as an array, giving an O(log n) priority-queue implementation.
• Heapsort builds a heap from n elements in O(n) time via heapify, then calls deletemax n-1 times at O(log n) each, giving O(n log n) total.

Memory Tip: Keep the two tree families straight with one sentence each: a binary search tree is ordered left-to-right by value (for fast lookup), while a heap is ordered top-to-bottom by value (for fast max-extraction) — the balanced-shape rule is what makes the heap efficient, not a sibling ordering.

Common Mistake: Confusing the binary-search-tree property with the heap (partially-ordered-tree) property — a heap only guarantees a parent is at least as large as its children, so a heap’s left and right children have no ordering relationship to each other, unlike a BST where you can always say which subtree a search value falls into.

Important Questions:

• What is the binary search tree property, and why does it make lookup efficient? In a binary search tree, every label in a node’s left subtree precedes that node’s own label, and every label in its right subtree follows it; a lookup starts at the root and, at each node, compares the target to the node’s label to decide whether to recurse left, recurse right, or stop, discarding roughly half the remaining tree at each step rather than examining every node.
• Why does heapsort run in O(n log n) time overall? Building the initial heap from n unsorted elements via heapify takes O(n) time total (proved with a summation bound on calls to bubbleDown), and the sorting loop then calls deletemax exactly n-1 times, each costing O(log n) since the heap has height O(log n); n-1 calls at O(log n) each gives the dominant O(n log n) term.

Chapter 6: The List Data Model

Difficulty: Medium · Data Structures · Lists & Strings · Key topics: lists, linked lists, arrays, stacks, the run-time stack, queues, character strings, longest common subsequence, dynamic programming

Covers lists as sequences of elements, comparing linked lists and arrays as the two standard implementations and their tradeoffs, then specializes to the stack (insert/delete at one end only) and the queue (insert at one end, delete at the other). Uses the stack to explain, in detail, how C and similar languages implement recursive function calls behind the scenes via a run-time stack of activation records. Covers character strings as lists of characters with their own space-efficient data structures, and closes with the longest-common-subsequence problem, solved by dynamic programming — filling a table of subproblem answers in the right order — the technique behind the UNIX diff command.

Key Points:

• A list’s length counts positions, not distinct values; a k-times-repeated symbol adds k to the length.
• Linked lists and arrays are the two standard list implementations; a “sentinel” at the end of an array-based structure is a useful trick to guarantee a search terminates.
• The run-time stack of activation records is how C and similar languages implement recursive function calls — each call pushes a record, each return pops it.
• A stack restricts insertion and deletion to one end (last-in-first-out); a queue inserts at one end and deletes at the other (first-in-first-out).
• Dynamic programming fills a table of subproblem answers in a carefully chosen order, so each entry is computed in O(1) from previously filled entries, avoiding the exponential blowup of recomputing overlapping subproblems.
• The longest-common-subsequence algorithm (behind tools like UNIX diff) is a classic dynamic-programming table-filling algorithm.

Practice Tip: Trace a 3–4 line recursive function on paper while drawing its run-time stack frame by frame, one box per call — watching activation records get pushed on each call and popped on each return is the fastest way to see why recursion needs a stack at all.

Common Mistake: Confusing the head of a list (an element) with the length-1 list containing only that element (a list) — the two are different types, and treating them interchangeably is a common source of bugs when implementing list operations with linked cells.

Important Questions:

• How does dynamic programming avoid the exponential blowup of a naive recursive LCS solution? A naive recursive solution recomputes the same subproblems — the longest common subsequence of shorter and shorter prefixes — over and over, causing exponential blowup; dynamic programming instead fills a table of these subproblem answers in an order where each new entry depends only on already-filled entries, so every subproblem is solved exactly once, giving a polynomial-time algorithm.
• What is the run-time stack, and why does implementing recursive functions require one? The run-time stack is a stack of activation records, one per currently active function call, holding that call’s local variables and its return address; because a recursive function can have many calls to itself active at once, each waiting on the next, the language needs a last-in-first-out structure to remember exactly where each call should resume, and with what local state, once the calls beneath it on the stack return.

Chapter 7: The Set Data Model

Difficulty: Medium · Discrete Math · Sets & Relations · Key topics: set membership, set-former notation, atoms, linked-list/characteristic-vector/hash-table implementations, relations and functions, partial orders, equivalence relations, countable vs uncountable sets

Formalizes the set as computer science’s most fundamental data model, covering membership, the empty set, set-former (abstraction) notation, and the distinction between sets (unordered, no repeats) and lists. Compares the three standard set implementations — linked lists, characteristic vectors, and hash tables — on their relative efficiency, then reinterprets binary relations and functions as sets of pairs, covering reflexivity, symmetry, and transitivity, and the special cases of partial orders and equivalence relations. Closes with infinite sets, proving by Cantor’s diagonal argument that the real numbers are uncountable — strictly larger than the countably infinite natural numbers — a result later chapters on computation build on.

Key Points:

• A set former like {x | x is in S and P(x)} builds a set by abstraction: all elements of S satisfying property P.
• Sets differ from lists in two ways: order is irrelevant, and no element can be repeated.
• The three set implementations — linked lists (flexible), characteristic vectors (fast, only for small universal sets), and hash tables (usually the best balance) — trade off differently across operations.
• A (binary) relation is a set of pairs; a function is a relation with at most one pair for any given first component.
• A partial order and an equivalence relation are two of the most important special properties a binary relation can have (reflexivity and transitivity, plus antisymmetry for partial orders or symmetry for equivalence relations).
• Cantor’s diagonal argument proves the real numbers are uncountable: any hypothetical listing of the reals can be used to construct a real number that differs from every row of the list, so no one-to-one correspondence with the natural numbers can exist.

Memory Tip: Picture Cantor’s diagonal argument literally as walking down a diagonal of a table of decimal digits, changing each digit you pass to build a number guaranteed to differ from every row in at least one place — that mental picture is the entire proof in one image.

Common Mistake: Writing a set with repeated elements, like {1, 2, 2}, as if it means something different from {1, 2} — a set cannot have an element occur more than once; if repetition matters, the right data model is a multiset (bag) or a list, not a set.

Important Questions:

• What makes a hash table usually the implementation of choice for representing a set? Hash tables generally provide both economy of representation (unlike characteristic vectors, they don’t need space proportional to the size of the entire universal set) and speed of access close to O(1) for insert, delete, and lookup on average, striking a better balance across common set operations than either linked lists (flexible but slower for lookup) or characteristic vectors (fast but only practical when the universal set is small).
• How does Cantor’s diagonal argument prove the real numbers are uncountable? Assuming for contradiction that all real numbers between 0 and 1 could be listed against the natural numbers in a table of their decimal digits, the argument constructs a new real number r by choosing its i-th digit to differ from the i-th digit of the i-th real in the list; this r cannot equal any real already in the list, contradicting the assumption that the list contained every real number, so no such correspondence with the naturals can exist.

Chapter 8: The Relational Data Model

Difficulty: Medium · Discrete Math · Relational Data & Querying · Key topics: relations as tables, attributes, tuples, keys, primary/secondary indexes, relational algebra, query optimization

Introduces the relational data model — organizing information into two-dimensional tables (“relations”) with named columns (attributes) and rows (tuples) — as a generalization of the binary relations from Chapter 7 to arbitrary arity. Covers database design (choosing attributes to avoid redundancy), keys (attributes that uniquely determine a whole row), and primary and secondary index structures that speed up common operations. Introduces relational algebra (union, intersection, difference, selection, projection, and join) as a high-level query notation, then covers query optimization — using algebraic equivalences such as pushing selections down before joins — through a multi-relation registrar’s-database example.

Key Points:

• A relation is a table: its scheme is the set of column names (attributes), and its value is the set of rows (tuples); no two rows may be identical in every column.
• A key is a set of attributes whose values uniquely determine the values of every other attribute in the relation, central to database design.
• A primary index arranges a relation’s tuples in memory by a domain of attributes (often a key); secondary indexes support fast operations on other attributes.
• Relational algebra’s core operators are union, intersection, difference, selection (σ), projection (π), and join, composed to express arbitrarily complex queries.
• Query optimization applies algebraic laws — most importantly, pushing a selection down through a join to shrink intermediate relations as early as possible.
• The relational model, first proposed by Codd (1970), underlies SQL and systems like INGRES and System R, and also appears outside databases, e.g. in the UNIX awk command.

Memory Tip: Read every relational-algebra query right to left as a pipeline of tables: start from the base relations, apply each selection and join in turn, and picture the intermediate table at each step — that habit turns an opaque algebra expression into a readable, step-by-step recipe.

Common Mistake: Forgetting that a join can be evaluated in more than one equivalent order, and that the order matters enormously for efficiency — always push selections and projections as far toward the base relations as possible before an expensive join, rather than joining full tables first and filtering afterward.

Important Questions:

• What is a key, and why does it matter for database design? A key is a set of attributes whose values uniquely determine the values of all other attributes in a relation — no two rows can agree on every key attribute while differing anywhere else; keys matter because they let a primary index arrange a relation’s rows for fast lookup, and because good database design uses keys to decide how to split information across tables without introducing redundant, repeated facts.
• Why does pushing a selection down through a join usually speed up a relational algebra query? A selection (σ) filters a relation down to only the rows satisfying some condition, so applying it as early as possible, before an expensive join rather than after, shrinks the size of the intermediate relations the join has to process; since join cost typically grows with the sizes of its input relations, evaluating a smaller filtered relation in the join is cheaper than joining full relations and discarding most of the result afterward.

Chapter 9: The Graph Data Model

Difficulty: Medium · Discrete Math · Graph Algorithms · Key topics: directed/undirected graphs, adjacency lists/matrices, connected components, minimal spanning trees, depth-first search, topological order, Dijkstra’s algorithm, Floyd’s algorithm, graph coloring

Generalizes trees to graphs — nodes connected by edges or arcs — covering adjacency lists and adjacency matrices as the two standard representations, then a sequence of classic graph algorithms. Covers finding connected components and minimal spanning trees (Kruskal’s algorithm), then depth-first search as a general graph-exploration technique with three applications: detecting cycles, computing a topological order, and testing reachability. Covers Dijkstra’s algorithm for single-source shortest paths and Floyd’s algorithm for all-pairs shortest paths, and closes with undirected-graph concepts — coloring, chromatic number, cliques, and planarity — summarizing every algorithm’s running time in one reference table.

Key Points:

• A directed graph is a set of nodes plus a binary relation (arcs) on them; paths, cycles, and simple cycles are all defined as sequences of nodes connected by arcs.
• Depth-first search, run once, can detect cycles, compute a topological order for an acyclic graph, and test single-source reachability, each in O(m) time (m = edges).
• Kruskal’s algorithm finds a minimal spanning tree in O(m log n) time by repeatedly adding the cheapest edge that doesn’t create a cycle.
• Dijkstra’s algorithm finds single-source shortest paths in O(m log n) time with a priority-queue implementation; Floyd’s algorithm finds all-pairs shortest paths in O(n³) time using an adjacency matrix.
• The chromatic number of a graph is the fewest colors needed so no two adjacent nodes share a color; a clique is a set of nodes that are all pairwise connected.
• Adjacency lists and adjacency matrices are the two standard graph representations, with adjacency lists usually preferred for the sparse graphs most algorithms in this chapter assume.

Memory Tip: Keep the chapter’s own summary table in view while studying: connected components, cycle detection, topological order, and single-source reachability are all just depth-first search wearing a different hat — solving one well means you already understand the other three.

Common Mistake: Reaching for Floyd’s O(n³) all-pairs algorithm when only a single-source shortest path is actually needed — Dijkstra’s algorithm with a priority-queue implementation solves that in O(m log n), much faster on a sparse graph where m is well below n².

Important Questions:

• What three problems can be solved using a single depth-first search of a graph? A single depth-first search can detect whether a directed graph has a cycle, compute a valid topological order for the nodes of an acyclic graph, and determine which nodes are reachable from a given source node, each in O(m) time where m is the number of edges — depth-first search is a general exploration tool these three problems are all specific applications of.
• When should Dijkstra’s algorithm be preferred over Floyd’s algorithm for shortest paths? Dijkstra’s algorithm, run from a priority-queue implementation, finds shortest paths from a single source in O(m log n) time, while Floyd’s algorithm finds shortest paths between every pair of nodes in O(n³) time; if only single-source shortest paths are needed, Dijkstra’s algorithm is the better choice, especially on sparse graphs, and Floyd’s algorithm (or running Dijkstra’s n times) is reserved for when all-pairs distances are genuinely required.

Chapter 10: Patterns, Automata, and Regular Expressions

Difficulty: Medium · Discrete Math · Automata & Pattern Matching · Key topics: deterministic and nondeterministic finite automata, the subset construction, regular expressions, algebraic laws, converting automata to/from regular expressions

Introduces patterns as sets of strings and automata as a graph-based way to specify and recognize them, starting from a worked C program (and its equivalent state diagram) that tests whether a word contains the five vowels in order. Covers deterministic finite automata formally, then nondeterministic automata, and the subset construction that converts any nondeterministic automaton into an equivalent deterministic one. Introduces regular expressions as an algebraic notation (union, concatenation, and Kleene star) for the same class of patterns, and proves the three-way equivalence between deterministic automata, nondeterministic automata, and regular expressions.

Key Points:

• A deterministic finite automaton reads one input character at a time, moving between a finite set of states via labeled transitions, accepting a string if it ends in an accepting state.
• The subset construction converts any nondeterministic automaton into an equivalent deterministic automaton, whose states are sets of the original automaton’s states.
• Regular expressions are built from single characters, union (|), concatenation, and the Kleene star (*, zero or more repetitions), and describe exactly the languages finite automata can recognize.
• Three-way equivalence: a language is accepted by some deterministic automaton if and only if it is accepted by some nondeterministic automaton if and only if it is described by some regular expression.
• There is more than one regular expression for the same language; mechanically converting an automaton to a regular expression rarely gives the simplest possible expression.
• Regular expressions and finite automata underlie many real tools, from Ken Thompson’s original QED text editor through many UNIX commands and modern pattern-matching libraries.

Practice Tip: Take a 3–4 state deterministic automaton, write out its transition function as a table, and manually trace it on several test strings one character at a time, writing down the current state after each step — the fastest way to internalize what “accepting state” means at runtime.

Common Mistake: Assuming a nondeterministic automaton with n states, once converted via the subset construction, will also have close to n states — the subset construction’s states are sets of the original states, so the deterministic automaton can have up to 2^n states in the worst case, even though the blowup is usually much smaller in practice.

Important Questions:

• What does the subset construction do, and why can the result have exponentially many states? The subset construction converts a nondeterministic automaton into an equivalent deterministic automaton whose states are sets of states of the original automaton, tracking every state the nondeterministic automaton could possibly be in after reading a given input prefix; because a set of n original states has up to 2^n possible subsets, the deterministic automaton produced can in the worst case have exponentially many states.
• What three ways of describing a language are proven equivalent in this chapter? A language L is accepted by some deterministic finite automaton if and only if it is accepted by some (possibly nondeterministic) finite automaton if and only if L is exactly the language of some regular expression; the chapter proves all three directions, using the subset construction for nondeterministic-implies-deterministic and explicit constructions to convert between automata and regular expressions.

Chapter 11: Recursive Description of Patterns

Difficulty: Hard · Discrete Math · Grammars & Parsing · Key topics: context-free grammars, productions, parse trees, ambiguity, recursive-descent parsing, grammars vs regular expressions

Introduces context-free grammars as a third, more powerful way to describe patterns than automata or regular expressions, motivated by defining arithmetic expressions and used throughout the chapter to specify programming-language syntax. Covers grammar terminology (syntactic categories, terminals, productions, heads and bodies), parse trees as tree representations of a string’s grammatical structure, and ambiguity — when a string has two or more distinct parse trees, a real problem for language design. Introduces recursive-descent parsing for turning certain grammars into working parsers, and proves grammars strictly more expressive than regular expressions by showing balanced parentheses can be described by a grammar but by no regular expression.

Key Points:

• A context-free grammar has three parts: syntactic categories, terminals, and productions of the form head arrow body, where the body can use terminals and/or syntactic categories.
• A parse tree displays the grammatical structure a grammar assigns to a string; a string is ambiguous under a grammar if it has two or more distinct parse trees.
• Ambiguous grammars are undesirable for programming-language syntax, since a program’s meaning can then depend on which parse tree a compiler happens to choose.
• Recursive-descent parsing builds a parse tree top-down, one syntactic category at a time, and can be implemented as mutually recursive functions or a table-driven algorithm.
• Context-free grammars are strictly more expressive than regular expressions: languages like balanced parentheses can be described by a grammar but by no regular expression at all.
• Context-free grammars, also called Backus-Naur Form (BNF), were first used to define Fortran’s and Algol 60’s syntax and remain the standard tool for specifying programming-language syntax.

Practice Tip: Build the parse tree for a small expression like 2+3*4 by hand using the grammar in Fig. 11.1, then check whether a second, equally valid parse tree also exists — directly experiencing ambiguity on a tiny example makes the definition click faster than reading about it.

Common Mistake: Assuming a context-free grammar can express any rule a programming language needs, including something like “a variable must be declared before it is used” — such context-sensitive rules genuinely cannot be captured by a pure context-free grammar, which is why real compilers pair CFG-based parsing with a separate semantic-checking pass.

Important Questions:

• What does it mean for a string to be ambiguous under a grammar, and why is that a problem? A string is ambiguous under a grammar if it has two or more genuinely different parse trees according to that grammar’s productions; this is a problem for programming languages because a parse tree usually determines the program’s meaning, so an ambiguous grammar can let the same source code be interpreted in more than one way, which compiler writers must avoid or explicitly resolve.
• How does this chapter prove grammars are more powerful than regular expressions? It exhibits a language, the set of strings of properly balanced parentheses, that has a simple context-free grammar (a basis rule for the empty string and an inductive rule building larger balanced strings from smaller ones) but provably has no regular expression describing it, using an argument showing any hypothetical finite automaton for the language could be “fooled” into accepting an unbalanced string.

Chapter 12: Propositional Logic

Difficulty: Medium · Discrete Math · Logic & Proof · Key topics: Boolean algebra, truth tables, Karnaugh maps, tautologies, proof by contradiction/contrapositive, deduction, resolution

Introduces propositional logic as an algebra for reasoning, starting from simplifying C conditional expressions such as a < b || (a >= b && c == d) to motivate propositional variables and the AND/OR/NOT operators. Covers truth tables for representing and converting between logical expressions, the Karnaugh map for simplifying expressions of up to four variables, and an extensive set of algebraic tautologies. Shows how standard proof techniques — case analysis, the contrapositive, and contradiction — are themselves justified by specific tautologies, then introduces line-by-line deduction and resolution, closing by noting the tautology problem is NP-hard.

Key Points:

• Core logical operators: AND, OR, NOT, plus implication (→), equivalence (≡), NAND, and NOR; AND/OR/NOT correspond directly to C’s &&, ||, and !.
• A truth table lists an expression’s value for every combination of its operands’ truth values; any truth table can be converted mechanically into a logical expression.
• Karnaugh maps are a tabular technique for simplifying logical expressions of up to about four variables by visually grouping adjacent 1’s.
• Proof by contradiction, proof of the contrapositive, and proof by case analysis are all justified by specific tautologies of propositional logic, not separate ad hoc tricks.
• Resolution combines two clauses sharing a variable in opposite polarity to derive a new, shorter clause, useful for finding proofs by contradiction efficiently.
• The tautology problem (deciding if an expression is always true) is NP-hard, so no algorithm is known, or believed to exist, that solves it quickly in the worst case.

Memory Tip: Keep De Morgan’s laws literal: pushing a NOT through an AND turns it into an OR of the negations, and vice versa — write NOT(p AND q) equals (NOT p) OR (NOT q) from scratch a few times until the flip is automatic, since it underlies most proofs by contradiction.

Common Mistake: Treating an exhaustive truth-table check as the only way to establish a tautology — it works but only scales to a handful of variables; for anything larger, the chapter’s algebraic laws (De Morgan’s, distributivity, and the rest) are what make proofs of bigger propositional statements tractable by hand.

Important Questions:

• How does resolution let you find a proof by contradiction? Resolution combines two clauses that contain the same variable in opposite polarity (one has p, the other has NOT p) into a new clause containing everything else from both, minus that variable pair; starting from the hypotheses together with the negation of the desired conclusion, repeatedly applying resolution and eventually deriving the empty clause (a contradiction) proves the hypotheses together imply the original conclusion.
• Why can propositional logic fail to capture reasoning that relies on what < actually means? Propositional logic treats statements like a < b as opaque, atomic propositional variables with no internal structure, so it cannot see that a < b, a < c, and b < c are related through the transitivity of < itself; an argument relying on such a relationship is valid but cannot be verified using propositional logic alone — it requires predicate logic, covered in Chapter 14.

Chapter 13: Using Logic to Design Computer Components

Difficulty: Medium · Digital Logic · Circuit Design · Key topics: gates, combinational vs sequential circuits, divide-and-conquer adder and multiplexer design, memory elements

Applies propositional logic to digital circuit design, covering gates (AND, OR, NOT/inverter, NAND, NOR) as electronic devices computing a Boolean function, and how gates combine into circuits. Distinguishes combinational circuits (whose gate-connection graph has no cycles, so their behavior directly mirrors a logical expression) from sequential circuits (which can have feedback and can therefore remember state). Works through two divide-and-conquer circuit designs — a fast adder and a multiplexer — showing algorithm-design techniques transfer directly to hardware, and closes with the memory element, a sequential circuit built from ordinary gates that stores a bit until explicitly told to accept a new value.

Key Points:

• A gate is an electronic device computing one Boolean function of its inputs; AND-, OR- and NOT-gates (inverters) are the easiest to build, along with NAND- and NOR-gates.
• A circuit’s underlying directed graph (an arc from gate u to gate v whenever u’s output feeds v’s input) determines whether the circuit is combinational (acyclic) or sequential (has a cycle).
• Combinational circuits are the electronic equivalent of logical expressions and cannot remember any past input; sequential circuits can, because feedback lets output influence future output.
• Divide-and-conquer, the same technique used for merge sort, also designs efficient hardware — this chapter’s adder and multiplexer are both built this way.
• A memory element is built from ordinary AND/OR/NOT gates with feedback, controlled by a load signal: while load is 0 the output holds its value; when load is 1 the output tracks the input.
• Real memory chips pack millions of bits into a few square centimeters, with much of the chip’s area spent on selection circuitry to address a specific bit rather than on the memory elements themselves.

Memory Tip: Test for “combinational versus sequential” with one question: draw the circuit’s gate-to-gate graph and ask whether any arc chain leads back to where it started — a cycle means sequential (can remember state); no cycle means combinational (a logical expression in disguise).

Common Mistake: Assuming a circuit with gates wired in loops is automatically broken — feedback making a circuit sequential is a deliberate design choice, as in the memory element, not a mistake; the real mistake is not checking that a combinational circuit’s graph has no cycles at all.

Important Questions:

• What makes a circuit combinational rather than sequential, and why does that matter? A circuit is combinational if the directed graph formed by its gate-to-gate connections has no cycles, meaning no gate’s output can eventually reach back to its own input; this matters because a combinational circuit’s output depends only on its current input (the electronic equivalent of a logical expression), while a sequential circuit, which does have such a cycle, can remember past inputs, as the memory element in this chapter demonstrates.
• How does the memory element in this chapter use feedback to remember a bit? While the control signal load is 0, two gates feed each other’s output back around a loop so that whatever the circuit’s output currently is keeps circulating and being reproduced, holding its value; when load is set to 1, that feedback loop is broken and the output instead tracks the external input, so setting load back to 0 freezes whatever value the input had at that moment as the newly stored bit.

Chapter 14: Predicate Logic

Difficulty: Hard · Discrete Math · Advanced Logic & Limits of Proof · Key topics: predicates, atomic formulas, quantifiers, interpretations, tautologies of predicate logic, deduction, Godel’s incompleteness theorem, Turing’s undecidability theorem

Generalizes propositional logic to predicate (first-order) logic by allowing predicates — functions with arguments that return Boolean values — as atomic operands, motivated by an example about who takes an umbrella when it rains. Introduces quantifiers (“for all” and “there exists”), the interpretation (a domain plus meanings for predicates and free variables, the predicate-logic analog of a truth assignment), and tautologies and deduction in this richer system. Closes the book with two landmark negative results reached through the connection between provability and computability: Gödel’s Incompleteness Theorem and Turing’s theorem that some problems, such as whether a program halts, cannot be solved by any computer program at all.

Key Points:

• A predicate generalizes a propositional variable by taking arguments; an atomic formula is a predicate applied to zero or more arguments, which can be constants or variables.
• Predicate logic adds two quantifiers with no propositional-logic counterpart: “for all” and “there exists,” used to bind variables in an expression.
• An interpretation — a domain of values, a meaning for each predicate over that domain, and values for any free variables — plays the role a truth assignment plays in propositional logic.
• Predicate logic is expressive enough to represent database relations directly, e.g. csg(C,S,G) representing the Course-Student-Grade relation from Chapter 8 as a predicate.
• Gödel’s Incompleteness Theorem: for every sound proof system rich enough to express arithmetic, some true statement exists that the system cannot prove — a permanent limitation, not a temporary gap.
• Turing’s theorem shows some well-defined problems — the canonical example being whether a given program halts on a given input — cannot be solved by any computer program at all, no matter how much computing power is available.

Memory Tip: Hold the closing pair of results together as one sentence: Gödel’s theorem says some true statements can never be proven, and Turing’s theorem says some well-defined questions can never be answered by any program — both come from the same deep idea that a system cannot fully reason about something as complex as itself.

Common Mistake: Confusing “true but unprovable” with “not yet proven” — Gödel’s theorem is a permanent limitation of any sufficiently powerful, sound, fixed proof system, not a gap a cleverer mathematician working within that same system could eventually close with enough effort.

Important Questions:

• What is the difference between a propositional variable and a predicate? A propositional variable like p is a fixed statement that is simply true or false, with no internal structure, while a predicate like u(X) takes an argument and can be true for some values of X and false for others; this lets a single predicate stand in for what would otherwise be an infinite family of separate propositions, exactly the added expressiveness predicate logic needs to state general facts about every individual at once.
• What does Turing’s theorem establish, and what is its canonical example? Turing’s theorem establishes that there exist well-defined computational problems no computer program can solve correctly for every possible input, no matter how much time or computing power is allowed; its canonical example, developed via a hypothetical decider program that leads to a contradiction when fed its own complementer as input, is the halting problem — deciding, for an arbitrary program and input, whether that program eventually halts or runs forever.

Read or Download Foundations of Computer Science (C Edition) for Free

This book is free from its official source — after W. H. Freeman took it out of print, authors Alfred Aho and Jeffrey Ullman began hosting the complete set of chapter PDFs directly on Stanford’s InfoLab site, in their own words “welcome to use it if you like.” There is no single combined PDF, no current paid edition, and no other authorized copy; the authors’ own page below is the only legitimate free way to read or download it.

How to Study This Book

Chapters 1–4 are the mathematical-foundations backbone the rest of the book leans on — work through Chapter 2’s induction proofs by hand before Chapter 3’s running-time analysis, since Chapter 3’s recurrence-relation proofs for merge sort reuse Chapter 2’s induction machinery directly. Chapter 4 (combinatorics and probability) can be read somewhat independently of Chapters 2–3 if your course schedules it later.

Chapters 5–9 (trees, lists, sets, the relational data model, and graphs) are the book’s data-structures half, and each chapter follows the same shape: definitions, a matched proof technique, then one or two flagship algorithms — heapsort in Chapter 5, longest-common-subsequence in Chapter 6, hash tables in Chapter 7, relational algebra and query optimization in Chapter 8, and Dijkstra’s, Floyd’s, and depth-first search in Chapter 9. Chapter 8 doubles as a first, gentle introduction to databases and doesn’t strictly require Chapters 5–6 first.

Chapters 10–11 (automata, regular expressions, and grammars) form the book’s theory-of-computation slice — lighter than a dedicated automata theory course, but the natural bridge into one. Chapter 11 depends on Chapter 10’s automaton vocabulary throughout its expressiveness proof, so read them in that order rather than skipping ahead.

Chapters 12–14 (propositional logic, digital circuit design, and predicate logic) close the book. Chapter 13’s circuit design sits between two mathematical chapters and is the one part of the book that reads like a hardware, not software, course — it can be read more lightly if your course doesn’t cover digital logic. Chapter 14 assumes Chapter 12’s tautologies and deduction techniques are already solid before adding quantifiers on top of them.

The book’s own preface describes Stanford’s two-quarter CS109A/CS109B sequence, which splits cleanly at the Chapter 7/8 boundary: Chapters 1–7 for one course, Chapters 8–14 for the second. For a single-semester “CS2” course, the preface’s own suggested outline instead selects Sections 2.7–2.8, all of Chapter 3 except 3.11, Sections 5.2–5.10, all of Chapter 6, Sections 7.2–7.9 and 8.2–8.6, and Sections 9.2–9.9, skipping Chapter 4 and Chapters 10–14 entirely.

All code examples use ANSI C in a pre-C99 style — Section 1.6 defines its own NULL, TRUE/FALSE, and BOOLEAN conventions rather than relying on <stdbool.h>, which did not exist when this edition was written. Treat the code as clear, compilable illustrative C rather than idiomatic modern C, and expect to translate constructs like the DefCell macro into your own course’s preferred style if it uses a newer C standard.

If your course is short on time, Chapters 2, 3, 5, and 9 (induction/recursion, running time, trees, and graphs) form the spine that shows up in almost every downstream CS course; Chapters 4, 10, 11, and 13 are the ones most commonly trimmed to a lighter treatment when a single semester can’t fit all 14.

Used In These Programs

This book is used for Discrete Mathematics and Data Structures (CS2) coursework in BS Computer Science. Browse all Discrete Mathematics books or Data Structures books, or all Computer Science books.

Who Should Read This

Foundations of Computer Science is written for freshman and sophomore BSCS students, especially at universities that combine a CS2 (data structures) course with a discrete mathematics course into a single text, exactly how Stanford’s own CS109A/CS109B sequence used it. It assumes only a solid prior course in programming and comfort with ANSI C constructs — recursive functions, structures, pointers, and operators like -> and & — and builds trees, lists, sets, relations, graphs, automata, grammars, and both propositional and predicate logic from first principles. It is not a dedicated algorithms-design-and-analysis text, a full automata-theory text, or a database-systems text — each of Chapters 8, 9, 10, and 11 is closer to a first taste than a complete treatment, so students who want to go deeper into data structures and algorithms afterward are well served by a book such as Data Structures in C++ (Aikman Series) or Problem Solving with Algorithms and Data Structures using Python as a next step.

Applicable Universities

This book is useful for students at Pakistani universities offering BSCS programs with a Discrete Mathematics or Data Structures (CS2) core course, including Punjab University, Virtual University, COMSATS, FAST, UET, NUST, GIKI, LUMS, and other HEC-recognized institutions, and for self-learners who want a single, classic text covering both halves of a typical first-year theory-and-data-structures sequence.

FAQs

Related Books

• Data Structures in C++ – Aikman Series (the natural next step in the same procedural, C-family tradition, with a full course’s worth of depth on the data structures this book only introduces)
• Problem Solving with Algorithms and Data Structures using Python (the same trees, lists, and graph algorithms revisited in a language many students find easier to experiment in)
• Think Java – Downey & Mayfield (an object-oriented programming foundation for BSCS programs that pair this book’s procedural C with an early Java-based sequence)
• Think Python – Allen B. Downey (a gentler, interpreted-language companion for students who want to prototype this book’s data models before implementing them in C)

Foundations of Computer Science (C Edition) by Alfred V. Aho and Jeffrey D. Ullman is a free, classic discrete-math-and-data-structures textbook — covering induction and recursion, running-time analysis, trees, lists, sets, relations, graphs, automata, grammars, and propositional and predicate logic in 14 chapters, hosted directly by the authors after its original publisher took it out of print. Browse more Computer Science books for the rest of your semester.

Foundations of Computer Science, C Edition, by Alfred V. Aho and Jeffrey D. Ullman. Originally published 1994 by W. H. Freeman / Computer Science Press (ISBN 978-0-7167-8284-1), Principles of Computer Science Series; taken out of print by the publisher. No formal open licence applies — the authors state on their own official page, “You are welcome to use it if you like,” and host every chapter free to read online at its official source, https://infolab.stanford.edu/~ullman/focs.html