Data Structures & Algorithms Graphs & Advanced Structures Flashcards

24 sample cards from the Graphs & Advanced Structures deck

Sampled from the end of the deck, so these are different cards from the ones shown on the syllabus page.

1. What is the A* search algorithm and its evaluation function?

   A* is a best-first shortest-path search using $$f(n) = g(n) + h(n),$$ where $g(n)$ is the known cost from the start and $h(n)$ is a heuristic estimate of the cost to the goal.

2. What condition on the heuristic $h$ guarantees A* finds an optimal path?

   $h$ must be admissible: it never overestimates the true cost to the goal, i.e., $h(n) \leq h^{*}(n)$. Consistency (monotonicity) is a stronger sufficient condition.

3. Define a consistent (monotone) heuristic for A*.

   For every edge $(n, n')$ with cost $c$: $$h(n) \leq c(n, n') + h(n').$$ Consistency implies admissibility and guarantees each node is expanded at most once.

4. How does A* relate to Dijkstra's algorithm?

   A* with the zero heuristic $h(n) = 0$ reduces exactly to Dijkstra's algorithm. A good heuristic focuses the search toward the goal, expanding fewer nodes.

5. Define a minimum spanning tree (MST).

   A spanning tree (connected, acyclic subgraph including all $V$ vertices) of a weighted undirected graph whose total edge weight is minimum.

6. Describe Kruskal's algorithm and its complexity.

   Sort all edges by weight ascending; add each edge if it connects two different components (checked via Union-Find), skipping edges that form cycles. Runs in $O(E \log E) = O(E \log V)$.

7. Describe Prim's algorithm and its complexity with a binary heap.

   Grow the MST from a start vertex, repeatedly adding the minimum-weight edge crossing from the tree to a new vertex, using a priority queue. Time $O(E \log V)$ with a binary heap; $O(E + V\log V)$ with a Fibonacci heap.

8. State the cut property for MSTs.

   For any cut (partition of vertices), the minimum-weight edge crossing the cut belongs to some MST. This justifies the greedy choices in both Prim's and Kruskal's algorithms.

9. State the cycle property for MSTs.

   For any cycle, the maximum-weight edge on that cycle is not in any MST (assuming unique weights). Kruskal's algorithm implicitly discards such edges.

10. What two operations does a Union-Find (Disjoint Set Union) structure support?

    $\text{Find}(x)$: return the representative of $x$'s set. $\text{Union}(x, y)$: merge the sets containing $x$ and $y$.

11. Name the two optimizations for Union-Find and state the resulting amortized complexity.

    Union by rank/size and path compression. Together they give nearly constant amortized time $O(\alpha(n))$ per operation, where $\alpha$ is the inverse Ackermann function.

12. How does path compression work in Union-Find?

    During a $\text{Find}$ operation, every node visited on the path to the root is re-pointed directly to the root, flattening the tree for future queries.

13. How does union by rank/size work?

    When merging two trees, attach the root of the shorter/smaller tree under the root of the taller/larger one, keeping trees shallow and bounding height at $O(\log n)$.

14. Define a strongly connected component (SCC) of a directed graph.

    A maximal set of vertices such that every vertex is reachable from every other vertex in the set via directed paths.

15. Name two linear-time algorithms for finding SCCs and their complexity.

    Kosaraju's algorithm (two DFS passes, using the transpose graph) and Tarjan's algorithm (single DFS with low-link values). Both run in $O(V + E)$.

16. Outline Kosaraju's algorithm for SCCs.

    1) Run DFS on $G$, pushing vertices onto a stack by finish time. 2) Compute the transpose $G^{T}$. 3) Pop vertices in decreasing finish order and run DFS on $G^{T}$; each DFS tree is one SCC.

17. Define an articulation point (cut vertex) in an undirected graph.

    A vertex whose removal (with its incident edges) increases the number of connected components—i.e., it disconnects part of the graph.

18. Define a bridge in an undirected graph.

    An edge whose removal increases the number of connected components. Bridges belong to no cycle.

19. How are articulation points and bridges found efficiently, and what is the key quantity used?

    By a single DFS in $O(V + E)$ using discovery times $\text{disc}[u]$ and low-link values $\text{low}[u]$ (the earliest reachable ancestor). An edge $(u,v)$ is a bridge if $\text{low}[v] > \text{disc}[u]$; a non-root $u$ is an articulation point if some child $v$ has $\text{low}[v] \geq \text{disc}[u]$.

20. In a flow network, what is a flow and what constraints must it satisfy?

    A flow $f(u,v)$ on edges must satisfy the capacity constraint $0 \leq f(u,v) \leq c(u,v)$ and flow conservation: at every non-source, non-sink vertex, total inflow equals total outflow.

21. State the Max-Flow Min-Cut Theorem.

    In a flow network, the maximum value of an $s$-$t$ flow equals the minimum capacity of an $s$-$t$ cut: $$\max_{f} |f| = \min_{(S,T)} c(S, T).$$

22. What is an augmenting path, and which algorithm uses them to compute max flow?

    An augmenting path is a source-to-sink path in the residual graph with spare capacity on every edge. The Ford-Fulkerson method repeatedly augments along such paths until none remain.

23. What is the Edmonds-Karp algorithm and its time complexity?

    An implementation of Ford-Fulkerson that finds augmenting paths via BFS (shortest augmenting path first). It runs in $O(V E^{2})$.

24. Compare Dijkstra, Bellman-Ford, and Floyd-Warshall by scope, weight support, and complexity.

    Dijkstra: single-source, non-negative weights, $O((V+E)\log V)$. Bellman-Ford: single-source, allows negative weights (detects negative cycles), $O(VE)$. Floyd-Warshall: all-pairs, allows negative weights, $O(V^{3})$.

What this deck covers

Graphs & Advanced Structures flashcards FAQ