final

Question 1

spanning tree

Answer 1

A subset of edges of a graph that connects all the vertices without forming a cycle

Question 2

MST

Answer 2

a spanning tree with the smallest possible total edge weight

Question 3

Generic-MST Algorithm

Answer 3

An algorithm for finding a minimum spanning tree by adding safe edges iteratively

Question 4

safe edge

Answer 4

An edge that can be added to the current tree without violating its properties as part of an MST

Question 5

cut

Answer 5

a partition of the vertices of a graph into two disjoint subsets

Question 6

light edge

Answer 6

the smallest weight edge crossing a given cut

Question 7

edge replacement

Answer 7

The process of adding and removing edges to maintain a spanning tree structure

Question 8

Prim’s Algorithm

Answer 8

A greedy algorithm that grows an MST starting from an arbitrary vertex

Question 9

Kruskal’s Algorithm

Answer 9

A greedy algorithm that builds an MST by sorting edges and adding them while avoiding cycles

Question 10

Union-Find Data Structure

Answer 10

A data structure that efficiently supports union and find operations for disjoint sets

Question 11

Single-Source Shortest Path (SSSP)

Answer 11

The problem of finding the shortest paths from a single source vertex to all other vertices

Question 12

relaxation

Answer 12

The process of updating an estimate of the shortest path in shortest-path algorithms

Question 13

Dijkstra’s Algorithm

Answer 13

An algorithm for solving the SSSP problem on graphs with non-negative weights

Question 14

Fibonacci Heaps

Answer 14

A data structure used to improve the running time of algorithms like Prim’s and Dijkstra’s

Question 15

Flow Network

Answer 15

A directed graph with a capacity assigned to each edge, used to model flow problems

Question 16

(s, t)-Flow

Answer 16

A function that represents the flow of material from source s to sink t under capacity and conservation constraints

Question 17

Feasible Flow

Answer 17

A flow that satisfies capacity constraints

Question 18

residual graph

Answer 18

A graph showing remaining capacities and possible reverse flows after some flow has been pushed

Question 19

Max-Flow Min-Cut Theorem

Answer 19

States that the maximum value of an (s, t)-flow equals the capacity of the minimum (s, t)-cut

Question 20

Augmenting Path

Answer 20

A path in the residual graph where additional flow can be pushed from s to t

Question 21

Ford-Fulkerson Algorithm

Answer 21

A method to compute the maximum flow in a flow network by iteratively augmenting flow
along paths in the residual graph

Question 22

Edmonds-Karp Algorithm #1

Answer 22

An implementation of Ford-Fulkerson that selects the widest augmenting path (the one with the largest bottleneck value)

Question 23

Edmonds-Karp Algorithm #2

Answer 23

An implementation of Ford-Fulkerson that selects the shortest augmenting path in terms of edges (the smallest number of edges)

Question 24

Bipartite Graph

Answer 24

A graph whose vertex set can be divided into two disjoint sets such that every edge connects a vertex from one set to the other

Question 25

Matching

Answer 25

A subset of edges in a graph such that no two edges share a vertex

Question 26

Maximum Matching

Answer 26

A matching that contains the largest possible number of edges

Question 27

Tractability

Answer 27

A problem is considered tractable if it can be solved in polynomial time, making it reasonably solvable

Question 28

Hamiltonian Cycle

Answer 28

A simple cycle in a graph that visits every vertex exactly once

Question 29

Hamiltonian Cycle Problem

Answer 29

The decision problem of determining whether a graph contains a Hamiltonian cycle

Question 30

Decision Problem

Answer 30

A problem with a yes/no answer, such as ”Does the graph have a flow of value k?”

Question 31

Search/Optimization Problem

Answer 31

A problem where the goal is to find the best solution, such as ”What is the maximum flow value?”

Question 32

Reduction

Answer 32

The process of transforming one problem into another in polynomial time to compare their hardness.

Question 33

NP

Answer 33

Nondeterministic Polynomial-Time The class of problems that can be guessed and verified in polynomial time

Question 34

NP-Complete

Answer 34

A problem that is in NP and is as hard as every other problem in NP

Question 35

Boolean Satisfiability Problem (SAT)

Answer 35

The decision problem of determining whether there exists an assignment of Boolean values to variables that satisfies a given CNF formula

Question 36

P = NP

Answer 36

A major unsolved question in computer science, asking whether every problem in NP can be solved in polynomial time

Question 37

Traveling Salesman Problem (TSP)

Answer 37

The problem of finding the shortest possible route that visits each city exactly once and returns to the starting city

Question 38

Approximation Algorithm

Answer 38

An algorithm that provides a solution within a provable factor α of the optimal solution ALG / OPT < α

Question 39

Randomized Algorithm

Answer 39

An algorithm that uses randomness and may provide correct solutions with high probability or run in polynomial time with high probability.

Question 40

respects (cut)

Answer 40

A cut (S, S ̄) respects A ⊆ E if no edge in A crosses (S, S ̄)

Question 41

sparse graph

Answer 41

O(n)

Question 42

dense graph

Answer 42

O(n^2)