This guide covers C949 Data Structures and Algorithms I as one connected idea: an abstract data type promises a set of operations, a data structure keeps that promise, and an algorithm’s cost depends on which structure you chose. Many reported exam questions reduce to naming the structure, the operation, or the cost.

WGU’s June 2026 catalog describes C949 as the fundamentals of dynamic data structures (bags, lists, stacks, queues, trees, and hash tables) with their associated algorithms, object-oriented design and abstract data types as design paradigms, and techniques for designing efficient, maintainable software, with students implementing simple applications. (wgu.edu)

Each teaching chapter opens with a scope note naming the course source that covers it. Sections marked Supplemental (and † in the Contents) go beyond what those sources name; they make the course material easier to understand, but no source here establishes that the exam tests them. The current WGU course materials take precedence, especially because student reports describe more than one course version.

Reading route. Each part uses the ideas before it:

1. ADTs promise operations; Python supplies the notation; classes bundle data and operations. Analysis counts their cost, including recursive calls.
2. Searching and sorting apply those costs. Arrays and linked lists explain why the same operation can be cheap in one structure and expensive in another. Restrict their operations to get stacks and queues.
3. Hashing locates keys without sorted order. Trees introduce branching; BSTs add key order; balance keeps searches short. Heaps keep only priority order.
4. Graph algorithms reuse stacks, queues, and priority queues; Huffman coding combines priority queues and trees. Finish with the design strategies these algorithms illustrate. Chapters 22 and 23 are quick references.

Part IFoundations#

1Course map and sources#

Scope. Orientation. Read once, then come back to 1.3 when a scope note puzzles you.

1.1What WGU says C949 covers#

The public catalog description names four areas of course content:

1. Dynamic data structures and their algorithms: bags, lists, stacks, queues, trees, and hash tables. “Dynamic” means the structure grows and shrinks while the program runs, as opposed to a fixed-size array declared once.
2. Design paradigms: object-oriented design and abstract data types.
3. Problem-solving for efficient, maintainable software: choosing structures by their costs, and writing code someone else can change safely.
4. Simple implementations: building small applications with these techniques.

C949 is 4 competency units and sits in the B.S. Computer Science and B.S. Software Engineering programs, among others. Its sequel, C950 Data Structures and Algorithms II, takes up graphs, hashing, self-adjusting structures, and dynamic programming in more depth, with C949 and C960 Discrete Mathematics II as prerequisites.

1.2Course materials and assessment#

Students report that C949 uses an interactive zyBook and describe at least two course versions: in v3, chapter 1 is “Introduction to Python”; in v4, it is “Introduction to Data Structures & Algorithms”. In v4, students describe roughly the first eleven chapters as the data structures and algorithms core, followed by Python chapters (which students who already know Python skip), then chapters on classes and recursion. The course’s current zyBook is behind WGU login, so this guide could not confirm which version Alan has.

The v4 chapter 1 title, and the topics students list for the core (lists, stacks, queues, hash tables, trees including balanced trees and heaps, sets, graphs, B-trees, algorithm analysis), match the public table of contents of the zyBooks title Data Structures in Pseudocode: introduction to data structures and algorithms; searching and algorithm analysis; sorting; lists; stacks and queues; hash tables; trees; balanced trees; heaps and treaps; graphs; and algorithms such as Huffman compression, greedy methods, and dynamic programming. That match suggests the v4 core follows this book. It is an inference: the course’s own zyBook sits behind a login, and this guide could not check it directly.

Student reports describe the assessment as a proctored objective assessment with multiple-choice questions, and the pre-assessment as a close preview. Treat those as reports, not a guaranteed description of the current course version. Students say the OA asks them to read code: trace a Python or pseudocode snippet, name the algorithm or structure, state its Big-O cost, or match a description to a term.

1.3How this guide marks scope#

Each chapter’s scope note cites one or more of these sources, from strongest to weakest evidence:

The point of the labels is triage. If time is short, master what the catalog and study guide name, read what only the zyBook covers for recognition (definitions and costs, not step-by-step cases), and skip the † sections.

1.4How to study for a code-reading exam#

If the current OA resembles the student reports above, three habits help more than passive reading:

• Read the traces. Worked traces accompany binary search; selection, insertion, merge, and radix sort; heap insert and remove; BFS; and Dijkstra. Follow them alongside the code or described steps. For algorithms without a trace, such as bubble sort, shell sort, and quicksort partition, work a small input by hand and record each step. Do the same whenever a provided trace leaves a step unclear.
• Know the identifying property. Each structure has one property that defines it: last in, first out; keys mapped to values; left subtree smaller than the node. Exam stems paraphrase that property and ask for the name.
• Attach a cost to every operation. “Insert at the front of an array” should immediately read as O(n) because everything shifts. Chapter 22 collects these costs in one place.

2Data structures, algorithms, and ADTs#

Scope. Catalog (abstract data types); study guide (algorithm characteristics, ADTs, records, arrays versus linked structures).

2.1Data structures#

A data structure is a way of organizing, storing, and operating on data. The organization decides which operations are cheap. A phone book sorted by surname makes finding a surname fast and finding a phone number slow; the same entries in a different organization would reverse that.

A record deserves a second look because the exam defines it by its access style: a record stores subitems, called fields, each with an associated name. An array’s items are reached by position; a record’s by name.

student = {"name": "Ada", "student_id": 1815, "program": "BSCS"}
student["program"]     # field access by name: a record
grades = [91, 84, 77]
grades[1]              # element access by position: an array

2.2Algorithms and their characteristics#

An algorithm is a finite sequence of well-defined steps that solves a problem. A recipe is the everyday version, and its failure modes show why each formal property matters. “Bake until done” is not definite; “stir forever” is not finite.

Beyond those defining properties, good algorithms are judged on correctness (right answer for every valid input), efficiency (time and memory), simplicity and clarity, modularity (built from parts that can be understood and replaced separately), maintainability, robustness (sensible behavior on bad input), and extensibility. The catalog’s phrase “efficient, maintainable software” is a pair of these.

Two ideas recur in algorithm questions:

• A computational problem specifies an input, a question about it, and the desired output. “Given a list of numbers, return the largest” is a problem; a loop that tracks a running maximum is one algorithm for it.
• Some problems have no known efficient algorithm. Finding the shortest route that visits every city once (the traveling salesperson problem) is one: no polynomial-time algorithm for it is known. Its yes-or-no version (“is there a route shorter than L?”) is NP-complete; the find-the-shortest version is NP-hard, at least as hard. For such problems practical code settles for heuristics: fast methods that give good, not guaranteed-best, answers.

2.3How structures and algorithms relate#

Algorithms operate on data structures, and a structure is only as useful as the algorithms that run on it. The relation runs both ways:

• Some algorithms need a particular structure. Binary search needs a sorted array with constant-time indexing; on a linked list it gains nothing, because reaching the middle element already costs a walk.
• Some structures exist to make an algorithm cheap. A heap exists so that reading the largest remaining item costs O(1) and removing it costs O(log n); an unsorted list needs O(n) just to find it.
• Each structure comes with its own algorithms: insert, remove, search, traverse. Studying a structure means studying those algorithms and their costs.

2.4Abstract data types#

An abstract data type (ADT) specifies what operations a data type supports, and what they mean, without saying how they are implemented. It is a contract. A stack ADT promises push, pop, and peek, with last-in-first-out behavior; it says nothing about arrays or nodes.

A restaurant menu is the analogy that sticks. The menu lists dishes (operations) and what you get (behavior). The kitchen (implementation) can change cooks, ovens, or suppliers, and diners never notice as long as the dishes come out the same.

The benefits follow from that separation:

• Client code can focus on higher-level operations and algorithms instead of storage details.
• Client code does not depend on internal implementation details.
• The implementation can be swapped (an array-based stack for a linked one, say) without changing client code that uses the ADT interface.

“ADT versus data structure” is a distinction questions often draw. A queue is an ADT; a circular array is a data structure that can implement it. When a question asks which is “abstract”, look for the one defined only by its operations. Most of this guide follows the same three steps for each ADT: state its promise, build structures that keep it, and compare what each structure charges.

2.5ADTs in Python#

Python’s built-in types are ready-made implementations of common ADTs, which is why C949 can use Python to illustrate them:

Using a list as a queue works but costs O(n) per dequeue, because pop(0) shifts every remaining element. That one fact is a good test of whether the ADT/implementation split has landed: the queue ADT is fine, the chosen implementation is the problem.

3Reading Python#

Scope. Study guide (operator precedence, identifiers, lists and tuples, slicing, sorted versus sort, loop tracing); zyBook reports (Python chapters). Student reports describe Python and pseudocode reading on the OA; the current assessment format is unverified.

3.1Identifiers#

An identifier is a name for a variable, function, class, or module. Python’s rules:

• Use only letters, digits, and underscores.
• Do not start with a digit.
• Do not use a reserved keyword (class, def, if, for, while, return, True, None, and, or, not, in, is, lambda, and others).
• Names are case-sensitive: total and Total are different.

Convention (PEP 8, not a rule): snake_case for variables and functions, PascalCase for classes, UPPER_CASE for constants.

3.2Operators and precedence#

Python evaluates higher-precedence operators first; equal precedence groups left to right, except **, which groups right to left. From highest to lowest:

Worked example: in a + b * c ** 2 > 40, Python computes c ** 2 first, then multiplies by b, then adds a, then compares. Two traps: -2 ** 2 is -4 (exponent before unary minus), and 2 ** 3 ** 2 is 2 ** 9 = 512 (right to left).

Division has three forms: 7 / 2 is 3.5 (always a float), 7 // 2 is 3 (floor division), and 7 % 2 is 1 (remainder). Floor division rounds toward negative infinity, so -7 // 2 is -4. The // operator is everywhere in this course: midpoints in binary search, parent indexes in heaps.

3.3Types, mutability, lists, and tuples#

Every Python value is an object with a type. Some types are mutable (the object can change in place) and some are immutable (any “change” creates a new object).

The list-versus-tuple distinction in one line: lists are mutable; tuples are immutable. Both are ordered sequences indexed from 0. Use a tuple for a fixed record (a coordinate pair, a database row) and a list for a collection that grows. A tuple can be a dictionary key or set member when everything inside it is hashable: (3, 4) works, but ([1], 2) raises TypeError because of the list inside. A list can never be a key (3.6).

point = (3, 4)
point[0] = 9          # TypeError: tuple does not support item assignment
scores = [3, 4]
scores[0] = 9         # fine: scores is now [9, 4]
one = (5,)            # one-element tuple needs the comma; (5) is just 5

Variables hold references to objects. Assignment copies the reference, not the object, so two names can share one list:

a = [1, 2, 3]
b = a                 # b and a name the same list
b.append(4)
print(a)              # [1, 2, 3, 4]
c = a[:]              # slice makes a (shallow) copy
c.append(5)
print(a)              # still [1, 2, 3, 4]

This aliasing is exactly how linked structures work. Chapter 4 builds a Node object whose next attribute is a reference to another node, and chapter 9 chains such nodes into lists: a.next = b copies a reference, just as b = a does here.

3.4Indexing and slicing#

Indexes start at 0; negative indexes count from the end (-1 is the last item). A slice s[start:stop:step] includes start and excludes stop. Omitted bounds default to the ends.

s = [10, 20, 30, 40, 50, 60]
s[1:4]      # [20, 30, 40]      indexes 1, 2, 3
s[:3]       # [10, 20, 30]      first three
s[3:]       # [40, 50, 60]      from index 3 to the end
s[-2:]      # [50, 60]          last two
s[::2]      # [10, 30, 50]      every second item
s[::-1]     # [60, 50, 40, 30, 20, 10]   reversed copy
s[4:1]      # []                start past stop with positive step

A quick check: s[a:b] holds b - a items when 0 ≤ a ≤ b ≤ len(s) and the step is 1. Otherwise convert negative bounds (add len(s)) and clip to the list first; if a still ends up at or past b, the slice is empty, as s[4:1] shows. Slicing never raises an index error; out-of-range bounds are clipped. Indexing does raise one: s[6] on a six-item list fails.

Slicing creates a new list, which costs O(k) for a slice of length k. A recursive function that slices its input on every call is quietly paying that copy cost each time.

3.5sorted() versus .sort()#

The classic mistake is nums = nums.sort(), which sorts the list and then sets nums to None. Both accept reverse=True and a key function (sorted(words, key=len) sorts by length). Both use Timsort, which is stable and O(n log n).

3.6Dictionaries and sets#

stock = {"apple": 5, "pear": 2}
stock["fig"] = 7            # insert or overwrite: O(1) average
stock["apple"]              # 5; missing key raises KeyError
stock.get("kiwi", 0)        # 0; get() returns a default instead
"pear" in stock             # True; tests keys, O(1) average
del stock["pear"]
for name, qty in stock.items():
    print(name, qty)        # insertion order is preserved (Python 3.7+)

seen = {3, 1, 4}
seen.add(1)                 # no effect: sets hold distinct items
{1, 2} | {2, 3}             # union        {1, 2, 3}
{1, 2} & {2, 3}             # intersection {2}
{1, 2} - {2, 3}             # difference   {1}

Both use hash tables underneath (chapter 12), which is why membership tests are O(1) on average, while x in some_list is O(n). Built-in mutable collections such as lists, dictionaries, and sets cannot be keys; tuples can be keys if all their contents are hashable. Custom objects may also be keys when their equality and hash remain consistent.

3.7Control flow and tracing#

Exam snippets combine a loop, a condition, and an accumulator. Trace them with a table: one column per variable, one row per iteration. Watch for break (leave the loop now), continue (skip to the next iteration), and range bounds (range(a, b) stops before b).

values = [4, 7, -1, 9, 6]
total = 0
count = 0
for v in values:
    if v < 0:
        break               # stops at -1; 9 and 6 are never seen
    total += v
    count += 1
print("Mean:", total / count)

Output: Mean: 5.5. It is a float because / always produces one. With continue in place of break, the loop would skip −1 but go on to 9 and 6, giving total 26, count 4, and Mean: 6.5. One keyword, a different answer: exam distractors are built from exactly this kind of misreading.

Other forms worth recognizing on sight: while loops with a manual counter, for i in range(len(xs)) (index-based iteration), enumerate(xs) (index and value together), and list comprehensions such as [x * x for x in xs if x % 2 == 0] (squares of the even items).

3.8Functions, parameters, and scope#

A function receives references to its arguments. Rebinding a parameter inside the function does not affect the caller; mutating the object it refers to does:

def rebind(xs):
    xs = [0]          # local name now points elsewhere; caller unaffected

def mutate(xs):
    xs.append(0)      # changes the caller's list

data = [1]
rebind(data)          # data is still [1]
mutate(data)          # data is now [1, 0]

A name assigned inside a function is local to it unless declared global or nonlocal. A function without a return statement returns None. Exceptions (try/except) let code handle errors such as popping an empty stack; a well-designed ADT documents which operations raise and when.

4Object-oriented design#

Scope. Catalog (object-oriented design as a design paradigm; efficient, maintainable software); study guide (overloaded methods); zyBook reports (classes chapter).

4.1Classes and objects#

A class is a blueprint that bundles data (attributes) with the operations on that data (methods). An object is one instance built from the blueprint. The class Node describes what every node has; each node in a linked list is an object.

class Node:
    def __init__(self, data):      # constructor: runs when an object is created
        self.data = data           # instance attribute
        self.next = None

a = Node(5)                        # instantiate
b = Node(9)
a.next = b                         # objects refer to other objects

self is the object the method is running on. Python passes it automatically: a.method(x) is Node.method(a, x). An instance attribute (self.data) belongs to one object; a class attribute, assigned in the class body, is shared by all instances.

4.2Encapsulation and information hiding#

Encapsulation keeps an object’s data and the code that manipulates it together, and hides the internals behind a public interface. That is the ADT idea, enforced in code: callers use push and pop, never the internal array.

Python does not enforce privacy. By convention, a leading underscore (self._items) marks an attribute as internal; a double underscore triggers name mangling, which makes accidental access from outside harder. Either way the intent is the same: if callers cannot depend on internals, you can change them later.

class Stack:
    def __init__(self):
        self._items = []           # internal; callers should not touch it

    def push(self, item):
        self._items.append(item)

    def pop(self):
        return self._items.pop()

    def peek(self):
        return self._items[-1]

    def is_empty(self):
        return len(self._items) == 0

    def __len__(self):             # lets callers write len(stack)
        return len(self._items)

4.3Inheritance and polymorphism#

Inheritance lets a subclass reuse and extend a superclass: class Deque(Queue): starts with everything a Queue has and adds operations at the other end. The relationship should read as “is a”: a deque is a queue with more abilities. When the relationship is “has a” (a stack has a list), use composition: store the other object as an attribute.

Polymorphism means code written against an interface works with any object that provides it. A function that calls len(x) and iterates over x works on lists, tuples, sets, and any class defining __len__ and __iter__. Python calls this duck typing: if it supports the operations, it qualifies.

4.4Overloading and overriding#

Overloaded methods share a name but differ in their parameter lists, so the call’s arguments decide which one runs. Java and C++ support this directly. Python keeps only the last definition of a name, so Python code gets the same effect with default or variable arguments:

def area(width, height=None):     # one name, two calling forms
    if height is None:
        return width * width       # area(4)    -> square
    return width * height          # area(4, 3) -> rectangle

Overriding happens across an inheritance relation: a subclass defines a method with the same name and a compatible signature, and calls on subclass objects use the subclass version. Python’s operator overloading uses special methods: __eq__ and __lt__ define how == and < work on your objects. The related protocol method __len__ supplies their behavior for len().

4.5Designing efficient, maintainable software#

The catalog pairs “efficient” with “maintainable”, and the pairing is deliberate: fast code loses its value once nobody can safely change it. The working principles:

• Abstraction: program against the ADT, not the implementation, so the implementation can change.
• Modularity: split the program into units with one job each (high cohesion) that know little about one another (low coupling).
• Information hiding: expose the smallest interface that works.
• Simplicity: choose the simplest structure that meets the cost requirement. A list scanned linearly is fine for twenty items; a hash table is warranted for twenty million lookups.
• Efficiency by selection, not cleverness: the large wins come from choosing the right structure (O(1) lookups instead of O(n)), not from micro-optimizing a loop.

4.6Worked example: a bag as a class#

A bag (or multiset) is the simplest collection the catalog names: it holds items without order, allows duplicates, and answers “how many of these?”. It shows every idea of this chapter in a dozen lines.

class Bag:
    """Unordered collection that allows duplicates."""

    def __init__(self):
        self._counts = {}                      # item -> how many
        self._size = 0

    def add(self, item):
        self._counts[item] = self._counts.get(item, 0) + 1
        self._size += 1

    def remove(self, item):
        if self._counts.get(item, 0) == 0:
            raise KeyError(item)
        self._counts[item] -= 1
        self._size -= 1
        if self._counts[item] == 0:
            del self._counts[item]

    def count(self, item):
        return self._counts.get(item, 0)

    def __len__(self):
        return self._size

    def __contains__(self, item):              # enables: item in bag
        return item in self._counts

Callers see add, remove, count, len, and in. Internally the bag uses a dictionary of counts, so each operation is O(1) on average. A version storing items in a plain list would keep the same interface but make count O(n). Same ADT, different implementation, different cost: the chapter’s whole argument in one class.

5Algorithm analysis and Big-O#

Scope. Study guide (Big-O; simplifying expressions; linear and binary search costs; space complexity and auxiliary space). The most heavily weighted skill in student reports. Sections 5.7 and 5.8 are supplemental.

5.1Why count operations#

Timing code with a stopwatch measures the machine as much as the algorithm. Instead we count how many basic steps the algorithm takes as a function of the input size n, and ask how that count grows. A constant-time operation takes the same time regardless of n: arithmetic, a comparison, an assignment, reading a[i], calling a function (not running it). These costs use the usual unit-cost model for fixed-size values; counting individual bits of arbitrarily large integers is a different model.

Not everything that looks like one step is constant. In Python, x in some_list, some_list.index(x), some_list.insert(0, x), slicing, and string concatenation in a loop all hide a loop over the data.

5.2Growth rates#

For small inputs nearly any algorithm is fast. Analysis asks what happens as n becomes large, where growth rates separate sharply:

The logarithm column is the one to internalize: log₂ of a million is about 20. Halving a million items repeatedly reaches one item in about twenty steps, which is why binary search on a million sorted records needs at most twenty comparisons (7.2).

5.3O notation and the simplification rules#

O(g(n)) is an upper bound on growth: f(n) is O(g(n)) if, beyond some input size, f(n) never exceeds a constant multiple of g(n). In practice you find the step count and simplify with two rules:

1. Keep only the fastest-growing term. 3n² + 40n + 900 is O(n²); for large n the square dominates everything else.
2. Drop constant factors. 500n is O(n); 5n + 9n + 200 = 14n + 200 is O(n). A constant on its own, however large, is O(1).

Why drop constants? They are real, and they come from the machine, the language, and sometimes the algorithm itself (one comparison per item versus three). O notation drops them because it asks a narrower question: how the cost grows. Doubling n doubles a 500n algorithm’s time just as it doubles a 2n one, and that ratio is what O notation captures. Two algorithms in the same class can still differ several-fold in practice.

Two more combination rules:

• Different inputs keep different letters: looping over a list of size n and then a list of size m is O(n + m), not O(n).
• Logarithm bases do not matter: log₂n and log₁₀n differ by a constant factor, so both are O(log n).

5.4Reading the cost off code#

Four patterns cover most exam snippets:

def pairs(xs):                        # O(n^2)
    for i in range(len(xs)):
        for j in range(i + 1, len(xs)):
            print(xs[i], xs[j])        # runs n(n-1)/2 times

def halvings(n):                      # O(log n)
    steps = 0
    while n > 1:
        n //= 2
        steps += 1
    return steps

def mixed(xs):                        # O(n log n): n outer x log n inner
    for x in xs:
        k = len(xs)
        while k > 1:
            k //= 2

The triangular loop in pairs is a frequent trap: the inner loop shrinks, so the count is 0 + 1 + … + (n − 1) = n(n − 1)/2, which is still O(n²).

5.5Best, worst, and average case#

The same algorithm can do very different amounts of work on different inputs of the same size. Linear search finds its target at index 0 in one comparison (best case) or not at all after n comparisons (worst case); averaged over all positions it makes about n/2 (average case, still O(n)).

Two separate questions hide in a phrase like “linear search is O(n)”. Which inputs? Best, worst, or average case. What kind of bound? O is an upper bound; Ω and Θ (5.7) are others. Big-O is not another name for the worst case: “the best case is O(1)” is a correct sentence. Unless a question says otherwise, though, a single cost quoted for an algorithm describes its worst case, because that is a guarantee. The exceptions worth memorizing are where the average differs from the worst in a way that matters: quicksort (O(n log n) average, O(n²) worst), hash tables (O(1) average, O(n) worst), and insertion sort (O(n) best on sorted input).

5.6Space complexity#

Space complexity counts memory as a function of n. Auxiliary space counts only the extra memory the algorithm uses beyond its input. Exam questions usually mean auxiliary space.

def total(xs):              # O(1) auxiliary: one accumulator
    s = 0
    for x in xs:
        s += x
    return s

def evens(xs):              # O(n) auxiliary in the worst case:
    out = []                # if every item is even, out grows to n
    for x in xs:
        if x % 2 == 0:
            out.append(x)
    return out

Recursion uses space too: each active call holds a stack frame. A recursion that goes n calls deep needs O(n) stack space even if each call stores nothing else. Count the calls that are alive at the same time, not the total number of calls: naive recursive Fibonacci makes O(2ⁿ) calls but never has more than n on the stack, so its space is O(n).

5.7Big-Omega and Big-Theta#

O gives an upper bound, Ω (Big-Omega) a lower bound, and Θ (Big-Theta) both at once. Linear search is O(n) and Ω(1) over all inputs; its worst case is Θ(n). Merge sort always does Θ(n log n) work. When people say “quicksort is O(n log n)” they usually mean its average case is Θ(n log n); strictly, its worst case is Θ(n²).

5.8Amortized cost#

Some operations are usually cheap and occasionally expensive. A dynamic array’s append costs O(1) until the array is full, then O(n) to copy everything into an array twice as large. Doubling means the expensive copies get rarer as the array grows: after n appends, the copies total at most 1 + 2 + 4 + … + n < 2n element moves. Spread across n appends, that is a constant per append: amortized O(1).

6Recursion#

Scope. Study guide (recursion; recurrence relations); zyBook reports (recursive definitions, recursive algorithms, and their analysis; a recursion chapter).

6.1Base case and recursive case#

A recursive function solves a problem by calling itself on a smaller instance of the same problem. Every correct recursion has two parts:

• A base case that answers directly, without recursing.
• A recursive case that reduces the problem and calls itself, making progress toward the base case.

def factorial(n):
    if n <= 1:                     # base case
        return 1
    return n * factorial(n - 1)    # recursive case: smaller n

Missing the base case, or a recursive case that does not shrink the problem, produces infinite recursion; Python stops it with a RecursionError when the call stack exceeds its limit (about 1,000 frames by default).

6.2Tracing recursion and the call stack#

Each call gets its own frame on the call stack holding its parameters and local variables. Calls go down until a base case returns; results then come back up in reverse order. Tracing factorial(4):

factorial(4)
  4 * factorial(3)
        3 * factorial(2)
              2 * factorial(1)
                    returns 1          base case
              returns 2 * 1 = 2
        returns 3 * 2 = 6
  returns 4 * 6 = 24

When tracing an exam snippet, write each call on its own line, indented by depth, and fill in return values on the way back up. Work done before the recursive call happens on the way down; work after it, on the way back up. Printing before the call prints in descending order; printing after prints in ascending order.

6.3Common recursive algorithms#

Recursion fits problems whose structure is self-similar: a list is a first item plus a smaller list; a tree is a root plus smaller trees.

def fib(n):                         # two recursive calls per call
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

def binary_search(xs, target, low, high):
    if low > high:
        return -1                    # base case: empty range
    mid = (low + high) // 2
    if xs[mid] == target:
        return mid                   # base case: found
    if xs[mid] < target:
        return binary_search(xs, target, mid + 1, high)
    return binary_search(xs, target, low, mid - 1)

def count_down(n):
    if n == 0:
        return
    print(n)                         # before the call: prints n, n-1, ..., 1
    count_down(n - 1)

Other recursive classics in data structures courses: summing or reversing a linked list, tree traversals (chapter 14), merge sort and quicksort (chapter 8), and generating permutations or subsets by choosing each element in or out.

6.4Recurrence relations#

A recursive function’s running time is naturally described by a recurrence: T(n) in terms of T on smaller inputs plus the work done in one call. Solving it means counting levels of recursion and the work at each level.

The level count follows from how the argument shrinks. Subtracting k each time takes n/k levels to reach zero: a recursion on n − 5 has n/5 levels, still O(n) levels. If a subtract-k recursion also does O(n) work per call, the total is at most (n/k) × n = O(n²) time, and since the calls are nested, O(n) stack space. Dividing by b each time takes log_bn levels.

The two halving rows with linear work look alike and differ by a factor of log n. Merge sort splits into two halves and recurses on both, so every level still holds all n elements: n work times log n levels. A recursion into one half does shrinking work, n + n/2 + n/4 + … < 2n, which is O(n). For Fibonacci, replacing T(n − 2) by the larger T(n − 1) gives 2T(n − 1) + c, whose solution grows proportionally to 2ⁿ, giving an upper bound. The tighter Fibonacci growth is Θ(φⁿ), where φ = (1 + √5)/2 ≈ 1.618; it is still exponential.

6.5Recursion versus iteration#

Any recursion can be rewritten as a loop, often with an explicit stack. Recursion is clearer when the data is recursive (trees, divide-and-conquer); iteration avoids call overhead and the stack-depth limit. Factorial and linear traversal are simpler as loops in Python; tree traversal and merge sort are simpler recursively.

Naive fib(n) recomputes the same values exponentially often. Memoization (caching each result the first time it is computed) cuts it to O(n); that idea grows into dynamic programming (21.4).

Part IISearching and sorting#

7Searching#

Scope. Study guide (linear search worst case; binary search and its O(log n) cost); zyBook reports (searching and algorithm analysis).

7.1Linear search#

Linear search checks each element in turn until it finds the target or runs out of elements. It works on any list, sorted or not, and on any structure you can walk (a linked list, a file).

def linear_search(xs, target):
    for i in range(len(xs)):
        if xs[i] == target:
            return i          # found: index of first match
    return -1                 # not found

Auxiliary space is O(1). Python’s in operator and list.index on a list are linear searches.

7.2Binary search#

Binary search finds a target in a sorted array by comparing it with the middle element and discarding the half that cannot contain it. It is how you look up a word in a printed dictionary: open in the middle, decide which half, repeat.

def binary_search(xs, target):
    low, high = 0, len(xs) - 1
    while low <= high:
        mid = (low + high) // 2
        if xs[mid] < target:
            low = mid + 1         # target is in the right half
        elif xs[mid] > target:
            high = mid - 1        # target is in the left half
        else:
            return mid            # found
    return -1                     # range is empty: not present

Trace a search for 47 in [3, 9, 14, 22, 31, 47, 58, 66, 80] (indexes 0–8):

Each comparison halves the remaining range, so a range of n elements empties after about log₂n halvings. The worst case is ⌊log₂n⌋ + 1 comparisons: 10 for 1,000 elements, 20 for a million. Binary search is O(log n) time and O(1) auxiliary space iteratively (O(log n) recursively, for the stack frames).

Its preconditions make natural distractors:

• The data must be sorted. On unsorted data binary search returns wrong answers, not slow ones.
• It needs constant-time access by index. On a linked list, finding each middle costs a walk, which erases the advantage.
• If the data changes often, keeping it sorted may cost more than the searches save. Sorting first costs O(n log n), which pays off only when you search many times.

7.3Choosing a search method#

8Sorting#

Scope. Study guide (sorting algorithms compared by best, average, and worst case, stability, and in-place behavior; counting sort; quickselect); zyBook reports (selection, insertion, shell, quick, merge, radix sort; bubble sort and bucket sort as additional material).

8.1Vocabulary#

• Comparison sort: decides order only by comparing pairs of elements. General comparison sorting requires at least on the order of n log n comparisons in the worst case. This is a lower bound, not a promise that every comparison sort achieves it.
• Non-comparison sort: uses the values themselves (digits, ranges) as positions, and can run in linear time when the values are constrained. Counting, radix, and bucket sort.
• Stable: equal elements keep their original relative order. It matters when sorting records by one field after another: sort employees by name, then stably by department, and each department stays alphabetical.
• In-place: uses O(1) extra memory (O(log n) stack is usually allowed). Merge sort is the common sort that is not.
• Adaptive: runs faster on input that is already nearly sorted. Insertion sort is the standard example.

8.2Bubble sort#

Bubble sort repeatedly walks the list swapping adjacent elements that are out of order. Each pass carries the largest remaining element to the end, like a bubble rising.

def bubble_sort(xs):
    n = len(xs)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):        # last i items already in place
            if xs[j] > xs[j + 1]:
                xs[j], xs[j + 1] = xs[j + 1], xs[j]
                swapped = True
        if not swapped:                   # no swaps: already sorted
            break

O(n²) worst and average; O(n) best with the early-exit flag on sorted input. Stable and in-place. Recognize it by the comparison of xs[j] with xs[j + 1] and an inner loop that shrinks from the right.

8.3Selection sort#

Selection sort treats the list as a sorted part on the left and an unsorted part on the right. Each pass selects the smallest unsorted element and swaps it to the end of the sorted part.

def selection_sort(xs):
    for i in range(len(xs) - 1):
        smallest = i
        for j in range(i + 1, len(xs)):
            if xs[j] < xs[smallest]:
                smallest = j
        xs[i], xs[smallest] = xs[smallest], xs[i]

Trace on [29, 10, 14, 37, 13]:

i=0: min is 10      [10 | 29, 14, 37, 13]
i=1: min is 13      [10, 13 | 14, 37, 29]
i=2: min is 14      [10, 13, 14 | 37, 29]
i=3: min is 29      [10, 13, 14, 29 | 37]

Always O(n²) comparisons, even on sorted input, but at most n − 1 swaps, which helps when writes are expensive. In-place; not stable (the long-distance swap can jump an element over an equal one). Recognize it by the inner loop that only tracks an index of the minimum, with one swap after it.

8.4Insertion sort#

Insertion sort also grows a sorted part on the left, but takes the next element and inserts it into place by shifting larger sorted elements right, the way most people sort a hand of cards.

def insertion_sort(xs):
    for i in range(1, len(xs)):
        j = i
        while j > 0 and xs[j] < xs[j - 1]:
            xs[j], xs[j - 1] = xs[j - 1], xs[j]
            j -= 1

Trace on [29, 10, 14, 37, 13]:

i=1: insert 10      [10, 29 | 14, 37, 13]
i=2: insert 14      [10, 14, 29 | 37, 13]
i=3: insert 37      [10, 14, 29, 37 | 13]     no shifts
i=4: insert 13      [10, 13, 14, 29, 37]

O(n²) worst (reverse-sorted input) and average; O(n) best on sorted input, where each element needs one comparison. For a nearly sorted list with few inversions, it runs in nearly linear time, which is why hybrid sorts (including Python’s Timsort) use it for small runs. Stable and in-place. Recognize it by the inner while loop moving backward from i.

8.5Shell sort#

Shell sort generalizes insertion sort. It insertion-sorts elements that are a gap apart, then repeats with smaller gaps, finishing with a gap of 1 (ordinary insertion sort). Early passes move elements long distances cheaply, so the final pass finds the list nearly sorted, insertion sort’s best case.

def shell_sort(xs, gaps=(5, 3, 1)):
    for gap in gaps:
        for start in range(gap):
            # insertion sort on xs[start], xs[start+gap], xs[start+2*gap], ...
            for i in range(start + gap, len(xs), gap):
                j = i
                while j - gap >= 0 and xs[j] < xs[j - gap]:
                    xs[j], xs[j - gap] = xs[j - gap], xs[j]
                    j -= gap

Its running time depends on the gap sequence, so no single cost row describes it. With gaps 2^k − 1 the worst case is O(n^3/2); poor sequences degrade to O(n²). The fixed gaps (5, 3, 1) above keep the sketch short; real implementations derive the gaps from n. In-place; not stable. Recognize it by a gap variable inside an insertion-sort loop.

8.6Merge sort#

Merge sort is divide and conquer: split the list in half, sort each half recursively, then merge the two sorted halves by repeatedly taking the smaller front element.

def merge_sort(xs):
    if len(xs) <= 1:
        return xs
    mid = len(xs) // 2
    left = merge_sort(xs[:mid])
    right = merge_sort(xs[mid:])
    return merge(left, right)

def merge(left, right):
    out = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:          # <= keeps it stable
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:])                # one side may have leftovers
    out.extend(right[j:])
    return out

[38, 27, 43, 3, 9, 82, 10]
split   [38, 27, 43]           [3, 9, 82, 10]
split   [38] [27, 43]          [3, 9] [82, 10]
merge   [38] [27, 43]          [3, 9] [10, 82]
merge   [27, 38, 43]           [3, 9, 10, 82]
merge   [3, 9, 10, 27, 38, 43, 82]

The splitting makes log₂n levels; merging at each level touches all n elements. Total O(n log n) in every case, best, average, and worst. The price is O(n) extra memory for the merged lists. Stable. Recognize it by two recursive calls on halves followed by a merge loop with two indexes.

8.7Quicksort#

Quicksort is also divide and conquer, but does its work before recursing. It picks a pivot, partitions the list so everything in the low part is ≤ the pivot and everything in the high part is ≥ it, then sorts each part recursively. No merge step is needed; the parts are already in the right order relative to each other.

The zyBooks version picks the middle element as the pivot and moves two indexes toward each other, swapping pairs that are on the wrong side:

def partition(xs, low, high):
    pivot = xs[low + (high - low) // 2]       # middle element
    while True:
        while xs[low] < pivot:
            low += 1
        while pivot < xs[high]:
            high -= 1
        if low >= high:
            return high                       # last index of the low part
        xs[low], xs[high] = xs[high], xs[low]
        low += 1
        high -= 1

def quicksort(xs, low, high):
    if low >= high:
        return
    low_end = partition(xs, low, high)
    quicksort(xs, low, low_end)
    quicksort(xs, low_end + 1, high)

Many textbooks use the Lomuto partition instead (pivot is the last element; one index sweeps and swaps smaller elements to the front). The mechanics differ; the idea and costs do not.

Good pivots split the list roughly in half, giving log n levels of O(n) partitioning: O(n log n) average and best. A pivot that is always the smallest or largest element (first-element pivot on already-sorted input, for instance) splits off one element per level: O(n²) worst. Middle-element or random pivots make the worst case unlikely. In-place apart from the recursion stack, which is O(log n) deep on average and O(n) in the worst case (recursing on the smaller part and using a loop for the larger part caps the stack at O(log n)). Not stable. On random data in arrays it is often the fastest comparison sort in practice.

8.8Heapsort#

Heapsort builds a max-heap from the array, then repeatedly swaps the root (the maximum) to the end of the array and restores the heap on the remaining elements. It is O(n log n) in every case, in-place, and not stable. Full mechanics are in 17.4, after heaps.

8.9Counting sort#

Counting sort sorts integers in a known range 0 … k without comparing them. It counts how many times each value occurs, then writes values out in order according to the counts. It requires knowing the range of input values in advance, because the count array needs one slot per possible value.

def counting_sort(xs, k):                 # values in 0..k
    counts = [0] * (k + 1)
    for x in xs:                          # O(n)
        counts[x] += 1
    out = []
    for value in range(k + 1):            # O(k)
        out.extend([value] * counts[value])
    return out

counting_sort([3, 1, 4, 1, 5, 2, 1], 5)    # [1, 1, 1, 2, 3, 4, 5]

Cost O(n + k) time, where n is the number of elements and k the size of the value range: one loop over the input, one over the counts, and sequential loops add. Extra space is also O(n + k): k + 1 counters plus the n-item output list. It is practical when k is not much larger than n. Sorting 1,000 exam scores between 0 and 100 is ideal; sorting 10 phone numbers by a count array of ten billion slots is absurd. The version that sorts whole records uses prefix sums of the counts to place each record and is stable.

8.10Radix sort#

Radix sort sorts integers digit by digit, from the least significant digit to the most, distributing elements into ten buckets (one per digit value) on each pass and collecting them in bucket order. Because each pass is stable, ties on the current digit keep the order set by the earlier passes.

input:            [170, 45, 75, 90, 802, 24, 2, 66]
by ones digit:    [170, 90, 802, 2, 24, 45, 75, 66]
by tens digit:    [802, 2, 24, 45, 66, 170, 75, 90]
by hundreds:      [2, 24, 45, 66, 75, 90, 170, 802]

With d digits, the cost is O(d · n), linear when the digit count is bounded. Extra space O(n) for the buckets. Negative numbers need separate handling (sort negatives and non-negatives apart, reverse the negatives). Recognize it by a loop over digit positions using // 10 ** p % 10 or similar.

8.11Bucket sort#

Bucket sort divides the value range into k buckets, distributes elements into them, sorts each bucket (usually with insertion sort), and concatenates. For values spread evenly across the range, each bucket stays small and the total is O(n + k) on average. If everything lands in one bucket it degrades to the inner sort’s O(n²).

8.12Quickselect#

Quickselect finds the k-th smallest element (the median, say) without sorting everything. It borrows quicksort’s partition: after partitioning, the target is in one part, so it recurses into that part only and ignores the other. Like binary search (7.2), it discards candidates that cannot contain the answer, but its partitions need not be equal halves.

def quickselect(xs, low, high, k):      # k is a 0-based index
    if low >= high:
        return xs[low]
    low_end = partition(xs, low, high)  # the zyBooks partition above
    if k <= low_end:
        return quickselect(xs, low, low_end, k)
    return quickselect(xs, low_end + 1, high, k)

The single difference from quicksort is that quickselect does not recursively sort both partitions. When pivots split roughly in half, the work sums to n + n/2 + n/4 + … < 2n, so the average is O(n); bad pivots give an O(n²) worst case, like quicksort.

8.13Comparing sorts and recognizing them#

All costs are O( ); * when implemented to place records in input order.

Selection rules worth carrying into the exam:

• Nearly sorted data: insertion sort.
• Guaranteed O(n log n) and stability: merge sort.
• Guaranteed O(n log n) with O(1) extra memory: heapsort.
• Often fastest in practice on random data in arrays: quicksort.
• Small integer range: counting sort; fixed-width integers or strings: radix sort.
• One order statistic (median, k-th smallest): quickselect, not a full sort.

And the code-shape cues: adjacent swaps (bubble); find-minimum-then-swap (selection); backward shifting while (insertion); a gap (shell); two recursive calls then a merge (merge); a pivot and two converging indexes (quick); a count array indexed by value (counting); digit extraction with // 10 and % 10 (radix).

Part IIILinear structures#

9Lists: arrays and linked lists#

Scope. Catalog (lists); study guide (arrays versus linked structures; removing the head; positional lists; circular lists); zyBook (inferred: singly and doubly linked lists, traversal, dummy nodes, array-based lists).

9.1The list ADT#

A list is an ordered collection: items have positions, and order matters. The ADT’s usual operations:

Two structures implement it, and their costs mirror each other. An array is a row of numbered lockers: you can open locker 500 directly, but inserting a new locker in the middle means moving everyone after it. A linked list is a scavenger hunt: each clue points to the next, so adding a clue in the middle means rewriting one pointer, but reaching the 500th clue means following 499 pointers.

9.2Array-based lists#

An array-based list stores items in a contiguous array with spare capacity, tracking how many slots are used. Python’s list is one. This sketch assumes a positive initial capacity and valid indexes: 0 through length for insertion, and 0 through length − 1 for removal.

class ArrayList:
    def __init__(self, capacity=4):
        self._data = [None] * capacity
        self._length = 0

    def append(self, x):
        if self._length == len(self._data):
            self._resize(2 * len(self._data))   # full: double capacity
        self._data[self._length] = x
        self._length += 1

    def insert(self, i, x):                     # shift right to open a gap
        if self._length == len(self._data):
            self._resize(2 * len(self._data))
        for j in range(self._length, i, -1):
            self._data[j] = self._data[j - 1]
        self._data[i] = x
        self._length += 1

    def remove_at(self, i):                     # shift left to close the gap
        x = self._data[i]
        for j in range(i, self._length - 1):
            self._data[j] = self._data[j + 1]
        self._length -= 1
        self._data[self._length] = None         # release the unused reference
        return x

    def _resize(self, capacity):
        new = [None] * capacity
        for j in range(self._length):
            new[j] = self._data[j]
        self._data = new

• Access by index: O(1). The address of item i is computed directly.
• Append: amortized O(1). Resizing copies everything, O(n), but doubling makes it rare enough to average out (5.8).
• Insert or remove at index i: O(n − i) shifts, so O(n) at the front and O(1) at the end.
• Search: O(n) unsorted; O(log n) with binary search if kept sorted.

9.3Singly linked lists#

A singly linked list puts the references of 3.3 and the Node class of 4.1 to work: it is a chain of nodes, each holding data and a reference to the next node. The list object holds a head (first node) and usually a tail (last node); the last node’s next is None.

head                                  tail
 |                                     |
[12 | •]-->[45 | •]-->[7 | •]-->[30 | None]

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, node):                 # O(1) with a tail reference
        if self.head is None:
            self.head = self.tail = node
        else:
            self.tail.next = node
            self.tail = node

    def prepend(self, node):                # O(1)
        if self.head is None:
            self.head = self.tail = node
        else:
            node.next = self.head
            self.head = node

    def insert_after(self, cur, node):      # O(1) once you hold cur
        if self.head is None:
            self.head = self.tail = node
        elif cur is self.tail:
            self.tail.next = node
            self.tail = node
        else:
            node.next = cur.next            # order matters: link forward first
            cur.next = node

    def remove_after(self, cur):            # cur None means remove the head
        if cur is None and self.head is not None:
            self.head = self.head.next
            if self.head is None:
                self.tail = None
        elif cur is not None and cur.next is not None:
            cur.next = cur.next.next
            if cur.next is None:
                self.tail = cur

    def search(self, key):                  # O(n)
        node = self.head
        while node is not None:
            if node.data == key:
                return node
            node = node.next
        return None

Three details carry most of the exam questions:

• Removing the first node is head = head.next: the list’s head reference now points to the second node, so the old first node is no longer in the list. If no other variable refers to it, it is unreachable and Python reclaims it; a caller still holding a reference keeps it alive, outside the list. Nothing shifts; the nodes are connected by references, not positions.
• Insertion order of the two assignments matters. In insert_after, setting cur.next = node first would lose the reference to the rest of the list.
• A singly linked list removes after a node. Removing a node in the middle or at the tail means changing its predecessor’s next, and finding the predecessor costs a walk from the head. The head is the exception: it has no predecessor, so the list’s own head reference changes instead (the cur is None branch). That predecessor walk is the gap doubly linked lists fill.

9.4Doubly linked lists#

A doubly linked list gives each node a prev reference as well as next. It costs an extra reference per node and buys O(1) removal of any node you hold, plus backward traversal.

def insert_after(self, cur, node):         # doubly linked version
    if self.head is None:
        self.head = self.tail = node
    elif cur is self.tail:
        self.tail.next = node
        node.prev = self.tail
        self.tail = node
    else:
        succ = cur.next
        node.next = succ
        node.prev = cur
        cur.next = node
        succ.prev = node

def remove(self, cur):                     # O(1): no predecessor search
    succ, pred = cur.next, cur.prev
    if succ is not None:
        succ.prev = pred
    if pred is not None:
        pred.next = succ
    if cur is self.head:
        self.head = succ
    if cur is self.tail:
        self.tail = pred

Inserting a new node between nodes A and B always takes exactly four reference updates: new.prev = A, new.next = B, A.next = new, B.prev = new. Removing a node between them takes two: A.next = B and B.prev = A.

9.5Traversal#

Traversal visits every node, starting at the head and following next until None. Reverse traversal starts at the tail and follows prev, which only a doubly linked list supports directly. Both are O(n).

node = lst.head
while node is not None:
    print(node.data)
    node = node.next             # forgetting this line loops forever

Recursion fits too: a list is a node followed by a shorter list. Printing before the recursive call prints in order; printing after it prints in reverse, even for a singly linked list, because the output happens as the calls return.

def print_reverse(node):
    if node is None:
        return
    print_reverse(node.next)
    print(node.data)

9.6Dummy (sentinel) nodes#

A dummy node (or sentinel, or header node) is a permanent node at the front, and sometimes the back, that holds no data. The list is never truly empty, so the special cases for an empty list or for inserting before the head disappear: every real node has a predecessor. Python’s own OrderedDict uses a sentinel for this reason. The cost is one extra node; the benefit is fewer branches, and fewer branches means fewer bugs.

9.7Circular linked lists#

In a circular linked list, the last node’s next points back to the first node instead of None. There is no end; traversal stops when it returns to its starting node.

node = start
while True:
    visit(node)
    node = node.next
    if node is start:
        break

Circular lists suit anything that cycles through items continuously: round-robin scheduling (give each process a time slice, then move to the next, forever), turn-taking in games, and circular buffers. A single reference to the tail gives O(1) access to both the tail and the head (tail.next).

9.8Positional lists#

An index identifies a place by counting, and counting costs O(n) in a linked list. A positional list ADT instead hands out positions: stable markers for places in the list, like a bookmark. Given a position, you can insert before or after it, replace its element, or delete it, all in O(1), and other positions stay valid when the list changes around them.

It is usually implemented as a doubly linked list (often with header and trailer sentinels), with each position wrapping a node. Insertion needs only pointer updates, the same four as in 9.4. A text editor’s cursor is the everyday example: typing inserts at the cursor without renumbering anything.

9.9Arrays versus linked lists#

The rule of thumb: arrays when you index and append; linked lists when you insert and remove in the middle at places you already hold. Arrays also tend to run faster on real hardware than their Big-O suggests, because neighbors in memory load into cache together.

9.10Sorting linked lists#

Algorithms that jump by index (shell sort, heapsort, quicksort with a middle pivot) suit arrays, not linked lists. Insertion sort adapts naturally to a doubly linked list by walking backward through prev, or to a singly linked list by searching forward from the head for each insertion point; both stay O(n²). Merge sort is the natural O(n log n) choice for linked lists: splitting and merging only relink nodes, so it needs no extra array.

10Stacks#

Scope. Catalog (stacks); study guide (LIFO, push, pop, peek, dynamic expansion of unbounded stacks); zyBook (inferred: stack ADT, linked and array-based stacks).

10.1The stack ADT#

Stacks and queues restrict which end of a list you can use. Choosing the right end and representation makes their basic operations O(1); resizing an array-backed structure makes insertion amortized O(1). A stack allows insertion and removal only at one end, the top: last in, first out (LIFO). A stack of plates is the picture: you add to the top and take from the top.

Popping or peeking an empty stack is an error (an exception in Python; “stack underflow” in older terminology). Trace this sequence and check that the last line prints 8:

push(5); push(3); pop(); push(8); push(1); pop()
# stack (bottom -> top):  [5] [5,3] [5] [5,8] [5,8,1] [5,8]
print(peek())   # 8

10.2Linked and array-based stacks#

A linked stack uses the head of a singly linked list as the top: push is prepend, pop is remove-the-head (head = head.next). Both are O(1), and the stack grows one node at a time with no capacity limit.

An array-based stack uses the end of an array as the top, because adding and removing at the end requires no shifting. In Python this is just a list:

stack = []
stack.append(5)      # push
stack.append(3)
stack[-1]            # peek -> 3
stack.pop()          # pop  -> 3

Using the front of an array as the top would make every push and pop shift the whole array: O(n) instead of O(1). Same ADT, wrong end, different cost.

10.3Bounded stacks and dynamic expansion#

A bounded stack has a fixed maximum size; pushing onto a full one fails (“stack overflow”). An unbounded stack accepts pushes until memory runs out. An array-based unbounded stack expands dynamically: when its array fills, it allocates a larger one (typically double) and copies the items over.

The reason to expand dynamically is to support continuous addition of elements without a predefined limit. Doubling, rather than growing by one slot, keeps push amortized O(1) (5.8), and growing only when needed avoids reserving memory that may never be used.

10.4Applications#

Stacks appear wherever the most recent unfinished thing must be dealt with first:

• Function calls: the call stack holds a frame per active call (6.2).
• Undo: each edit is pushed; undo pops the latest. Browser back buttons work the same way.
• Balanced brackets: push each opener; each closer must match the popped opener.
• Expression evaluation: postfix (reverse Polish) expressions evaluate with one stack; infix-to-postfix conversion uses an operator stack.
• Backtracking: depth-first search (19.2) and maze solving push choices and pop to retreat.

def balanced(text):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in text:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack                # leftovers mean unclosed openers

def eval_postfix(tokens):           # "3 4 + 2 *" -> (3 + 4) * 2 = 14
    stack = []
    for t in tokens.split():
        if t in ("+", "-", "*", "/"):
            right = stack.pop()     # popped in reverse order
            left = stack.pop()
            if t == "+":
                stack.append(left + right)
            elif t == "-":
                stack.append(left - right)
            elif t == "*":
                stack.append(left * right)
            else:
                stack.append(left / right)
        else:
            stack.append(float(t))
    return stack.pop()

11Queues and deques#

Scope. Catalog (queues); study guide (FIFO, enqueue and dequeue, computing the back of an array queue, deques and their operations); zyBook (inferred: linked and array-based queues, deque ADT).

11.1The queue ADT#

A queue inserts at the back and removes from the front: first in, first out (FIFO). A checkout line is the picture.

enqueue(5); enqueue(3); dequeue(); enqueue(8); enqueue(1); dequeue()
# queue (front -> back):  [5] [5,3] [3] [3,8] [3,8,1] [8,1]
print(peek())   # 8

Compare with the identical stack sequence in 10.1, which also ended with 8 on top, but holding [5, 8]: the operations match, the surviving items differ. A question of this kind gives one sequence and asks what remains. As with a stack, dequeuing or peeking an empty queue is an error.

11.2Linked queues#

A singly linked list with head and tail references implements a queue directly: enqueue appends at the tail, dequeue removes the head. Both are O(1). Reversing the roles (enqueue at head, dequeue at tail) would make dequeue O(n) in a singly linked list, because removing the tail needs its predecessor.

11.3Array-based (circular) queues#

A naive array queue that dequeues from index 0 shifts every element: O(n). The fix is a circular array: keep a front index and a length, and let indexes wrap around the end of the array with modulo.

class ArrayQueue:
    def __init__(self, capacity=8):
        self._data = [None] * capacity
        self._front = 0
        self._length = 0

    def enqueue(self, x):
        if self._length == len(self._data):
            self._resize(2 * len(self._data))
        back = (self._front + self._length) % len(self._data)
        self._data[back] = x
        self._length += 1

    def dequeue(self):
        if self._length == 0:
            raise IndexError("dequeue from empty queue")
        x = self._data[self._front]
        self._data[self._front] = None
        self._front = (self._front + 1) % len(self._data)
        self._length -= 1
        return x

    def _resize(self, capacity):        # unwrap into a new array
        old = self._data
        self._data = [old[(self._front + k) % len(old)] for k in range(self._length)]
        self._data += [None] * (capacity - self._length)
        self._front = 0

The arithmetic to know cold:

• The back item sits at (front + length − 1) % capacity.
• The next free slot (where enqueue writes) is (front + length) % capacity.

Example: capacity 6, front 4, length 3. The items occupy indexes 4, 5, and 0; the back item is at (4 + 3 − 1) % 6 = 0, and the next enqueue writes index (4 + 3) % 6 = 1. Without wrap-around (front 0, length 4 in an array holding [18, 6, 31, 9, …]), the back is simply index 3, holding 9.

In Python, use collections.deque for queues: append to enqueue, popleft to dequeue, both O(1). Avoid list.pop(0), which is O(n).

11.4The deque ADT#

A deque (“deck”, short for double-ended queue) allows insertion and removal at both ends. It generalizes both earlier ADTs: use one end only and it is a stack; insert at one end and remove at the other and it is a queue.

All are O(1) with a doubly linked list or a circular array. A singly linked list cannot do remove_last in O(1).

11.5Applications#

• Scheduling and buffering: print jobs, network packets, keystrokes, and requests to a server are handled in arrival order.
• Breadth-first search (19.1) explores a graph level by level using a queue.
• Simulation: customers in a line, cars at a light.
• Deques: undo histories with a size cap (add at one end, drop the oldest from the other), sliding-window algorithms, and work-stealing schedulers.

When arrival order is not the right rule (an emergency room treats the most urgent case first), the ADT you want is a priority queue, covered with heaps in chapter 17.

Part IVHashing, maps, and sets#

12Hash tables#

Scope. Catalog (hash tables); study guide (maps keys to values; storing and retrieving by key; O(1) average insertion and its assumptions; collisions; chaining and open addressing); zyBook (inferred: probing variants, resizing, hash functions, and direct hashing).

12.1The map ADT#

A map (also dictionary or associative array) associates keys with values. Each key appears at most once; looking up a key returns its value. A coat check is the picture: you hand over a coat (value), receive a ticket (key), and later the ticket alone gets the coat back.

inventory = {}
inventory["widget"] = 40        # stores 40 under the key "widget"
inventory["widget"]             # retrieves 40
inventory["widget"] = 35        # same key: the value is replaced, not duplicated

A map can be implemented with a list of pairs (O(n) per lookup), a balanced search tree (O(log n), keys kept in order), or a hash table (O(1) on average, no sorted order). The hash table is the usual choice and the one the course emphasizes. Where binary search (7.2) finds a key by comparing, a hash table computes where the key should be.

12.2How a hash table works#

A hash table stores items in an array of buckets. A hash function turns a key into an integer, and that integer modulo the table size picks the bucket. To find a key later, compute the same function and look in one bucket instead of scanning everything.

table size N = 10, hash function h(key) = key % 10

insert 47  ->  47 % 10 = 7  ->  bucket 7
insert 82  ->  82 % 10 = 2  ->  bucket 2
insert 15  ->  15 % 10 = 5  ->  bucket 5
search 82  ->  look only in bucket 2

It is a library where the call number is computed from the title: you walk straight to the shelf instead of searching every aisle. Lookup cost no longer depends on how many books there are, as long as shelves don’t overflow.

A collision occurs when two different keys map to the same bucket: 47 and 67 both land in bucket 7 above. Collisions are unavoidable once there are more possible keys than buckets (the pigeonhole principle), so every hash table needs a collision resolution strategy. The two families are chaining and open addressing.

12.3Chaining#

In chaining (separate chaining), each bucket holds a list of all the items that hash there. Insert appends to the bucket’s list if the key is not already present; search and remove scan only that one list.

class ChainingMap:
    def __init__(self, size=11):
        self._buckets = [[] for _ in range(size)]

    def _bucket(self, key):
        return self._buckets[hash(key) % len(self._buckets)]

    def put(self, key, value):
        bucket = self._bucket(key)
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)     # existing key: replace value
                return
        bucket.append((key, value))

    def get(self, key):
        for k, v in self._bucket(key):
            if k == key:
                return v
        raise KeyError(key)

    def remove(self, key):
        bucket = self._bucket(key)
        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]
                return
        raise KeyError(key)

With n items in N buckets, the average chain has n/N items, so operations cost O(1 + n/N). Chaining degrades gracefully: the table works even when it holds more items than buckets, just more slowly.

12.4Open addressing: linear probing#

Open addressing stores every item directly in the array; on a collision it probes other buckets in a fixed sequence until it finds a free one. Linear probing tries the next bucket, then the next, wrapping around: (h(key) + i) % N for i = 0, 1, 2, …

N = 10, h(key) = key % 10
insert 47 -> bucket 7
insert 67 -> 7 is taken -> bucket 8
insert 57 -> 7, 8 taken -> bucket 9
insert 39 -> 9 taken -> wraps to bucket 0

Search follows the same probe sequence and stops at the key or at an empty bucket. Removal creates a subtlety: emptying a bucket outright would break probe chains (after removing 67, a search for 57 would stop at bucket 8 and wrongly report “not found”). So buckets have three states:

• Empty-since-start: never used. A search may stop here.
• Empty-after-removal (a tombstone): once held an item. A search must continue past it; an insert may reuse it.
• Occupied.

Linear probing’s weakness is primary clustering: occupied buckets form runs, any key hashing into a run extends it, and long runs make probes long.

12.5Quadratic probing#

Quadratic probing spreads the probes out by stepping quadratically: (h(key) + c1·i + c2·i²) % N. With c₁ = 0 and c₂ = 1, the probes from bucket h are h, h + 1, h + 4, h + 9, … This breaks up primary clusters, but keys with the same initial bucket still follow the same sequence (secondary clustering), and poorly chosen constants and table sizes can miss empty buckets.

12.6Double hashing#

Double hashing uses a second hash function to choose the step size: (h1(key) + i · h2(key)) % N. Keys that collide at the first bucket often have different step sizes, so their probe sequences diverge and reduce clustering. h₂ must never return 0, or the probe never moves. Nonzero is not enough: the step must also share no factor with N, or the probe cycles through only some buckets. With N = 10 and step 5, the probes from bucket 3 visit 3, 8, 3, 8, … forever. Making N prime makes every step from 1 to N − 1 safe; a common choice is then h2(key) = R − key % R for a prime R < N, which gives steps from 1 to R.

12.7Load factor and resizing#

The load factor α = n/N measures how full the table is. It governs performance:

• With chaining, α is the average chain length; α may exceed 1.
• With open addressing, α must stay below 1 (every item needs its own bucket), and probe lengths grow sharply as α approaches 1. With well-spread keys, linear probing needs about ½(1 + 1/(1 − α)²) probes for an unsuccessful search: 2.5 at α = 0.5, about 50 at α = 0.9.

When α passes a threshold (often 0.5 to 0.75), the table resizes: allocate a larger array, typically the next prime at least double the size, and rehash every item into it, since each bucket index depends on N. A resize costs O(n), but like dynamic-array growth it is rare enough to amortize to O(1) per insertion.

This is why the course states hash table insertion as O(1) on average, assuming an effective hash function and a reasonably controlled load factor. If either assumption fails (a bad function piles keys into a few buckets, or the table is allowed to fill), collisions dominate and the worst case is O(n): every key in one chain, or one long probe run.

12.8Hash functions#

A good hash function is deterministic (the same key always gives the same value), fast, and spreads keys uniformly across buckets, including keys that are similar to each other. A perfect hash function maps a known set of keys with no collisions at all.

Summing a string’s character codes is a classic bad hash: anagrams (“stop”, “pots”, “tops”) collide, and short strings cluster in a narrow range. Position-weighted schemes like the multiplicative hash fix both.

In Python, hash(x) provides the integer; the dict and set types reduce it to a bucket internally. A user-defined class used as a key needs consistent __hash__ and __eq__: objects that compare equal must hash equally. A key’s hash and equality must stay stable while it is in the table. Python makes lists, dictionaries, and sets unhashable; a custom mutable object can be hashable, but changing fields used by its hash or equality can make the entry unreachable.

12.9Costs at a glance#

Hashing gives fast exact-key lookup; sorted order is its blind spot. Hashing scatters keys on purpose, so a hash table promises no sorted order and cannot answer “what is the next key after this one?” cheaply. Python’s dict does remember insertion order (3.6), but insertion order is not sorted order. When sorted order matters, use a balanced BST (chapter 16).

12.10Cryptographic and password hashing#

A hash table’s hash function is fast and collision-tolerant. Security uses a different kind: a cryptographic hash function (SHA-256, for instance) is designed so that it is infeasible to find an input producing a given output, or two inputs producing the same output. These serve as fingerprints for detecting tampering with files and messages. This distinction is supplemental; the WGU catalog names hash tables, not cryptographic hashes.

Password hashing stores a derived value instead of the password itself. Good password hashing adds a random salt per user and is deliberately slow (bcrypt, scrypt, Argon2), the reverse of what a hash table wants, so that guessing passwords by brute force is expensive.

13Sets and bags#

Scope. Catalog (bags); zyBook reports (sets; inferred: set ADT built on a BST).

13.1The set ADT#

A set is a collection of distinct items with no order. Adding an item already present does nothing. Its operations follow mathematical sets:

The defining use is fast membership and de-duplication: len(set(emails)) counts distinct addresses.

13.2Implementing sets#

A set is a map with keys and no values, which is why both share the same implementations. Python’s frozenset is an immutable, hashable set that can itself be a dictionary key or a member of another set.

13.3Bags (multisets)#

A bag (multiset) is an unordered collection that allows duplicates and remembers how many of each item it holds. Think of a bag of marbles: you can ask how many red marbles there are, but not which marble went in first.

Typical operations are add, remove (one occurrence), count of an item, size, and contains. The implementation in 4.6 stores a dictionary of counts; collections.Counter is Python’s built-in bag. Bags are the natural structure for word frequencies, inventory counts, and votes. Because a bag promises no order, an implementation is free to choose whatever layout makes its operations cheapest, which is the ADT idea at its plainest.

Part VTrees#

14Trees and binary trees#

Scope. Catalog (trees); OA reports (reading tree structures); zyBook (inferred: binary trees, applications, traversals, tries).

14.1Terminology#

A tree is a hierarchy of nodes connected by edges, with one root at the top and no cycles. Every node except the root has exactly one parent. A family tree drawn downward, or a file system’s folders, are the pictures.

            8              depth 0  (root)
          /   \
         3     10          depth 1
        / \      \
       1   6      14       depth 2
          / \    /
         4   7  13         depth 3  (height of the tree = 3)

14.2Binary trees#

In a binary tree each node has at most two children, called left and right. A node object is the linked-list node of 9.3 with two references instead of one (and sometimes a parent reference). The tree code in chapters 14 and 15 uses this class:

class TreeNode:
    def __init__(self, key):
        self.key = key
        self.left = None           # smaller keys, in a BST
        self.right = None          # larger keys, in a BST

Counting facts that answer many questions:

• A perfect tree of height h has 2^h+1 − 1 nodes, with 2^h of them leaves.
• The smallest possible height for n nodes is ⌊log₂n⌋; the largest is n − 1 (a chain).
• A complete tree can live in an array with no gaps, which is what heaps exploit (17.2).

The tree above is not full (10 and 14 have one child each), not complete (10 has no left child while level 2 continues to its right), and not perfect.

14.3Applications#

• File systems: directories contain files and subdirectories.
• Search: binary search trees and their balanced forms keep keys ordered with O(log n) operations.
• Priority: heaps.
• Expression trees: operators in internal nodes, operands in leaves; postorder traversal evaluates them.
• Space partitioning: binary space partitioning trees divide a region repeatedly so a game or renderer can skip whole regions (everything behind a wall) at once.
• Documents: HTML and XML are trees of nested elements.
• Compression: Huffman trees (chapter 20).

14.4Traversals#

A traversal visits every node once. The three depth-first orders differ only in when the node itself is visited relative to its subtrees:

def preorder(node):             # node, left, right
    if node is None: return
    visit(node)
    preorder(node.left)
    preorder(node.right)

def inorder(node):              # left, node, right
    if node is None: return
    inorder(node.left)
    visit(node)
    inorder(node.right)

def postorder(node):            # left, right, node
    if node is None: return
    postorder(node.left)
    postorder(node.right)
    visit(node)

Level-order traversal visits depth 0, then depth 1, and so on, left to right, using a queue (chapter 11): dequeue a node, visit it, enqueue its children. Breadth-first search on graphs (19.1) is the same loop with a visited set added.

Two shortcuts: the root is always first in preorder and last in postorder; and if the tree is a BST, inorder is sorted. Every traversal is O(n).

14.5Tries#

A trie (prefix tree) stores strings by spelling them out along paths: each edge is a character, each node represents a prefix, and a marker flags nodes where a complete word ends.

words: car, cat, cart, dog

(root)
 ├─ c ─ a ─ r*─ t*
 │       └─ t*
 └─ d ─ o ─ g*            * = end of a word

class TrieNode:
    def __init__(self):
        self.children = {}        # char -> TrieNode
        self.is_word = False

def insert(root, word):
    node = root
    for ch in word:
        node = node.children.setdefault(ch, TrieNode())
    node.is_word = True

def contains(root, word):
    node = root
    for ch in word:
        if ch not in node.children:
            return False
        node = node.children[ch]
    return node.is_word

Insert and search cost O(m) for a word of length m, regardless of how many words are stored. Tries answer prefix questions (“all words starting with ca”) directly, which is why they power autocomplete and spell checkers.

15Binary search trees#

Scope. Catalog (trees); study guide (BSTs among the core structures); zyBook (inferred: BST search, insert, remove, traversal, height and insertion order, recursion, parent pointers).

15.1The BST property#

A binary tree (14.2) fixes only the shape: who is whose child. A binary search tree adds an ordering rule on top of the shape. It is a binary tree ordered so that for every node, all keys in its left subtree are smaller and all keys in its right subtree are larger. The examples assume distinct keys; a structure that allows duplicates must define a consistent duplicate policy. The tree in 14.1 is a BST. The property must hold for whole subtrees, not just immediate children: putting 9 as the right child of 6 would satisfy 6 < 9, yet break the tree, because 9 sits in 8’s left subtree.

The payoff is that every comparison discards a subtree, like binary search on an array, but with cheap insertion and removal.

15.2Search#

def search(root, key):
    node = root
    while node is not None:
        if key == node.key:
            return node
        node = node.left if key < node.key else node.right
    return None

Searching for 7 in the 14.1 tree visits 8 → 3 → 6 → 7: four comparisons. The cost is proportional to the depth reached, at most the tree height h: O(h). The minimum is the leftmost node and the maximum the rightmost, also O(h).

15.3Insertion#

Insertion searches for the key; where the search falls off the tree, the new node becomes a leaf. A key that is already present is left alone, which keeps the keys distinct.

def insert(root, key):            # returns the (possibly new) root
    if root is None:
        return TreeNode(key)      # TreeNode from 14.2
    if key < root.key:
        root.left = insert(root.left, key)
    elif key > root.key:
        root.right = insert(root.right, key)
    return root                   # equal key: already present, no change

Inserting 5 into the 14.1 tree goes 8 → left to 3 → right to 6 → left to 4 → right of 4 is empty, so 5 becomes 4’s right child. O(h).

15.4Removal#

Removal has three cases, decided by how many children the doomed node has:

1. Leaf: set the parent’s reference to it to None.
2. One child: the parent adopts that child in the removed node’s place.
3. Two children: find the node’s in-order successor, the leftmost node of its right subtree (the smallest key larger than it). Copy the successor’s key into the node, then remove the successor from the right subtree. The successor has no left child, so its removal is case 1 or 2.

Removing 3 from the 14.1 tree: 3 has two children. Its successor is 4 (go right to 6, then left as far as possible). Copy 4 into the node, then remove the leaf 4. The tree stays a BST: 4 is larger than everything left of it (1) and smaller than everything right of it (6, 7). Using the in-order predecessor (rightmost of the left subtree) works equally well. Removal is O(h).

15.5Height and insertion order#

Every BST operation is O(h), so everything depends on the height, and the height depends on the order of insertion:

insert 4, 2, 6, 1, 3, 5, 7          insert 1, 2, 3, 4, 5, 6, 7

        4                           1
      /   \                          \
     2     6                          2
    / \   / \                          \
   1   3 5   7                          3 ...  (a chain)

height 2 = log2(7) rounded down     height 6 = n - 1

Same keys, same rules: one tree answers searches in three comparisons, the other in up to seven. Random insertion orders give an expected height of O(log n), but sorted or nearly sorted input, which is common in practice, produces a chain and O(n) operations. Balanced trees (chapter 16) exist to rule this out.

15.6Ordered operations, recursion, and parent pointers#

Because a BST keeps keys ordered, it supports queries a hash table cannot: in-order traversal yields sorted output in O(n); min and max cost O(h); and range queries (“all keys between 20 and 40”) visit only the relevant subtrees.

BST algorithms are naturally recursive (a subtree is itself a BST). Recursive search and insert mirror the iterative ones; computing the height recursively is one line:

def height(node):
    if node is None:
        return -1                     # so a single leaf has height 0
    return 1 + max(height(node.left), height(node.right))

Some implementations store a parent reference in each node. It costs memory and must be updated on every insert, remove, and rotation, but it lets code walk upward: finding a node’s successor without a stack, and rebalancing after an insertion in AVL and red-black trees.

16Balanced trees#

Scope. Catalog (trees); zyBook reports (balanced trees; B-trees); zyBook (inferred: AVL and red-black rotations, insertion and removal; 2-3-4 trees). The study-guide summaries and exam reports cited here do not name the mechanics, so know the ideas and the guarantees before the step-by-step cases.

16.1Why balance#

A BST’s O(h) costs are only as good as its height. A balanced tree adds rules that keep its height O(log n) no matter the insertion order, and restores those rules after each insertion or removal, usually with rotations. The result is guaranteed O(log n) search, insert, and remove.

16.2Rotations#

A rotation is a local restructuring that changes the shape of a subtree while preserving the BST order. A right rotation at node X lifts its left child L into X’s place:

        X                    L
       / \                  / \
      L   C      ==>       A   X
     / \                      / \
    A   B                    B   C

right rotation at X:  X.left = L.right (B);  L.right = X;  L replaces X

In-order is A, L, B, X, C on both sides, so the BST property survives, but the left side got shorter and the right side longer. A left rotation is the mirror image. Each rotation changes a constant number of references: O(1).

16.3AVL trees#

An AVL tree is a BST in which, for every node, the heights of the left and right subtrees differ by at most 1. The balance factor is left height minus right height and must be −1, 0, or +1. This keeps the height under about 1.44 log₂n.

Insertion is ordinary BST insertion followed by a walk back up toward the root, updating heights. At the first node whose balance factor reaches ±2, one of four cases applies, named for the path from that node to the inserted key:

insert 10, 20, 30: right-right case at 10

  10                                  20
    \         left rotation          /  \
     20       at 10        ==>     10    30
       \
        30

insert 30, 10, 20: left-right case at 30

      30                 30                   20
     /     left rotation /    right rotation  /  \
   10      at 10   ==>  20    at 30   ==>   10    30
     \                 /
      20              10

One single or double rotation fixes an insertion. Removal is BST removal followed by the same walk upward, but may need rotations at several ancestors. All operations are O(log n).

16.4Red-black trees#

A red-black tree balances more loosely, using node colors:

1. Every node is red or black.
2. The root is black.
3. A red node’s children are black (no two reds in a row).
4. Null children count as black leaves.
5. Every path from a node down to its null leaves passes through the same number of black nodes.

Rules 3 and 5 together mean the longest root-to-leaf path is at most twice the shortest, so the height is at most 2 log₂(n + 1). New nodes are inserted red, which never breaks rule 5; if it breaks rule 3, recoloring and at most two rotations repair it. Removal has more cases but the same O(log n) bound.

16.5B-trees and 2-3-4 trees#

A B-tree lets each node hold several sorted keys. An internal node has one more child than it has keys; a leaf has no children. In a B-tree of order K, each node holds up to K − 1 keys and K children, every non-root node is at least about half full, and all leaves are at the same depth, so the tree is perfectly balanced by construction.

A 2-3-4 tree is a B-tree of order 4: nodes hold one, two, or three keys (2-nodes, 3-nodes, 4-nodes). Search compares against a node’s keys to choose the child between them. Insertion always adds a key to a leaf; the zyBooks version splits every full node it meets on the way down, moving the middle key up into the parent, so there is always room. Splitting the root is the only way the tree grows taller, which is why the leaves stay level. Removal uses rotation (borrowing a key through the parent from a sibling) and fusion (merging two sparse siblings with a parent key) to keep nodes from becoming empty.

insert 50 into a tree whose root is the full node [20 | 40 | 60]

split the root on the way down:      then insert into the leaf:
        [40]                                 [40]
       /    \                               /    \
    [20]    [60]                        [20]    [50 | 60]

Why wide nodes? Databases and file systems store trees on disk, where reading one block costs as much as thousands of comparisons in memory. A B-tree with hundreds of keys per node holds millions of records in three or four levels, so a lookup reads three or four blocks. Search, insert, and remove are O(log n).

17Heaps and priority queues#

Scope. Study guide (priority queue ADT and its operations; heaps among the core structures; heapsort among the compared sorts); zyBook reports (heaps); zyBook (inferred: array-based heaps, treaps).

17.1The heap property#

A BST keeps every key in order, and chapter 16 showed the machinery it takes to keep that order fast. Many problems need less: only the largest (or smallest) item, over and over. A heap keeps just enough order for that, and uses the complete shape of 14.2 so it never needs rebalancing. A max-heap is a complete binary tree in which every node’s key is greater than or equal to its children’s keys, so the maximum is always at the root. A min-heap reverses the inequality and keeps the minimum at the root.

A heap is much weaker than a BST: it orders each parent against its children, not left against right. That is exactly enough to find the maximum in O(1) and to remove it in O(log n), and not enough to search for an arbitrary key faster than O(n).

17.2Heaps in arrays#

Because a heap is complete, its nodes fill an array level by level with no gaps, and parent-child links become arithmetic. With 0-based indexes:

index:   0   1   2   3   4   5
array: [90, 70, 80, 30, 60, 50]

            90                  children of index 1 (70): 3 and 4
          /    \                parent of index 5 (50): (5 - 1) // 2 = 2
        70      80
       /  \    /
      30  60  50

Some textbooks use 1-based arrays, where the children are 2i and 2i + 1 and the parent is i // 2. Check which convention a question uses before computing.

17.3Insert and remove#

Insert places the new key in the next free slot (the end of the array), then percolates up: while it is larger than its parent, swap them.

Remove takes the root, moves the last element into the root’s place, then percolates down: while it is smaller than its larger child, swap with that child.

insert 85 into [90, 70, 80, 30, 60]
  place at index 5:        [90, 70, 80, 30, 60, 85]
  parent index 2 (80) < 85, swap:   [90, 70, 85, 30, 60, 80]
  parent index 0 (90) > 85, stop

remove max from [90, 70, 85, 30, 60, 80]
  take 90; move last (80) to root:  [80, 70, 85, 30, 60]
  larger child is 85 > 80, swap:    [85, 70, 80, 30, 60]
  index 2 has no children, stop      returns 90

def percolate_up(a, i):
    while i > 0:
        parent = (i - 1) // 2
        if a[i] <= a[parent]:
            return
        a[i], a[parent] = a[parent], a[i]
        i = parent

def percolate_down(a, i, size):
    while True:
        left, right, largest = 2 * i + 1, 2 * i + 2, i
        if left < size and a[left] > a[largest]:
            largest = left
        if right < size and a[right] > a[largest]:
            largest = right
        if largest == i:
            return
        a[i], a[largest] = a[largest], a[i]
        i = largest

Both walks follow one root-to-leaf path in a complete tree of height ⌊log₂n⌋: O(log n). Peeking at the root is O(1).

17.4Heapsort#

Heapsort sorts an array in place in two phases:

1. Heapify: turn the array into a max-heap by percolating down every internal node, from the last one (index n // 2 − 1) back to the root. This costs only O(n), because most nodes are near the bottom and percolate a short way.
2. Extract: repeatedly swap the root (the maximum) with the last element of the heap, shrink the heap by one, and percolate the new root down. The sorted region grows from the right.

def heapsort(a):
    n = len(a)
    for i in range(n // 2 - 1, -1, -1):     # heapify
        percolate_down(a, i, n)
    for end in range(n - 1, 0, -1):         # extract
        a[0], a[end] = a[end], a[0]
        percolate_down(a, 0, end)

[4, 10, 3, 5, 1]
heapify:            [10, 5, 3, 4, 1]
swap 10 to end:     [5, 4, 3, 1 | 10]
swap 5 to end:      [4, 1, 3 | 5, 10]
swap 4 to end:      [3, 1 | 4, 5, 10]
swap 3 to end:      [1 | 3, 4, 5, 10]

O(n log n) in every case, O(1) extra space, not stable.

17.5The priority queue ADT#

A priority queue removes items according to their priority, not merely their arrival order: the highest-priority item leaves first. An emergency room is the picture.

The heap wins whenever both operations are frequent. Python’s heapq module maintains a min-heap inside a list, so the smallest priority value comes out first. Store (priority, item) tuples; for a max-priority queue, negate the priorities.

import heapq
pq = []
heapq.heappush(pq, (2, "write report"))
heapq.heappush(pq, (1, "fix outage"))
heapq.heappush(pq, (3, "lunch"))
heapq.heappop(pq)      # (1, 'fix outage'): lowest number = most urgent
pq[0]                  # peek: (2, 'write report')

Priority queues drive Dijkstra’s shortest paths and Prim’s spanning tree (chapter 19), Huffman coding (chapter 20), event-driven simulations, and operating-system schedulers.

17.6Treaps#

A treap is a BST by key and a heap by a random priority assigned to each node at insertion. Insert as a BST leaf, then rotate the node up while its priority beats its parent’s. Because the priorities are random, the tree has the shape of a BST built from a random insertion order, so its expected height is O(log n) without any balance bookkeeping.

Part VIGraphs and algorithm design#

18Graphs#

Scope. zyBook reports (graphs); OA reports (reading graphs); zyBook (inferred: representations, directed and weighted graphs). Graphs are not in the catalog description; C950 treats them in depth.

18.1Terminology#

A graph is a set of vertices (nodes) and edges connecting pairs of them. Trees are a special case: connected graphs with no cycles. Graphs drop the hierarchy, so any vertex may connect to any other.

    A ----- B ----- D
    |       |
    C ----- F ----- E

Graph costs are stated in terms of V (number of vertices) and E (number of edges).

18.2Applications#

• Road and flight networks: vertices are places, weighted edges are distances or fares; shortest paths are routes.
• Computer networks: routers and links.
• Social networks: people and friendships (undirected) or follows (directed).
• Dependencies: tasks, course prerequisites, and build steps form DAGs whose topological order is a valid schedule.
• The web: pages and links, a directed graph.

18.3Adjacency lists#

An adjacency list stores, for each vertex, a list of its neighbors. In Python a dictionary of lists does it:

graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "F"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["F"],
    "F": ["B", "C", "E"],
}

Space is O(V + E). Listing a vertex’s neighbors costs its degree; checking whether a particular edge exists costs a scan of one list. Most real graphs are sparse, so this is the default representation.

18.4Adjacency matrices#

An adjacency matrix is a V × V grid in which entry [i][j] is 1 (or the edge weight) if an edge runs from vertex i to vertex j, and 0 otherwise. If zero-weight edges are allowed, 0 can no longer mean “no edge”; mark absent edges with None or ∞ instead. An undirected graph’s matrix is symmetric.

18.5Directed and weighted graphs#

In a directed graph, an adjacency list records only outgoing edges, and a matrix need not be symmetric. A cycle in a digraph must follow edge directions. In a weighted graph, the list stores (neighbor, weight) pairs and the matrix stores weights. A path’s total weight is the sum of its edge weights; its edge count is a separate quantity. The fewest-edge path can therefore differ from the cheapest path.

19Graph algorithms#

Scope. zyBook (inferred: breadth-first and depth-first search, Dijkstra, Bellman-Ford, topological sort, minimum spanning trees, all-pairs shortest paths). The study-guide summaries and exam reports cited here do not name these algorithms. Read them for recognition unless your current course materials require more depth.

19.1Breadth-first search#

Breadth-first search (BFS) explores outward from a start vertex in rings: all vertices one edge away, then two, and so on. A queue (chapter 11) enforces that order: vertices found first are explored first. A visited set prevents revisiting. On a tree, which has no cycles, this is level-order traversal (14.4).

from collections import deque

def bfs(graph, start):
    visited = {start}
    order = []
    frontier = deque([start])
    while frontier:
        v = frontier.popleft()
        order.append(v)
        for w in graph[v]:
            if w not in visited:
                visited.add(w)
                frontier.append(w)
    return order

On the graph of 18.1, with neighbors taken in the order listed in 18.3, BFS from A dequeues A (enqueuing B and C), then B (enqueuing D and F), then C (F is already seen), D, F (enqueuing E), and E:

BFS from A: A, B, C, D, F, E

BFS finds the fewest-edge path from the start to every reachable vertex. It runs in O(V + E) with an adjacency list.

19.2Depth-first search#

Depth-first search (DFS) follows one path as far as it goes, then backs up to the most recent vertex with an unexplored neighbor, like exploring a maze with one hand on the wall. Recursion provides the backing up through the call stack (6.2); an iterative version uses an explicit stack (chapter 10), whose last-in, first-out order is exactly “the most recent vertex”.

def dfs(graph, v, visited=None, order=None):
    if visited is None:
        visited, order = set(), []
    visited.add(v)
    order.append(v)
    for w in graph[v]:
        if w not in visited:
            dfs(graph, w, visited, order)
    return order

# DFS from A on the graph of 18.1: A, B, D, F, C, E
# (B's first new neighbor is D, a dead end; back to B, on to F;
#  F's first new neighbor is C, a dead end; back to F, on to E)

Also O(V + E). DFS detects cycles, finds connected components, and underlies topological sorting. The one-line distinction: BFS uses a queue and goes wide; DFS uses a stack and goes deep.

19.3Dijkstra’s shortest path#

Dijkstra’s algorithm finds the cheapest path from a start vertex to every other vertex in a weighted graph with non-negative weights. It keeps a tentative distance for each vertex (0 for the start, ∞ for the rest), repeatedly takes the unvisited vertex with the smallest distance (from a priority queue, 17.5), where BFS would take the oldest one from a plain queue, and relaxes its edges: if going through it gives a neighbor a shorter distance, record the new distance and predecessor.

edges: A-B 4, A-C 1, C-B 2, B-D 1, C-D 5

step  take  A   B   C   D
0     -     0   ∞   ∞   ∞
1     A     0   4   1   ∞
2     C     0   3   1   6      via C: B = 1+2, D = 1+5
3     B     0   3   1   4      via B: D = 3+1
4     D     0   3   1   4      final

With a binary heap it runs in O((V + E) log V). A negative edge breaks it, because a vertex taken as “done” might later be reachable more cheaply.

19.4Bellman-Ford#

Bellman-Ford handles negative weights by relaxing every edge, V − 1 times over. That many rounds suffice because a shortest path has at most V − 1 edges. A further round that still improves a distance reveals a negative cycle reachable from the start, around which costs fall forever. A negative cycle the start cannot reach never changes its distances, so this check does not see it. O(V · E).

19.5Topological sort#

A topological sort orders the vertices of a DAG so that every edge points forward: each vertex comes after everything it depends on. Task dependencies are the natural example. If a project must fetch code before compiling it, and compile before both testing and packaging, then fetch, compile, test, package is a valid order (so is fetch, compile, package, test). One method: repeatedly output a vertex with no remaining incoming edges and delete its outgoing edges. A graph with a cycle has no topological order. O(V + E).

19.6Minimum spanning trees#

A spanning tree of a connected, undirected graph is a subset of edges that connects every vertex with no cycles (V − 1 edges). A minimum spanning tree (MST) has the smallest total weight: the cheapest way to cable every building on a campus.

• Kruskal’s algorithm: sort edges by weight; add each edge unless it would create a cycle (checked with a disjoint-set structure). O(E log E).
• Prim’s algorithm: grow one tree from a start vertex, always adding the cheapest edge leaving it (via a priority queue). O(E log V).

Both are greedy algorithms (21.3) that happen to be provably optimal.

19.7All-pairs shortest paths#

The Floyd-Warshall algorithm computes the shortest distance between every pair of vertices with a V × V matrix, considering each vertex in turn as a possible intermediate stop: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). O(V³) time, O(V²) space, negative edges allowed (negative cycles are not). It is dynamic programming (21.4) on graphs.

20Huffman coding#

Scope. Study guide (Huffman coding as lossless compression with variable-length codes; shorter codes for frequent characters; reading code lengths and bit counts); zyBook (inferred: Huffman compression and its implementation).

20.1Fixed-length and variable-length codes#

Text is stored as binary codes. A fixed 8-bit code spends the same number of bits on every character, whether it is e (very common) or z (rare). If a few characters dominate, giving them short codes and rare characters long ones lowers the average bits per character. Morse code applies the same idea: E is one dot.

Huffman coding is a lossless compression technique that builds an optimal prefix-free, variable-length binary code from the character frequencies of the input: more frequent characters get shorter codes, which reduces the file size. Lossless means decompression restores the input exactly, unlike lossy compression (JPEG photos, MP3 audio), which discards detail.

20.2Building the Huffman tree#

1. Count each character’s frequency.
2. Make a leaf node per character, weighted by frequency, and put them all in a min-priority queue (17.5). Each merge in step 3 is two removals and one insertion on that queue.
3. Repeatedly remove the two lowest-weight nodes, join them under a new parent whose weight is their sum, and insert the parent.
4. When one node remains, it is the root. Label each left edge 0 and each right edge 1; a character’s code is the sequence of labels from the root to its leaf.

Example: a 20-character text with frequencies A 10, B 5, C 3, D 2.

merge C(3) + D(2)   -> node 5
merge B(5) + (5)    -> node 10
merge A(10) + (10)  -> root 20

          (20)
         0/  \1
        A     (10)
            0/   \1
           B     (5)
               0/   \1
              C       D

codes: A = 0, B = 10, C = 110, D = 111

Which child goes left is a convention, and ties can be broken either way, so different correct trees exist. Here the ties do not change any code length, but in general they can. With frequencies 2, 2, 1, 1, one tie-break gives every symbol a 2-bit code and another gives lengths 1, 2, 3, 3. What every Huffman tree for the same frequencies shares is the total: both of those come to 12 bits, the minimum possible.

20.3Counting bits#

Total bits = sum over characters of frequency × code length:

Compare: a fixed 8-bit encoding needs 20 × 8 = 160 bits; the best fixed-length code for four symbols needs 2 bits each, 40 bits. Huffman uses 35, an average of 35/20 = 1.75 bits per character. The compression ratio against that encoding is 160/35 ≈ 4.6; equivalently the output is 35/160 ≈ 22% of the original size. These figures count only the encoded text; the stored tree or frequency table (20.4) adds overhead, which matters for short inputs.

20.4Decoding and the prefix property#

No Huffman code is a prefix of another, because every character sits at a leaf, never on the path to another leaf. So a decoder can read bits one at a time, walking down from the root, and emit a character whenever it reaches a leaf, with no separators needed:

bits: 0 10 110 0 111
      A  B  C  A  D        "0101100111" decodes to ABCAD

The tree (or the frequency table) must be stored with the compressed data so the decoder can rebuild it. A decoder rebuilding from frequencies alone must break ties and assign left and right exactly as the encoder did, or it builds a different tree and misreads the bits. Building the tree with a heap costs O(k log k) for k distinct characters; encoding and decoding are linear in the text. Huffman coding appears inside ZIP (DEFLATE), PNG, JPEG, and MP3. It is the textbook example of a greedy algorithm that is provably optimal: no prefix code that assigns one codeword per character uses fewer total bits.

21Algorithm design strategies#

Scope. Catalog (problem-solving techniques for efficient software); study guide (algorithm characteristics and factors); zyBook (inferred: heuristics, greedy algorithms, dynamic programming).

21.1Brute force#

Brute force tries every candidate and keeps the best. It is simple and obviously correct, and it is the right first answer for small inputs. It fails at scale: checking every route through 20 cities means about 10¹⁷ orderings.

21.2Divide and conquer#

Divide and conquer splits a problem into independent smaller problems of the same kind, solves them recursively, and combines the results. Binary search (discard half), merge sort (split, sort, merge), and quicksort (partition, sort parts) are the course’s examples. The cost follows from the recurrence (6.4): solving both halves with linear combining gives O(n log n); keeping only one half with constant work, as binary search does, gives O(log n).

21.3Greedy algorithms#

A greedy algorithm builds a solution by making the locally best choice at each step and never reconsidering. It is fast and simple, and it is correct only for problems with the right structure.

• Making change with US coins (25, 10, 5, 1): always take the largest coin that fits. Greedy is optimal here.
• With coins 1, 3, and 4, making 6 greedily gives 4 + 1 + 1 (three coins); the optimum is 3 + 3 (two). Greedy fails.
• Optimal greedy algorithms in this guide: Huffman coding, Dijkstra, Kruskal, Prim.

The fractional knapsack problem (take items by value per kilogram, splitting the last one) is greedy-optimal; for the 0/1 knapsack (items cannot be split) greedy can miss the best load, and the standard exact method is dynamic programming (21.4).

21.4Dynamic programming#

Dynamic programming solves problems whose subproblems overlap (the same subproblem recurs many times) and whose optimal solution is built from optimal solutions to subproblems. It solves each subproblem once and stores the answer, either top-down (memoization) or bottom-up (tabulation).

def fib(n):                       # bottom-up: O(n) instead of O(2^n)
    if n < 2:
        return n
    prev, cur = 0, 1
    for _ in range(n - 1):
        prev, cur = cur, prev + cur
    return cur

The longest common subsequence (LCS) of two strings is the classic table-filling example. A subsequence keeps order but may skip characters: the LCS of DATA and GATE is AT. Entry [i][j] holds the LCS length of the first i characters of one string and the first j of the other; if those characters match, it is 1 + [i−1][j−1], otherwise the larger of [i−1][j] and [i][j−1]. O(mn) time for strings of lengths m and n. The same pattern drives the 0/1 knapsack, edit distance (spell checkers, diff), and Floyd-Warshall.

21.5Heuristics#

A heuristic trades guaranteed optimality for speed: it finds a good answer quickly where the best answer would take too long. For the traveling salesperson problem (finding the shortest tour is NP-hard; 2.2), “always visit the nearest unvisited city” produces a usually reasonable tour in O(n²), where every known exact method takes exponential time in the worst case. A heuristic algorithm is the right tool when an approximate answer now is worth more than an exact answer never.

21.6Choosing a strategy#

ReferenceEnd matter#

22Complexity reference#

Scope. Summary of costs stated in earlier chapters. Average case unless marked; h is tree height.

22.1Lists, stacks, and queues#

22.2Hash tables, trees, and heaps#

22.3Algorithms#

23Recognition map#

Scope. Phrasings drawn from the definitions in this guide, matched to the term an exam stem is describing. Use it as a last-day review: cover the right column and answer from the left.

23.1From description to term#

23.2From code shape to algorithm#

24Sources#

Scope. What each scope note cites, with what each source can and cannot establish.

24.1Course sources#

• Western Governors University, Institutional Catalog, June 2026: the C949 course description and its place in the Computer Science and Software Engineering programs. The only primary source here.
• WGU’s C949 study guide and practice exam: seen only through student summaries. A public study site built for the course in September 2026 (github.com/DietKyle956/c949-study-guides) maps its lessons to the practice exam’s topics: Big-O, Python reading, ADTs and records, stacks, queues, deques, priority queues, linked lists, hash tables, counting sort and quickselect, and Huffman coding. Student-posted copies of the v4 study guide open with “Explains Algorithms” and the characteristics of algorithms.
• Student course reports: rickp.dev, week 1 (v3 and v4 versions, zyBook chapter 1 titles) and rickp.dev, passed (OA format and topics, chapter guidance), and onlinedegreeblogs.com (topic list including balanced trees, heaps, sets, graphs, and B-trees).
• zyBooks, Data Structures in Pseudocode: the public table of contents whose first chapter title and topics match the student reports of the v4 core. The “zyBook (inferred)” label in scope notes rests on this match.

24.2Supplemental references#

• Goodrich, Tamassia, and Goldwasser, Data Structures and Algorithms in Python (Wiley): positional lists, deque method names, amortized analysis.
• Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms (MIT Press): asymptotic notation, heaps, hashing analysis, graph algorithms, Huffman codes.
• Jay Wengrow, A Common-Sense Guide to Data Structures and Algorithms (Pragmatic Bookshelf): the gentler companion text C949 students most often recommend.
• Python documentation for list, dict, set, collections, and heapq.