From the free course Data Structures and Algorithmic Analysis on Lykke

Final Exam and Course Review

Key concepts: Exam Logistics · Regrade Policies · Comprehensive Review

Comprehensive review of course materials and logistics for the final examination.

Final Exam and Course Review

The final assessment in a data structures and algorithms course (CS112) represents the synthesis of a semester's worth of computational theory, implementation patterns, and performance analysis. This review serves as a comprehensive technical guide, bridging the gap between abstract algorithmic concepts and the rigorous demands of a final examination. Success on the final requires more than rote memorization; it demands a deep understanding of how data structures interact with memory, how algorithms scale with input size, and the trade-offs inherent in every design decision.

Administrative Logistics and Exam Protocol

The final exam is a high-stakes environment where administrative precision is as important as technical proficiency. Unlike midterms, the final is comprehensive and often follows a stricter protocol regarding identification and submission.

Exam Day Procedures

The exam typically spans a three-hour window (e.g., 4:00 PM – 7:00 PM). Students are expected to arrive at least 30 minutes early to facilitate seating and ID verification.

Requirement Description Rationale
Valid ID University-issued photo ID or government ID. Mandatory for identity verification during exam submission.
Room Assignment Often different from midterm locations; check the course portal. Capacity management and proctoring optimization.
Materials Usually restricted to pens/pencils; check if a "cheat sheet" is allowed. Focus on internalizing concepts rather than external retrieval.

Post-Exam: Grading and Regrades

Once the final is graded, results are released via platforms like Gradescope. The "Regrade Window" is notoriously narrow—often closing within 24 hours of grade release.

Regrade Policy Insight: Regrade requests are intended to correct grading errors where the rubric was applied incorrectly. They are not a platform for negotiating partial credit. Students are generally limited to one request per sub-question.


Core Concept I: Union-Find (Disjoint Sets)

The Union-Find data structure solves the Dynamic Connectivity problem. It maintains a set of elements partitioned into non-overlapping subsets.

Mechanics and Implementation

We track components using an array id[]. The two primary operations are:

  1. find(p): Return the identifier for the component containing p.
  2. union(p, q): Merge the components containing p and q.

While the "Quick-Find" and "Quick-Union" approaches provide baseline implementations, the Weighted Quick-Union with Path Compression (WQUPC) is the gold standard for performance.

Algorithm Union Find Connected
Quick-Find $O(N)$ $O(1)$ $O(1)$
Quick-Union $O(\text{tree height})$ $O(\text{tree height})$ $O(\text{tree height})$
Weighted QU $O(\log N)$ $O(\log N)$ $O(\log N)$
WQUPC $\alpha(N)^*$ $\alpha(N)^*$ $\alpha(N)^*$
*$\alpha(N)$ is the inverse Ackermann function, which is effectively constant ($< 5$) for all practical values of $N$.

Worked Example: Weighted Quick-Union

Suppose we have 10 elements (0-9). We perform union(4, 3), union(3, 8), and union(6, 5).

  • In Weighted QU, we always attach the smaller tree to the root of the larger tree to keep the structure flat.
  • If we then union(9, 4), and 4 is the root of a tree of size 3, 9 becomes a child of 4.
public int find(int i) {
    while (i != parent[i]) {
        parent[i] = parent[parent[i]]; // Path compression (halving)
        i = parent[i];
    }
    return i;
}

public void union(int p, int q) {
    int rootP = find(p);
    int rootQ = find(q);
    if (rootP == rootQ) return;
    if (size[rootP] < size[rootQ]) {
        parent[rootP] = rootQ;
        size[rootQ] += size[rootP];
    } else {
        parent[rootQ] = rootP;
        size[rootP] += size[rootQ];
    }
}

Core Concept II: Asymptotic Analysis (Big O)

Asymptotic analysis is the mathematical framework used to describe the limiting behavior of a function. In CS112, it is used to classify algorithms by how their running time or space requirements grow as the input size $N$ grows.

The Hierarchy of Growth

Understanding the relative order of growth is critical for selecting the right algorithm for a given scale.

  1. Constant: $O(1)$ — Array access, basic arithmetic.
  2. Logarithmic: $O(\log N)$ — Binary search, balanced BST operations.
  3. Linear: $O(N)$ — Single loop, traversing a linked list.
  4. Linearithmic: $O(N \log N)$ — Merge Sort, Quick Sort (average).
  5. Quadratic: $O(N^2)$ — Nested loops, Elementary sorts (Selection/Insertion).
  6. Exponential: $O(2^N)$ — Exhaustive search, recursive Fibonacci.

Common Pitfalls in Big O

  • Ignoring Constants in Small N: While $O(N^2)$ is worse than $O(N \log N)$ asymptotically, for $N=10$, an $N^2$ algorithm with a small constant might be faster.
  • Confusing Best, Average, and Worst Case: Big O usually refers to the Upper Bound (worst case), while Big Omega ($\Omega$) refers to the Lower Bound. Big Theta ($\Theta$) indicates a tight bound where the upper and lower bounds match.

Core Concept III: Sorting Algorithms

Sorting is the bedrock of algorithmic study. The final exam tests the ability to distinguish between Stability, In-place execution, and Complexity.

Comparison of Sorting Methodologies

Algorithm Best Case Average Case Worst Case Space Stable? In-place?
Selection $O(N^2)$ $O(N^2)$ $O(N^2)$ $O(1)$ No Yes
Insertion $O(N)$ $O(N^2)$ $O(N^2)$ $O(1)$ Yes Yes
Merge Sort $O(N \log N)$ $O(N \log N)$ $O(N \log N)$ $O(N)$ Yes No
Quick Sort $O(N \log N)$ $O(N \log N)$ $O(N^2)$ $O(\log N)$ No Yes

Merge Sort: Divide and Conquer

Merge Sort is a recursive algorithm that splits the array into halves, sorts them, and merges the results.

  • The Merge Step: Requires an auxiliary array. This is why Merge Sort is not in-place.
  • Performance: Guaranteed $O(N \log N)$, making it ideal for large datasets where memory is not the primary constraint.

Quick Sort: The Partitioning Strategy

Quick Sort selects a "pivot" and partitions the array such that elements less than the pivot are on the left and greater are on the right.

  • Worst Case: Occurs when the pivot is the smallest or largest element (e.g., sorting an already sorted array without shuffling).
  • Optimization: Randomized shuffling before sorting guarantees $O(N \log N)$ average performance.

Core Concept IV: Search Trees

Search trees facilitate efficient retrieval, insertion, and deletion. The transition from simple Binary Search Trees (BSTs) to Balanced Trees is a major exam focus.

Binary Search Trees (BST)

A BST is a tree where each node has a key, and every node's key is larger than all keys in its left subtree and smaller than all keys in its right subtree.

  • Problem: In the worst case (inserting keys in sorted order), a BST becomes a linked list, degrading performance to $O(N)$.

Balanced Search Trees (LLRB)

Left-Leaning Red-Black (LLRB) Trees are a 2-3 tree representation using binary nodes. They maintain balance by ensuring no path from the root to a leaf is more than twice as long as any other.

The Red-Link Rule: Red links lean left. No node has two red links connected to it. The tree has "perfect black balance" (every path from root to null link has the same number of black links).

Tree Rotations

Rotations are the fundamental operations used to maintain balance during insertion and deletion.

  • Rotate Left: Used when a red link leans right.
  • Rotate Right: Used to fix temporary 4-nodes or unbalance.
  • Color Flip: Used when both children are red.
private Node rotateLeft(Node h) {
    Node x = h.right;
    h.right = x.left;
    x.left = h;
    x.color = h.color;
    h.color = RED;
    return x;
}

Core Concept V: Directed Graphs (Digraphs)

Graphs represent relationships between objects. In a Directed Graph, edges have a specific orientation (from $v$ to $w$).

Key Graph Algorithms

  1. Depth-First Search (DFS): Explores as far as possible along each branch before backtracking. Used for cycle detection and topological sort.
  2. Breadth-First Search (BFS): Explores all neighbors at the current depth before moving to the next level. Used for finding the shortest path in unweighted graphs.
  3. Topological Sort: An ordering of vertices such that for every directed edge $uv$, vertex $u$ comes before $v$. This is only possible in Directed Acyclic Graphs (DAGs).
Problem Algorithm Complexity
Pathfinding (Any) DFS $O(V + E)$
Shortest Path (Unweighted) BFS $O(V + E)$
Cycle Detection DFS (Stack-based) $O(V + E)$
Topological Sort DFS (Post-order Reverse) $O(V + E)$

Cycle Detection and DAGs

A Directed Acyclic Graph (DAG) is a digraph with no directed cycles. In a final exam context, you are often asked to determine if a graph is a DAG or to provide a topological ordering. If a DFS finds an edge pointing to an ancestor in the recursion stack (a "back edge"), a cycle exists.


Exam Strategy: How to Approach Problem Types

The CS112 final usually consists of three distinct problem types. Mastering each requires a different mental model.

1. Trace Problems

You are given an initial state (e.g., an array or a tree) and a sequence of operations.

  • Strategy: Work slowly. For Union-Find, draw the trees. For Sorting, write out the array after each pass or partition.
  • Common Error: Skipping steps. In Quick Sort partitioning, missing one swap can invalidate the entire result.

2. Code Completion/Debugging

You are given a snippet of Java code with blanks or errors.

  • Strategy: Identify the "Invariants." For a BST put method, remember the recursive structure: node.left = put(node.left, key, val).
  • Focus: Pay attention to edge cases like null checks and boundary conditions in loops (i < N vs i <= N).

3. Design and Analysis

You are given a real-world scenario and must choose the best data structure.

  • Example: "You need to store a million usernames and check for duplicates instantly."
  • Answer: A Hash Set or a Balanced BST. If the question asks for the usernames in alphabetical order, the Balanced BST is superior because it supports in-order traversal in $O(N)$.

Summary Table: Data Structure Performance

Structure Search (Avg) Search (Worst) Insert (Avg) Notes
Array (Unsorted) $O(N)$ $O(N)$ $O(1)$ Fast insert, slow search.
Array (Sorted) $O(\log N)$ $O(\log N)$ $O(N)$ Binary search enabled.
Linked List $O(N)$ $O(N)$ $O(1)$ No random access.
BST $O(\log N)$ $O(N)$ $O(\log N)$ Depends on input order.
LLRB (Balanced) $O(\log N)$ $O(\log N)$ $O(\log N)$ Guaranteed performance.
Hash Table $O(1)$ $O(N)$ $O(1)$ No ordering properties.

Final Review Checklist

  • Union-Find: Can you perform a union operation on a Weighted Quick-Union tree and show the resulting structure?
  • Big O: Can you simplify $3N^2 + 10N \log N + 100$ to its asymptotic class?
  • Sorting: Do you know which sorts are stable? (Merge, Insertion).
  • Trees: Can you perform a Left Rotation on a specific node in a Red-Black tree?
  • Graphs: Can you trace a BFS and list the order in which vertices are visited?
  • Logistics: Do you have your ID and know your specific exam room?

The final exam is a test of endurance and clarity. By categorizing problems into these core domains and understanding the underlying mechanics of each data structure, you can navigate the complexities of the assessment with the precision of a senior engineer. Good luck.

Final Exam and Course Review - Data Structures and Algorithmic Analysis - diagram 1
Final Exam and Course Review - Data Structures and Algorithmic Analysis - diagram 1
Final Exam and Course Review - Data Structures and Algorithmic Analysis - diagram 2
Final Exam and Course Review - Data Structures and Algorithmic Analysis - diagram 2
Final Exam and Course Review - Data Structures and Algorithmic Analysis - diagram 3
Final Exam and Course Review - Data Structures and Algorithmic Analysis - diagram 3

Source Materials

Study Data Structures and Algorithmic Analysis on Lykke

This course page is free to open: signed out, you can read its first two sections, and signing in, on any plan, opens the rest. The free Lykke Chrome extension syncs your own Canvas courses, so ChatGPT, Claude and Muse can answer from your classes and deadlines. It only reads Canvas.

Add the free extensionSign in to open every section

All sections of Data Structures and Algorithmic Analysis · Browse more course pages

Final Exam and Course Review — Data Structures and Algorithmic Analysis | Lykke