Algorithm Design and Analysis

This is the graduate core algorithms class: formal design and analysis of algorithms (graphs, greedy, divide-and-conquer, DP, flows, FFT & segment trees, randomized algorithms, NP-completeness, and a bit of geometry), with a strong emphasis on proofs and actual implementations.

The class also had us complete 20 hard LeetCode problems and complete a problem generally thought to be an NP-hard problem.

Project: Graph Isomorphism Heuristic

For the Graph Isomorphism part, we were given two undirected graphs $G$ and $G^{'}$ on the same vertex set and asked to output a permutation $f$ so that as many edges as possible "line up":

x = \frac{# {(u, v) \in E : (f (u), f (v)) \in E^{'}}}{m}

The score was a cubic function of $x$ .

The rough pipeline:

1. Weisfeiler-Lehman (WL) refinement

Color vertices by degree, then iteratively refine based on neighbor colors in both graphs, so structurally similar vertices share a color:

for (int v = 1; v <= n; v++) {
    vector<int> sig;
    sig.push_back(color[v]);        // own color
    for (int u : adj[v]) sig.push_back(color[u]);
    sort(sig.begin() + 1, sig.end());
    newColor[v] = get_or_create_id(sig);
}
color.swap(newColor);

2. Seed matching from unique colors

Any color that appears exactly once in each graph gives a very likely match $u \mapsto v$ . Those become seeds.

3. Seed-and-extend + greedy fill

Prefer unmapped vertices with many already-mapped neighbors.
Within a color class, pick candidates in $G^{'}$ that preserve those edges.
Finally, greedily pair whatever remains inside each color class.

4. Local improvement by swapping images

Repeatedly pick two vertices of the same WL color, hypothetically swap their images, and keep the swap if it increases the number of matched edges. Only edges touching those two vertices need to be rechecked:

long long delta = 0;
for (auto [u, v] : incident_edges_of(a, b)) {
    bool oldMatch = edge2.count(enc(f[u], f[v]));
    int fu_new = (u == a ? f[b] : (u == b ? f[a] : f[u]));
    int fv_new = (v == a ? f[b] : (v == b ? f[a] : f[v]));
    bool newMatch = edge2.count(enc(fu_new, fv_new));
    delta += (newMatch - oldMatch);
}
if (delta > 0) swap(f[a], f[b]);

5. Small-class refinement with Hungarian

For small WL color classes where the images form a clean 1–1 set, I build a tiny weight matrix (“how many edges would match if i→j?”) and run the Hungarian algorithm to optimally reassign within that class.

The result is not a formal GI solver, but a pretty robust data-dependent heuristic that does well on the course’s instance and nicely ties together graph theory, combinatorial optimization, and local search. This scores a 3.95, which is approximately 96% correct on the provided test instance.