Mastering Graph Algorithms and Tries: A Comp251 Final Assignment Guide

Introduction: The Metro Challenge

McGill's COMP 251 final assignment tasks you with building an efficient metro system for the STM. With students complaining about 10-minute cross-campus commutes, your code will determine how many passengers can travel between buildings, which tracks to build, and how to search for passengers quickly. This guide breaks down each objective with clear explanations and practical examples.

Understanding the Data Structures

Disjoint Set with Path Compression and Union by Rank

The provided DisjointSet class uses a naive implementation. To achieve near-constant time operations, you must implement path compression in find and union by size or union by rank in union. This is essential for Kruskal's algorithm in Task 3.3.

// Example: find with path compression
public int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

// Example: union by rank
public void union(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX == rootY) return;
    if (rank[rootX] < rank[rootY]) {
        parent[rootX] = rootY;
    } else if (rank[rootX] > rank[rootY]) {
        parent[rootY] = rootX;
    } else {
        parent[rootY] = rootX;
        rank[rootX]++;
    }
}

Think of this like building a social network: path compression ensures everyone points directly to the group leader, and union by rank keeps the tree shallow.

Task 3.2: maxPassengers – Maximum Flow Between Two Buildings

Given a sparse graph (the metro network), you need to find the maximum number of people that can travel from a start building to an end building. The maximum is the minimum of the start and end building occupants, and the capacity of the connecting track. If no direct track exists, return 0.

Approach: Use a HashMap to store adjacency lists. Since the graph is sparse, an adjacency list is memory-efficient. For each query, check if a direct edge exists; if so, compute the min.

public int maxPassengers(BuildingID start, BuildingID end) {
    Building s = buildingTable.get(start);
    Building e = buildingTable.get(end);
    if (s == null || e == null) return 0;
    Track track = adjacency.get(start).get(end); // assume adjacency map
    if (track == null) return 0;
    return Math.min(s.occupants, Math.min(e.occupants, track.capacity));
}

This is similar to checking the bandwidth of a direct connection between two servers; the weakest link determines throughput.

Task 3.3: bestMetroSystem – Maximum Spanning Tree with Custom Weight

The STM wants a set of tracks connecting all buildings with no cycles, maximizing the “goodness” formula:

goodness = floor( min(start.occupants, end.occupants, track.capacity) / track.cost )

This is a maximum spanning tree problem. Since the graph is connected and undirected, use Kruskal's algorithm with a disjoint set to avoid cycles. Sort edges by goodness descending, then add edges that connect different components.

public List<TrackID> bestMetroSystem() {
    List<Track> edges = new ArrayList<>(Arrays.asList(tracks));
    edges.sort((a, b) -> Integer.compare(goodness(b), goodness(a)));
    DisjointSet ds = new DisjointSet(buildingTable.size());
    List<TrackID> result = new ArrayList<>();
    for (Track t : edges) {
        int u = indexOf(t.startBuilding);
        int v = indexOf(t.endBuilding);
        if (ds.find(u) != ds.find(v)) {
            ds.union(u, v);
            result.add(t.id);
        }
    }
    return result;
}

private int goodness(Track t) {
    int minOcc = Math.min(buildingTable.get(t.startBuilding).occupants,
                          buildingTable.get(t.endBuilding).occupants);
    return Math.min(minOcc, t.capacity) / t.cost;
}

This is like choosing which metro lines to build to maximize passenger throughput per dollar, similar to optimizing a network for a music festival with limited budget.

Task 3.4: Passenger Search with Trie

Implement a trie (prefix tree) to add passengers and search by prefix. The search is case-insensitive, and results should be returned with first letter capitalized and in alphabetical order.

Trie Node Structure

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEnd;
    String fullName; // store the original name at end node
}

addPassenger

public static void addPassenger(String name) {
    String lower = name.toLowerCase();
    TrieNode node = root;
    for (char c : lower.toCharArray()) {
        node = node.children.computeIfAbsent(c, k -> new TrieNode());
    }
    if (!node.isEnd) {
        node.isEnd = true;
        node.fullName = name; // store original for capitalization
    }
}

searchForPassengers

public static List<String> searchForPassengers(String firstLetters) {
    String prefix = firstLetters.toLowerCase();
    TrieNode node = root;
    for (char c : prefix.toCharArray()) {
        if (!node.children.containsKey(c)) return Collections.emptyList();
        node = node.children.get(c);
    }
    List<String> result = new ArrayList<>();
    dfs(node, result);
    Collections.sort(result);
    return result;
}

private static void dfs(TrieNode node, List<String> result) {
    if (node.isEnd) {
        result.add(capitalize(node.fullName));
    }
    for (TrieNode child : node.children.values()) {
        dfs(child, result);
    }
}

private static String capitalize(String name) {
    if (name.isEmpty()) return name;
    return Character.toUpperCase(name.charAt(0)) + name.substring(1).toLowerCase();
}

This trie is like a phone contact list that predicts names as you type, but must handle case-insensitive search and return sorted results.

Testing and Code Review Preparation

You are limited to 50 submissions on Ed, so test locally using the provided template. During the code review, you will need to explain every line and provide time complexities:

• DisjointSet: find and union are nearly O(α(n)) due to path compression and union by rank.
• maxPassengers: O(1) per query using HashMap.
• bestMetroSystem: O(E log E) for sorting + O(E α(V)) for Kruskal's.
• Trie: addPassenger O(k), search O(k + m) where k is prefix length and m is number of results.

Practice explaining your reasoning. For example, why did you choose Kruskal's over Prim's? (Sparse graph, edge list sorting is efficient.)

Final Tips

This assignment mirrors real-world problems: building cost-effective transit, optimizing network flow, and implementing fast search. Trends like AI-driven logistics or gaming matchmaking use similar algorithms. For instance, the maximum spanning tree is used in designing efficient tournament brackets for esports events. The trie powers autocomplete in apps like Spotify or Google Search. By mastering these concepts, you're not just passing Comp251—you're building skills for modern software development.

Good luck, and remember to disable any AI assistants as per the academic integrity policy. Your understanding is what matters.