MTH 4300 Final Exam Practice Questions

Exam format

Exams in MTH 4300 revolve around 3 classes of questions:

Tracing - evaluating the output of a code snippet
Debugging - given a code snippet, diagnose and fix the errors
Implementation - write code from scratch to solve a problem

A note about partial credit

Clarity is the only way you'll get points. If you don't even understand what it is you're trying to say, then how can I?

Tracing

Consider the following program. It builds a BST by inserting values in order, then runs an inorder traversal and two depth-finding queries.

#include <iostream>

struct Node {
    int   val;
    Node* left;
    Node* right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

Node* insert(Node* root, int val) {
    if (!root) return new Node(val);
    if (val < root->val) root->left  = insert(root->left,  val);
    else                 root->right = insert(root->right, val);
    return root;
}

void inorder(Node* root) {
    if (!root) return;
    inorder(root->left);
    std::cout << root->val << " ";
    inorder(root->right);
}

// Returns the depth at which val is found (root = depth 0), or -1.
int findDepth(Node* root, int val, int depth = 0) {
    if (!root) return -1;
    if (root->val == val) return depth;
    if (val < root->val) return findDepth(root->left,  val, depth + 1);
    else                 return findDepth(root->right, val, depth + 1);
}

int main() {
    Node* root = nullptr;
    for (int v : {5, 3, 8, 1, 4, 7, 9}) {
        root = insert(root, v);
    }

    inorder(root);
    std::cout << std::endl;

    std::cout << findDepth(root, 7) << std::endl;
    std::cout << findDepth(root, 6) << std::endl;
    return 0;
}

First draw the BST that results from the insertions. Then write the exact output of the program. For each findDepth call, trace which nodes are visited.

Consider the following program. It runs BFS twice on the same 5-node undirected graph from different starting nodes.

#include <iostream>
#include <vector>
#include <queue>

void bfs(const std::vector<std::vector<int>>& adj, int start) {
    int n = adj.size();
    std::vector<bool> visited(n, false);
    std::queue<int> q;

    visited[start] = true;
    q.push(start);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        std::cout << u << " ";
        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
    std::cout << std::endl;
}

int main() {
    std::vector<std::vector<int>> adj = {
        {1, 2},     // 0 connects to 1, 2
        {0, 3, 4},  // 1 connects to 0, 3, 4
        {0, 4},     // 2 connects to 0, 4
        {1},        // 3 connects to 1
        {1, 2},     // 4 connects to 1, 2
    };

    bfs(adj, 0);
    bfs(adj, 3);
    return 0;
}

Write the exact output produced by this program. For each BFS call, trace the queue state after each dequeue operation.

Debugging

The following function is supposed to detect whether an undirected graph has a cycle using DFS. It contains 3 bugs. For each one:

Identify the line or lines where the bug occurs.
Explain in one or two sentences what goes wrong.
Write the corrected line or lines of code.

#include <iostream>
#include <vector>

bool dfs(const std::vector<std::vector<int>>& adj,
         int u, int parent, std::vector<bool>& visited) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (visited[v]) {
            return true;
        }
        if (dfs(adj, v, u, visited)) {
            return true;
        }
    }
    return false;
}

bool hasCycle(const std::vector<std::vector<int>>& adj) {
    int n = adj.size();
    std::vector<bool> visited(n, false);
    for (int i = 0; i < n; ++i) {
        if (dfs(adj, i, -1, visited)) {
            return true;
        }
    }
    return false;
}

int main() {
    std::cout << std::boolalpha;
    // Linear chain 0-1-2-3 (no cycle)
    std::vector<std::vector<int>> g1 = {{1}, {0, 2}, {1, 3}, {2}};
    // Triangle 0-1-2-0 (has cycle)
    std::vector<std::vector<int>> g2 = {{1, 2}, {0, 2}, {0, 1}};

    std::cout << hasCycle(g1) << std::endl;  // expected: false
    std::cout << hasCycle(g2) << std::endl;  // expected: true
    return 0;
}

The following function is supposed to compute the shortest distances from a source vertex using Dijkstra's algorithm. It contains 3 bugs. For each one:

Name the line or lines where the bug occurs.
Explain in one or two sentences what goes wrong.
Write the corrected line or lines of code.

#include <iostream>
#include <limits>
#include <queue>
#include <vector>

const int INF = std::numeric_limits<int>::max();

// adj[u] = list of {neighbor, edge weight}
std::vector<int> dijkstra(
    const std::vector<std::vector<std::pair<int, int>>>& adj, int src) {
    int n = adj.size();
    std::vector<int> dist(n, 0);

    std::priority_queue<std::pair<int, int>> pq;
    pq.push({0, src});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();

        for (auto& [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

Implementation

Given the following node definition:
struct Node { int val; Node* left; Node* right; Node(int v, Node* l = nullptr, Node* r = nullptr) : val(v), left(l), right(r) {} };
Implement the following function:
int height(Node* root) // height(nullptr) → 0 // height(single node) → 1 // height of BST built from {5, 3, 8, 1, 4, 7} → 3
Returns the height of the binary tree — the number of nodes on the longest root-to-leaf path. An empty tree has height 0.
Given the following function signature:
int numIslands(std::vector<std::vector<char>>& grid) // {{'1','1','0'}, // {'0','1','0'}, // {'0','0','1'}} → 2 // {{'1','1','1'}, // {'0','1','0'}, // {'1','1','1'}} → 1 // {{'0','0','0'}} → 0
Given a 2D grid of '1' (land) and '0' (water), returns the number of islands. An island is a maximal group of '1' cells connected horizontally or vertically. You may modify the grid in-place to mark visited cells.
Given the following function signature:
bool hasCycleDirected(int n, const std::vector<std::vector<int>>& adj) // n=4, adj={{},{0},{0,1},{1}} → false // n=3, adj={{1},{2},{0}} → true (0→1→2→0) // n=1, adj={{}} → false
Returns true if the directed graph with n vertices has a cycle. Use Kahn's algorithm: compute in-degrees, process 0-in-degree vertices with a queue, and check whether the resulting topological order contains all n vertices.

Relevant LeetCode questions

For all these problems, give each one an honest 30-minute attempt. If it's not working out, then ask AI to walk you through the correct framework to solve the problem.

You can expect the problems on the final exam to test the patterns you've learned from solving the problems below.

MTH 4300 Final Exam Practice Questions

Tracing

Debugging

Implementation

Relevant LeetCode questions

Trees

Tries

Graphs

Command Palette

MTH 4300 Final Exam Practice Questions

Tracing

Debugging

Implementation

Relevant LeetCode questions

Trees

Tries

Graphs