21. COMP2521 Revision

Turn Familiar Algorithms Into Decisions#

The review lectures test three connected skills: tracing a specified variant, implementing a representation correctly, and choosing an approach from its costs and requirements. Use this chapter after the teaching chapters. For a programming problem, first write its contract, identify edge cases, choose a representation, then justify both correctness and complexity before coding.

For example, “find a path” differs from “find the fewest edges”, “find minimum total weight”, and “connect all vertices cheaply”. DFS or BFS can establish reachability; BFS finds fewest-edge paths; Dijkstra handles nonnegative weighted shortest paths; Prim or Kruskal builds a minimum spanning tree. Similar-looking graph drawings do not make those objectives interchangeable.

A Selection Map#

Practice. A set needs membership, insertion and sorted traversal. Why can a hash table be an incomplete answer even if membership is fast?

Revisit the Lecture Traces#

Iterative DFS Is Variant-Sensitive#

The course-review graph has adjacency lists a:[b,c], b:[a,e,f], c:[a,d,f], d:[c,e], e:[b,d], f:[b,c,g,h], g:[f], h:[f]. The lecture's stack algorithm pushes neighbours in listed order and marks a vertex when popped. Because a stack is last-in-first-out, the last pushed neighbour is explored next.

Starting at a, push b then c; visit c next. From c, push d then f; visit f, then its last pushed child h, then g, then b, then e, then d. Discovery output is a,c,f,h,g,b,e,d. Pending entries for already visited vertices may remain and get discarded later. Graph Traversal explains why marking on pop can produce duplicates and why its stack bound differs from marking on push.

Practice. Would recursive DFS scanning these adjacency lists in their printed order necessarily have the same order?

A Shortest-Path Tree From the Revision Matrix#

The second revision lecture gives this undirected weighted adjacency matrix. In this example zero means no edge, not a zero-weight edge.

Run Dijkstra from a. Tie-breaking here selects c before e, then b before d. Relaxation replaces a tentative distance only if the new route is smaller.

The predecessor edges are a-b, a-c, a-e, e-d, d-f. Following them backwards reconstructs paths: for f, f -> d -> e -> a, so the forward route is a-e-d-f, weight 17. The deck briefly displays d=12 after examining b; that would overwrite a better route and contradict relaxation. Retain d=10, as the minimum rule requires.

Watch that unsuccessful relaxation from b to d, then the successful improvement from d to f:

Practice. Why does b retain direct predecessor a, while f replaces predecessor e with d?

AVL: Find the First Relevant Imbalance#

Use the second revision deck's tree immediately after inserting 4. Its left branch contains 20 -> 6 -> 1 -> 3 -> 4, with the other subtrees shown in the figure. Use edge-height convention: empty height -1, leaf height 0; balance factor is left height minus right height.

Working upward, node 3 has balance -1, but node 1 has no left child and a right subtree of height one, so balance is -2. Its right child is right-heavy: perform a left rotation at 1, producing subtree root 3 with children 1 and 4. This changes 6's left-subtree link to 3. Recompute heights after the pointer updates. The next lecture step inserts 10: follow 20 -> 6 -> 13 -> 8, then attach 10 as the right child of 8. Now node 20 has balance +2, and its left child 6 has balance -1, a left-right case. First rotate left at 6, promoting 13 and moving 8 to become 6's right child. Then rotate right at 20, promoting 13 to the overall root and moving 14 to become 20's left child. The final root is 13, with left child 6 and right child 20. Recompute heights in dependency order after each rotation. Follow AVL Trees for the general return-path repair rule.

Practice. Why can't the rotation simply swap the values 1 and 3?

MST: Total Network Weight Is the Objective#

Starting Prim at A, choose AB=1. The next minimum crossing edges tie: AC=4 and BE=4. Choose AC for this trace. Then BE=4, ED=1, and EF=2. Each edge brings in one new vertex; all six vertices are connected using five edges, total 12. Choosing BE before AC can still give the same minimum total. A tie can change the trace without making either result incorrect.

Kruskal considers weights globally: accept AB=1, DE=1, EF=2, then AC=4 and BE=4. These five edges connect all vertices without a cycle, also total 12. Explain the cycle check and representation before giving a Kruskal complexity claim: the lecture's DFS-based check differs from a union-find implementation.

Practice. Does an MST rooted at A necessarily give every vertex a shortest path from A?

Heap Structure and Ordering Are Separate#

The heap array in level order is [2,7,4,8,11,9,5,10]. It is complete: the final level fills from the left. Every parent is at most its children, so 2 is the minimum. This does not make the array sorted: 7 appears before 4.

Removing 2, move the final 10 to the root and reduce the logical size. Compare children 7 and 4, choose the smaller 4, and exchange. At that position choose child 5 over 9, and exchange again. The result is [4,7,5,8,11,9,10]. Choosing either smaller child locally is what preserves heap order after sinking; blindly selecting the left child would be wrong here.

Practice. What is the next minimum? Can binary search be used on the heap's level-order array?

Programming Workshop#

Top k Without Modifying or Copying the Input#

The second revision deck asks for the most trusted contestants in descending score order while retaining the original array. A simple constant-space approach scans repeatedly, choosing the next item below the previously printed item in a total ordering. Break score ties by original index so every contestant has a distinct rank. Preconditions: 0 <= k <= n, readable contestants, and valid name strings.

#include <stdbool.h>
#include <stdio.h>

struct contestant { const char *name; int trust; };

void printTopKTrusted(const struct contestant a[], int n, int k) {
    bool havePrevious = false;
    int previous = 0;
    for (int printed = 0; printed < k; printed++) {
        int best = -1;
        for (int i = 0; i < n; i++) {
            if (havePrevious &&
                (a[i].trust > a[previous].trust ||
                 (a[i].trust == a[previous].trust && i <= previous))) {
                continue;
            }
            if (best == -1 || a[i].trust > a[best].trust ||
                (a[i].trust == a[best].trust && i < best)) {
                best = i;
            }
        }
        puts(a[best].name);
        previous = best;
        havePrevious = true;
    }
}

For scores [7_A,9_B,9_C,3_D] and k=3, print B,C,A. After B, allow lower scores or equal-score later indices, so C is eligible while B is not. After C, the next eligible maximum is A. Each scan selects the maximum remaining rank; induction shows the output is the first k descending ranks. There are k scans of n entries: Θ(kn) time, constant auxiliary space. k=0 prints nothing; negative scores and the maximum representable integer need no sentinel score.

Practice. Why does remembering only the previous score fail when two contestants have that score?

Three Tree Orders With Two Recursive Call Sites#

The revision constraint is at most three recursive call sites in the program. There is no need for separate duplicated traversal routines: print before, between or after the same two subtree calls. Here use struct treeNode { int value; struct treeNode *left, *right; }; and order values 0,1,2.

void traverse(const struct treeNode *t, int order) {
    if (t == NULL) return;
    if (order == 0) printf("%d\n", t->value);
    traverse(t->left, order);
    if (order == 1) printf("%d\n", t->value);
    traverse(t->right, order);
    if (order == 2) printf("%d\n", t->value);
}

For root 4 with children 2 and 6, preorder prints 4,2,6, inorder 2,4,6, postorder 2,6,4. The code contains two recursive call expressions, although executing it visits every node. Time is linear in nodes; auxiliary stack space depends on height. Invalid order values are outside the contract; do not silently claim they produce one of the three traversals.

Card Collections Require Multiplicities#

The deck's card problem asks whether your count of every card is at least your friend's count. A set of names loses duplicates and cannot answer this. Build a hash map of your card counts, then decrement for each friend's card. If a missing entry or zero count is encountered, return false; otherwise all required copies have been matched.

For yours [P,P,Q] and friend's [P,Q,Q], initial counts are P:2,Q:1. Consuming P leaves P:1; consuming first Q leaves zero; second Q fails. With friend's [P,P], both decrements succeed. Applications of Hash Tables provides map implementation and ownership details.

The following is a complete solution for the deck's string-card signature. It borrows the input strings only while the call runs; it allocates and frees its own counter nodes. NULL strings and negative lengths are outside the contract. Allocation failure exits the teaching program rather than falsely reporting that one trainer is worse. The bucket count is proportional to n, so with reasonably distributed hashes its expected chain lengths remain bounded. The exact key comparison uses strcmp, not pointer equality: equal card names may live at different addresses.

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct cardCount {
    const char *name;              /* Borrowed; do not free. */
    int remaining;
    struct cardCount *next;
};

static size_t cardBucket(const char *name, size_t buckets) {
    size_t hash = 5381;
    for (const unsigned char *p = (const unsigned char *)name; *p; p++)
        hash = hash * 33u + *p;
    return hash % buckets;
}

static void freeCardCounts(struct cardCount **table, size_t buckets) {
    for (size_t i = 0; i < buckets; i++) {
        struct cardCount *p = table[i];
        while (p != NULL) {
            struct cardCount *next = p->next;
            free(p);
            p = next;
        }
    }
    free(table);
}

bool betterTrainer(char *myCards[], int n, char *friendsCards[], int m) {
    if ((size_t)n > (SIZE_MAX - 1) / 2) {
        fputs("too many cards\n", stderr);
        exit(EXIT_FAILURE);
    }
    size_t buckets = 2 * (size_t)n + 1;
    struct cardCount **table = calloc(buckets, sizeof *table);
    if (table == NULL) {
        fputs("out of memory\n", stderr);
        exit(EXIT_FAILURE);
    }
    for (int i = 0; i < n; i++) {
        size_t b = cardBucket(myCards[i], buckets);
        struct cardCount *p = table[b];
        while (p != NULL && strcmp(p->name, myCards[i]) != 0)
            p = p->next;
        if (p == NULL) {
            p = malloc(sizeof *p);
            if (p == NULL) {
                freeCardCounts(table, buckets);
                fputs("out of memory\n", stderr);
                exit(EXIT_FAILURE);
            }
            *p = (struct cardCount){myCards[i], 0, table[b]};
            table[b] = p;
        }
        p->remaining++;
    }
    bool enough = true;
    for (int i = 0; i < m; i++) {
        size_t b = cardBucket(friendsCards[i], buckets);
        struct cardCount *p = table[b];
        while (p != NULL && strcmp(p->name, friendsCards[i]) != 0)
            p = p->next;
        if (p == NULL || p->remaining == 0) {
            enough = false;
            break;
        }
        p->remaining--;
    }
    freeCardCounts(table, buckets);
    return enough;
}

After counting your first i cards, each node's remaining value is its multiplicity in that prefix. After processing the first j of your friend's cards without failure, it is your original multiplicity minus those j requirements. A missing or zero count therefore proves a shortage; if all requirements are consumed, every required multiplicity was available. There are n+m hash operations with expected O(1) bucket work under the stated distribution/load assumption, so expected table work is O(n+m). Hashing and comparing a card name reads its characters; for unbounded names, add the total string-character work and any collision comparison work. Storage is O(d+n) slots and nodes for d distinct cards, hence O(n). Worst-case collisions still permit O(n(n+m)) string comparisons.

Practice. Explain the deck's O(n+m) requirement carefully for string cards.

Left Median of a Sorted Linked List#

The list must be nonempty and sorted. Use a slow pointer advancing once and a fast pointer advancing twice. Start fast at the second node so an even-length list stops at the left median:

int medianLinkedList(const struct node *head) {
    const struct node *slow = head;
    const struct node *fast = head->next;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow->value;
}

For [1,3,5,7], slow starts at 1, fast at 3; one iteration moves slow to 3, fast to 7; stop because fast has no successor. Return 3. For [1,3,5,7,9], a second iteration moves slow to 5 and fast to null, giving 5. Each iteration advances through the list without allocating: linear time, constant auxiliary space. An empty list needs a separate error/result contract because an integer return alone cannot identify a missing median.

Practice. Why can this function select the middle node without sorting, but cannot guarantee a statistical median on an unordered list?

Reach an Enemy Through a Graph#

For the deck's path from vertex 0 to n-1, run DFS or BFS from 0, then check whether the destination was discovered. Mark visited vertices to prevent endless revisits around cycles. Use the graph's direction consistently: a directed alliance u -> v does not imply v -> u. A one-vertex graph has an empty path from 0 to itself under the usual reachability definition; an empty graph needs an explicit contract because there is no vertex 0.

With adjacency lists, one whole reachable-component traversal takes O(V+E) in the worst case; with a matrix, scanning all candidate neighbours gives O(V²). Graph Traversal includes complete C routines rather than an invented Graph API here.

Theory Workshop#

Scaling Predictions Need an Explicit Model#

The revision deck compares A taking 1.5 seconds on 10,000 entries with linear growth, and B taking 0.2 seconds there with quadratic growth. If those are assumed pure scaling models, multiplying size by ten predicts 15 seconds for A and 20 for B. A wins at 100,000 even though B won at 10,000.

Big-Oh alone is insufficient to produce those exact predictions: an upper bound is not a measured equality and can hide fixed costs or lower-order terms. The worked estimate assumes constants stay fixed and the dominant model applies across that range. This is a useful projection to test, not a guaranteed stopwatch result.

Practice. In that model, solve the approximate crossover size.

Analyse the Loops That Actually Run#

The deck's function iterates i < a and, inside, j < b, reading arr[(i+j)%n]. Assuming valid positive sizes, readable array entries and fixed-width non-overflowing arithmetic, there are exactly ab inner iterations. Modulo does not imply scanning the n entries; it computes one index. Thus time is Θ(ab) and auxiliary space constant.

Practice. If n doubles while a and b remain fixed, how does the iteration count change?

When a Trie Adds No Nodes#

Inserting an existing key adds no nodes and may simply retain an already set terminal marker. Inserting a prefix can also add no nodes if its whole path already exists: after cart is stored, inserting car only marks the existing r node terminal. Shared character paths are not sufficient to say a word is stored; its endpoint marker matters.

For autocomplete on prefix ca, a trie follows two transitions then traverses the matching subtree. An ordinary hash table supports exact equality lookup but has no natural “all keys beginning with ca” bucket; it generally needs an additional index or a scan of keys. Include output length when comparing prefix-query costs.

Arrays, Trees and Priority Queues#

An unordered array can append cheaply but must scan for membership or an extreme. An ordered array searches by binary search, but inserting in the middle shifts a linear number of entries; deleting also closes a gap. A balanced BST spreads updates across a logarithmic-height path without moving the entire suffix. An unbalanced BST can become a chain and lose that advantage.

A heap specialises further: it keeps an extreme at the root without maintaining a complete sorted order. It offers cheap peek and logarithmic insertion/removal but cannot replace a balanced BST for efficient arbitrary key lookup or sorted range traversal. These are trade-offs among operation costs, not a universal hierarchy of better structures.

Practice. Give one advantage and one disadvantage of insertion sort over quicksort on random input, then radix over comparison sorting.

Common Mistakes to Diagnose During Revision#

Use this list after an incorrect answer to find the reason, then return to the relevant worked explanation.

A Final Self-Test#

For each major technique, close the notes and explain: what problem it solves; the representation; valid inputs; the next-step rule; the maintained invariant; why it stops; and what work produces the time/space bound. Then implement a small version and test empty, singleton, duplicate, absent-target and structurally extreme cases where those fit the contract.

If you can trace only a memorised example, change its labels or introduce a tie. If you can recite only a complexity table, derive its sum, levels or path length. If you can write code only by copying it, reconstruct the pointer or array state changes first. The technical goal in the two review decks is the ability to reason from the mechanism to an implementation and justify the choice.

More exam-style practice#

Work each prompt before opening its answer. State the invariant or cost assumption that makes your reasoning valid.

Question 1. Choose between a heap and a sorted array for 1,000 inserts followed by one maximum query. Which operation costs drive the choice?

Question 2. A question asks whether a graph has an Eulerian circuit, not for the circuit itself. What minimal checks avoid unnecessary backtracking?

Question 3. A tree search runs in 3 ms for 1,024 nodes. Is 6 ms guaranteed for 2,048 nodes if the implementation is a BST? Explain.