Exam2-Algorithms

Question 1

Depth First Search
- Input
- Output
- Arrays available to access
- Graph types applicable
- Runtime

Answer 1

• Input
  
  • G=(V,E)
• Output
  
  • topological sort on a DAG
• Arrays available
  
  • prev, visited
  • pre, post on DIRECTED graphs
  • ccnum on UNDIRECTED GRAPHS
• Graph types
  
  • Unweighted
  • Undirected and Directed
• Runtime
  
  • O(n+m)

Question 2

Explore
- Input
- Output
- Arrays available to access
- Graph types applicable
- Runtime

Answer 2

• Input
  
  • G=(V,E)
  • Start vertex v in V
• Output
  
  • visited[], which is set to True for all vertices reachable from v
• Arrays available
  
  • ccnum[]
  • visited[]
• Graph types
  
  • Unweighted
  • Undirected and Directed
• Runtime
  
  • O(n+m)

Question 3

Breadth First Search
- Input
- Output
- Arrays available to access
- Graph types applicable
- Runtime

Answer 3

• Input
  
  • G=(V,E)
  • Start vertex v in V
• Output
  
  • dist[]
    
    • For all vertices u reachable from v, dist[u] is the shortest path distance from v to u. If no such path, infinity.
• Arrays available
  
  • prev[]
    
    • This provides the immediate parent vertex of a vertex. If there is no immediate parent, the array has Null/0.
• Graph types
  
  • Unweighted
  • Undirected and Directed
• Runtime
  
  • O(n+m)

Question 4

Dijkstra’s
- Input
- Output
- Arrays available to access
- Graph types applicable
- Runtime

Answer 4

• Input
  
  • G=(V,E)
  • Start vertex v in V
• Output
  
  • dist[]
    
    • For all vertices u reachable from v, dist[u] is the shortest path distance from v to u. If no such path, infinity.
• Arrays available
  
  • prev[]
    
    • This provides the immediate parent vertex of a vertex. If there is no immediate parent, the array has Null/0.
• Graph types
  
  • Weighted
  • Undirected and Directed
  • No negative weights
• Runtime
  
  • O((n+m)log n)
  • O((m log n) if the graph is strongly connected

Question 5

Bellman-Ford
- Input
- Output
- Arrays available to access
- Graph types applicable
- Runtime

Answer 5

Bellman-Ford is used to derive the shortest path from s to t using only a single vertex s.

• Input
  
  • G=(V,E)
  • Start vertex s
• Output
  
  • Shortest path from s to all other vertices
• Arrays available
  
  • Detect negative weight cycles
• Graph types
  
  • Weighted
  • Undirected and Directed
  • Can negative weights
• Runtime
  
  • O(nm)

Question 6

Floyd-Warshall
- Input
- Output
- Arrays available to access
- Graph types applicable
- Runtime

Answer 6

FW is primarily used to find the shortest path from ALL nodes to all other nodes where negative weights are allowed.

• Input
  
  • G=(V,E)
• Output
  
  • Shortest path from all vertices to all other vertices
• Arrays available
  
  • We can detect negative weight cycles by checking the diagonals (T[n, i, i])
• Graph types
  
  • Weighted
  • Undirected and Directed
  • Can negative weights
• Runtime
  
  • O(n^3)

Question 7

Strongly-Connected Components
- Input
- Output
- Arrays available to access
- Graph types applicable
- Runtime

Answer 7

• Input
  
  • G=(V,E)
• Output
  
  • meta-graph (DAG) that contains the connected components, represented as an adjacency list
  • Topological sorting of the meta-graph
    
    • With a source SCC first and a sink SCC last
• Arrays available
  
  • adjacency list of meta graph in topological order
  • ccnum
• Graph types
  
  • Directed
• Runtime
  
  • O(n+m)

Question 8

Kruskal’s
- Input
- Output
- Graph types applicable
- Runtime

Answer 8

Kruskal’s algorithm is used to find a minimum spanning tree of a connected, undirected graph. The strategy here is all edge weights are sorted, and the algorithm chooses the lowest edge weight to process.

• Input
  
  • G(V,E) - connected, undirected
• Output
  
  • MST
• Graph types applicable
  
  • connected, undirected, weighted
• Runtime
  
  • O(m log n)

Question 9

Prim’s
- Input
- Output
- Graph types applicable
- Runtime

Answer 9

Prim’s algorithm is used to find a minimum spanning tree of a connected, undirected graph. The strategy here is a start vertex is chosen, and then Dijkstra’s is used to choose the lowest weight, unvisited neighbors for exploration.

• Input
  
  • G(V,E) - connected, undirected
• Output
  
  • MST
• Graph types applicable
  
  • connected, undirected, weighted
• Runtime
  
  • O(m log n)

Question 10

Ford Fulkerson
- Input
- Output
- Arrays available
- Graph types applicable
- Runtime

Answer 10

A greedy algorithm to find max flow on networks. The algorithm continually sends flow along paths from the source (starting node) to the sink (end node), provided there is available capacity on all edges involved. This flow continues until no further augmenting paths with available capacity are detected.

• Input
  
  • G = (V, E)
  • Flow capacity c
  • Source node s
  • Sink node t
• Output:
  
  • Max flow
• Arrays available
  
  • Residual network G_r
  • Max flow of G
• Graph types applicable
  
  • Directed, weighted
• Runtime
  
  • O(C * m)
  • C is the maximum flow in the network
  • m is the number of edges

Question 11

Edmonds Karp
- Input
- Output
- Arrays available
- Graph types applicable
- Runtime

Answer 11

The Edmonds-Karp algorithm is utilized to determine the maximum flow in a network. This is analogous to the Ford-Fulkerson method but with one distinct difference: the order of search for finding an augmenting path must involve the shortest path with available capacity (BFS for G where all edge weights equal 1).

• Input
  
  • G = (V, E)
  • Flow capacity c
  • Source node s
  • Sink node t
• Output:
  
  • Max flow
• Arrays available
  
  • Residual network G_r
  • Max flow of G
• Graph types applicable
  
  • Directed, weighted
• Runtime
  
  • O(nm^2)

Question 12

RSA Procedure

Answer 12

1. Choose primes p and q. Let N = pq
2. Find e where gcd(e, (p-1)(q-1)) = 1
   
   • (p-1)(q-1) is used because of Fermat’s Little Theorem z^((p-1)(q-1)) === 1 mod N
   • e is part of the public key used to encrypt
3. Let d === e^-1 mod (p-1)(q-1)
   
   • Use Extended Euclid to find d
   • This is the private key used to decrypt
4. Publish public key (N,e)
5. Encrypt message m: y === m^e mod N
6. Decrypt y: m = y^e mod N

Question 13

If graph G has more than |V| − 1 edges, and there is a unique heaviest edge, then this edge cannot be part of a minimum spanning tree.

Answer 13

False. Consider a graph with two connected components and the heaviest edge is the only one connecting them.

Question 14

If G has a cycle with a unique heaviest edge e, then e cannot be part of any MST.

Answer 14

True. Consider the order in which edges would be processed by Kruskal’s.

Question 15

Let e be any edge of minimum weight in G. Then e must be part of some MST.

Answer 15

True. e will belong to some MST if running Kruskal’s.

Question 16

If the lightest edge in a graph is unique, then it must be part of every MST.

Answer 16

True. The cut property assures that it is safe to select the lightest edge across any cut.

Question 17

If e is part of some MST of G , then it must be a lightest edge across some cut of G.

Answer 17

True. Suppose there are vertices u and v and e is the edge that connects them.

Question 18

If G has a cycle with a unique lightest edge e, then e must be part of every MST.

Answer 18

False. Consider:

   1     1
A---B---C
|   / \    |  1 | /4 5\ | 1
|/   6   \|
D--------E

Question 19

The shortest-path tree computed by Dijkstra’s algorithm is necessarily an MST.

Answer 19

False. Consider:

  6    A---B 3 |    | 1    C---D
  3

Start Dijkstra’s from node A. It will find this as the shortest path:

  6    A---B 3 |    C---D
  3

However the MST is:

A B
3 | | 1
C—D
3

Question 20

The shortest path between two nodes is necessarily part of some MST.

Answer 20

False. Consider:

   v
  / \ 11/    \2    /       \ u--------w
 10

The shortest path between u and v is the single edge (u,v), but the MST would be (u,w) and (w,v).

Question 21

Prim’s algorithm works correctly when there are negative edges.

Answer 21

True

Question 22

Let G = (V,E) be a directed acyclic graph (DAG) with exactly one sink vertex v. True or False: There is a path from every vertex u to the sink vertex v.

Answer 22

True

In a directed acyclic graph (DAG), there can be only one sink vertex, which is a vertex with no outgoing edges. Since there are no cycles in the graph, there is a clear direction from every vertex to the sink vertex. Therefore, there exists at least one path from every vertex u to the sink vertex v.

Question 23

Let G = (V, E) be a directed graph with exactly one sink component. True or False: The reversed graph has exactly one source component.

Answer 23

True. Here’s the explanation:

Sink Component Definition: A sink component in a directed graph is a set of vertices where all directed paths end at a specific sink vertex. No outgoing edges exist from this specific sink vertex within the component.

Reversing Edges: When we reverse the edges of a directed graph, the direction of all paths is also reversed. This means:

Any sink vertex in the original graph becomes a source vertex in the reversed graph (no incoming edges).
Any source vertex in the original graph becomes a sink vertex in the reversed graph (no outgoing edges).
Uniqueness of Sink Component: Since the original graph has only one sink component, all vertices within that component ultimately reach the same unique sink vertex.

Reversal Impact: When we reverse the edges, all these vertices will have outgoing edges (previously incoming) towards the original sink, which becomes the source in the reversed graph. Thus, all vertices from the original sink component become a single source component in the reversed graph.

Therefore, if a directed graph has exactly one sink component, reversing its edges will result in the reversed graph having exactly one source component.