Graphs

Question 1

(a) Dijkstra pseudocode (6)

Dijkstra(G, s):
  for each v in V: dist[v] = +inf
  dist[s] = 0
  PQ = min-heap of (0, s)
  while PQ not empty:
     (d, u) = PQ.extract_min()
     if d > dist[u]: continue        # stale entry
     for each (u,v,w) in adj[u]:
        if dist[u] + w < dist[v]:
           dist[v] = dist[u] + w
           PQ.insert((dist[v], v))
  return dist

Marks: init +inf & dist[s]=0 (1); heap use (1); extract-min loop (1); stale-entry skip (1); relaxation condition (1); returns dist (1).

(b) Complexity (2): Each edge triggers at most one insert → $O(E)$ inserts, each $O(\log V)$; $V$ extract-mins each $O(\log V)$. Total $O((V+E)\log V)$. (1 for expression, 1 for justification.)

(c) Why fails on negatives (4): Dijkstra assumes once a vertex is extracted with minimum tentative distance, that distance is final — greedy finality. A negative edge later can reduce a distance already "finalized", violating the invariant. Counterexample: vertices $s,a,b$; $s\to a=1$, $s\to b=2$, $b\to a=-2$. Dijkstra extracts $a$ with dist 1 and finalizes it, but true $d(a)=s\to b\to a=2-2=0$. Wrong answer $d(a)=1$ instead of $0$. (2 for explanation of broken invariant, 2 for valid counterexample + wrong value.)

Question 2

(a) Recurrence & V-1 bound (4): Relaxation: $d(v)\leftarrow\min(d(v),\,d(u)+w(u,v))$ for every edge. A shortest path in a graph with no negative cycle is simple, containing at most $V-1$ edges. After iteration $k$, all shortest paths using $\le k$ edges are correct (proof by induction on edge count). Hence $V-1$ iterations relax all. (2 recurrence, 2 induction argument.)

(b) Negative cycle detection (3): Perform one extra ($V$-th) relaxation pass. If any edge can still be relaxed ($d(u)+w<d(v)$), a negative cycle reachable from source exists, since without one all distances would be stable after $V-1$ passes.

(c) Trace (3): From $A$: $d(A)=0$, $d(B)=4$, $d(C)=\min(5,\ 4+(-6))=-2$, $d(D)=\min(4+5,\ -2+3)=\min(9,1)=1$. Final: $d(A)=0,\ d(B)=4,\ d(C)=-2,\ d(D)=1$. (1 for C, 1 for D, 1 for others.)

Question 3

(a) Kahn's algorithm (5):

Kahn(G):
  compute indeg[v] for all v
  Q = queue of all v with indeg[v]==0
  order = []
  while Q not empty:
     u = Q.dequeue(); order.append(u)
     for each (u,v): 
        indeg[v] -= 1
        if indeg[v]==0: Q.enqueue(v)
  if len(order) < V: report CYCLE
  else return order

Marks: indegree compute (1); zero-indegree queue init (1); dequeue+append loop (1); decrement/enqueue (1); cycle check by count (1).

(b) Order (3): One valid order: $5,4,2,3,0,1$. (Also $4,5,0,2,3,1$ etc.) Number of distinct valid topological orders = 8. (2 for a valid order, 1 for count.)

(c) DFS method (2): Run DFS; push each vertex onto a stack when it finishes (post-order); reversed finishing order is a topological order. Finishing times ensure a vertex is placed only after all its descendants, so all its out-edges point to earlier-finishing (later-in-stack) vertices.

Question 4

(a) Kruskal + DSU (7):

find(x):
  if parent[x] != x: parent[x] = find(parent[x])   # path compression
  return parent[x]

union(a,b):
  ra=find(a); rb=find(b)
  if ra==rb: return false
  if rank[ra] < rank[rb]: swap(ra,rb)
  parent[rb] = ra
  if rank[ra]==rank[rb]: rank[ra]+=1
  return true

Kruskal(G):
  for each v: parent[v]=v; rank[v]=0
  sort edges by weight ascending
  mst=[]; total=0
  for (u,v,w) in sorted edges:
     if union(u,v):
        mst.append((u,v,w)); total+=w
  return mst, total

Marks: find w/ compression (1.5); union by rank + tie increment (2); init (1); sort (1); accept-edge-if-union (1); accumulate total (0.5).

(b) Complexity (2): Amortized $O(\alpha(n))$ per operation, effectively near-constant; $\alpha$ is the inverse Ackermann function.

(c) MST trace (3): Sorted: $AB=1, CD=2, AC=3, BC=4, BD=5$.

• $AB(1)$ accept, total=1
• $CD(2)$ accept, total=3
• $AC(3)$ accept, total=6 (connects {A,B} to {C,D})
• $BC(4)$ reject (cycle), $BD$ reject. Edges: $AB, CD, AC$; total weight = 6. (2 correct edges, 1 total.)

Question 5

(a) BFS shortest path (3): BFS explores vertices in nondecreasing order of distance from source, processing all vertices at level $k$ before level $k+1$. Since every edge has unit weight, the first time a vertex is dequeued its distance equals its BFS level = minimum number of edges from source. FIFO queue preserves this layer ordering.

(b) Bipartite BFS test (5):

isBipartite(G):
  color = {} (uncolored)
  for each start s with s uncolored:
     color[s]=0; Q=[s]
     while Q not empty:
        u=Q.pop_front()
        for each neighbor v of u:
           if v uncolored:
              color[v] = 1 - color[u]; Q.push(v)
           elif color[v]==color[u]:
              return false
  return true

Marks: outer loop over components (1); color assignment 1-color[u] (1); conflict check same color (1); BFS queue mechanics (1); returns true otherwise (1).

Question 6

(a) Max-flow min-cut theorem (2): The maximum value of an $s$–$t$ flow equals the minimum capacity of an $s$–$t$ cut.

(b) Edmonds-Karp bound (3): By choosing the shortest augmenting path (fewest edges) via BFS, the BFS distance from $s$ to $t$ is non-decreasing across augmentations, and each edge becomes "critical" (saturated) $O(V)$ times. There are $O(VE)$ augmentations, each BFS costs $O(E)$, giving $O(VE^2)$. Generic Ford-Fulkerson lacks this bound and may not even terminate with irrational capacities.

(c) Max flow (3): Capacities into $t$: $a\to t=2$, $b\to t=3$. Out of $s$: total 5. Push: $s\to a\to t = 2$; $s\to b\to t = 2$; remaining $s\to a$ has $1$ left, route $s\to a\to b\to t=1$. Total = $2+2+1=5$. Check cut $\{s\}$ vs rest: $s\to a + s\to b = 3+2 = 5$. Min-cut capacity 5 = max flow. Max flow = 5, min-cut = edges $\{s\to a, s\to b\}$ (capacity 5). (1 flow value, 1 valid routing, 1 min-cut.)

[
  {"claim":"Bellman-Ford Q2c distances",
   "code":"INF=float('inf')\nedges=[('A','B',4),('A','C',5),('B','C',-6),('C','D',3),('B','D',5)]\nV=['A','B','C','D']\nd={v:INF for v in V}; d['A']=0\nfor _ in range(len(V)-1):\n    for u,v,w in edges:\n        if d[u]+w<d[v]: d[v]=d[u]+w\nresult = (d['A'],d['B'],d['C'],d['D'])==(0,4,-2,1)"},
  {"claim":"Kruskal MST weight Q4c = 6",
   "code":"edges=sorted([('A','B',1),('B','C',4),('A','C',3),('C','D',2),('B','D',5)],key=lambda e:e[2])\nparent={v:v for v in 'ABCD'}\ndef find(x):\n    while parent[x]!=x: parent[x]=parent[parent[x]]; x=parent[x]\n    return x\ntotal=0\nfor u,v,w in edges:\n    ru,rv=find(u),find(v)\n    if ru!=rv: parent[ru]=rv; total+=w\nresult = total==6"},
  {"claim":"Number of topological orders Q3b = 8",
   "code":"from itertools import permutations\nE=[(5,2),(5,0),(4,0),(4,1),(2,3),(3,1)]\nV=[0,1,2,3,4,5]\ncnt=0\nfor p in permutations(V):\n    pos={v:i for i,v in enumerate(p)}\n    if all(pos[a]<pos[b] for a,b in E): cnt+=1\nresult = cnt==8"},
  {"claim":"Max flow Q6c = 5 (equals min s-cut)",
   "code":"cut = 3+2  # s->a + s->b\ninto_t = 2+3\nresult = min(cut,5)==5 and cut==5"}
]