[SOLVED] CS6515 Homework3

Graded Problem

You are given a directed graph $G=(V,E)$ where every vertex has a label $c(v)>0$. Design an algorithm to return, for each vertex $v$, the vertex $w$ of minimum label reachable from $v$. Here, reachable means there is a path from $v$ to $w$. You may assume that $v$ is reachable from itself. Faster (in asymptotic Big O notation) and correct solutions are worth more credit.

Instructions

For the graded problems, you are allowed to use the algorithms from class as black-boxes without further explanation. These include:

• DFS which outputs connected components, topological sort on a DAG. You also have access to the prev, pre, and post arrays.
• BFS on unweighted graphs to find the shortest distance from a source vertex to all other vertices and a path can be recovered backtracking over the prev labels.
• Dijkstra’s algorithm on weighted graphs to find the shortest distance from a source vertex to all other vertices and a path can be recovered backtracking over the prev labels.
• Bellman-Ford and Floyd-Warshall to compute the shortest path when weights are allowed to be negative.
• SCC which outputs the strongly connected components, and the metagraph of strongly connected components.
• Kruskal’s and Prim’s algorithms to find an MST.
• Ford-Fulkerson and Edmonds-Karp to find the max flow on networks.
• 2-SAT which takes a CNF with all clauses of size $\le 2$ and returns a satisfying assignment if it exists.

When using a black-box, make sure you clearly describe which input you are passing into it and how you use the output or take advantage of the data structures created by the algorithm. To receive full credit, your solution must:

• Include the description of your algorithm in words (no pseudocode!).
• Explain the correctness of your design.
• State and analyze the running time of your design (you can cite and use the running time of black-boxes without further explanations).

Unless otherwise indicated, black-box graph algorithms should be used without modification.

Example: I take the input graph $G$, I first find the vertex with largest degree, call it v∗v^*v∗. I take the complement of the graph $G$, call it G′G’G′. Run Dijkstra’s algorithm on G′G’G′ with s=v∗s = v^*s=v∗ and then I get the array dist[v] of the shortest path lengths from $s$ to every other vertex in the graph G′G’G′. I square each of these distances and return this new array.

We don’t want you to go into the details of these algorithms and tinker with it, just use it as a black-box as shown with Dijkstra’s algorithm above.

Context

A graph theory problem is a form of reduction. You are given some problem to solve, and the challenge is to solve that problem by using one of the graph algorithms we study this semester. In other words, you reduce your problem to a graph problem such that a known algorithm can solve it for you.

The known algorithms are treated as a black-box—you are not allowed to change/modify them in any way. You can (and often will) modify the original problem input in some way, or create a graph which represents the input—this becomes the input to the black-box. You then take the results of running the black-box (both its defined output and the data structures it creates during execution) and use those to deduce the solution to the original problem.

Rules

• NO PSEUDOCODE—YOU WILL LOSE A LOT OF POINTS.
• Only black-boxes of known algorithms are allowed.
• One or more graph black-box must be used to solve problems in this section.
• Do not make changes to black-boxes unless explicitly allowed. This is very rare and may not happen during the semester.
• We consider all graphs to be provided as:
  • $G=(V,E)$
  • $V$ is an array of vertices
  • $E$ is an adjacency list
  • When a graph is provided as input, you are also given $n=|V|$ and $m=|E|$.

Components of a complete solution

(a) Describe your algorithm:

• NO PSEUDOCODE—use words.
• What changes you may need for the input.
• What black-box you will feed your input to.
• What changes you may need for the output.
• Repeat with more black-boxes as needed.

(b) Justify why your algorithm is correct:

• Explain how your problem is solved by the black-boxes used.
• Explain how changing the inputs and/or outputs gets what you want.

(c) Analyze the runtime:

• Must be presented in Big O notation.
• Can explain/analyze in words.
• Can use known black-box runtime without explanation. Must include runtime analysis for any pre/post-processing, as well as any modifications to the black-box (if permitted by the problem).
• Again, if we give you a runtime, you must meet that for full credit. If we do not specify a runtime, faster (and correct) in Big O notation are worth more credit.