Graphs

Question 1

What is a graph?

Answer 1

A set of vertices and edges. Each edge connects a pair of verticies

Question 2

What is a path in a graph

Answer 2

A sequences of vertices connected by edges with no repeated edges

Question 3

What is a simple path in a graph?

Answer 3

A path (which is a sequence of vertices connected by edges, with no repeated edges) with no repeated vertices.

Question 4

What is a cycle in a graph?

Answer 4

A path (which is a sequence of vertices connected by edges, where no edge is repeated) with at least one edge. The path’s first and last vertices are the same.

Question 5

What is a simple cycle?

Answer 5

A cycle (which is a path with at least one edge whose first and last vertices are the same, and where a path is a sequence of vertices connected by edges with no repeated edges) with no repeated vertices. Note that the first and last vertices will be the same.

Question 6

What is the length of a cycle or path in a graph?

Answer 6

It is the number of edges in a path (vertices connected by edges with no repeated vertices) or a cycle (path with at least one edge whose first and last vertices are the same).

Question 7

What is a connected graph?

Answer 7

A graph that contains a path (vertices with no rotated edges) between all vertices.

Question 8

Describe a tree in terms of a graph

Answer 8

An acyclic connected graph (or a graph with no cycles and where every vertex has a path to every other vertex)

Question 9

What is a spanning tree of a connected graph?

Answer 9

A connected graph is a graph that contains a path from every vertex, to every other vertex. The spanning tree is a subgraph that contains all the vertices of the connected graph. The subgraph is a tree (acyclic and connected graph)

Question 10

Describe how a depth first search algorithm visits the vertices of a graph

Answer 10

When visiting a vertex

1. Mark it as visited
2. Visit (recursively) all the vertices that are adjacent to it and that have not yet been marked

Question 11

What is the time complexity of DFS when marking all nodes?

Answer 11

The time complexity is proportional to the sum of all vertices degrees.

Question 12

Write a simple DFS algorithm that searches each vertex.

Answer 12

private void dfs(int source) {

marked[source] = true;
count++;
for(int w : adj.get(source))
if (!marked[w]) dfs(w)

Question 13

Name two problems DFS can solve when looking at graphs

Answer 13

Connectivity: are two different vertices connected? How many connected components does a graph have?

Single-source paths: find a path from source vertex to target vertex

Question 14

Write a simple DFS algorithm that finds paths from a source to all vertices

Answer 14

Utilize an array called edgeTo[], where edgeTo[w] = v indicates that v-w edge accesses w first in the path. The array is a parent-link representation of the tree rooted at the source. Said another way v is the parent of w.

Private void dfs(int s) {
marked[v] = true;
for (int w : adj.get(s)) {
if (!marked[w]) {
edgeTo[w] = s;
dfs(w);
}
}
}

Question 15

What is the time complexity of a depth first search algorithm providing a path from a source vertex to a target vertex?

Answer 15

The time complexity is equal to the length of the path.

Question 16

Name one problem breadth first search solves

Answer 16

This algorithm solves the single-source shortest paths problem. This is equivalent to finding the shortest path (path with fewest edges) from source to some vertex.

Question 17

How does breadth first search visit each vertex?

Answer 17

This algorithm visits each graph vertex by:
Remove the next vertex from the queue
Put onto the queue all unmarked vertices that are adjacent to the vertex and mark them as seen.

Question 18

Write a breadth first search algorithm that visits all nodes and records a path from a source to all vertices

Answer 18

Utilize the edge to array to record each vertices parent vertex. Each vertex in the graph is visited first from their parent vertex.

private void bfs(int s) {
Queue<Integer> queue = new Queue<Integer>();
marked[s] = true;
while(!queue.isEmpty()) {
int v = queue.dequeue();
for(int w : adj.get(v)) {
if (!marked[w]) {
edgeTo[w] = v;
marked[w] = true;
queue.enqueue(w);
}
}
}</Integer></Integer>

}

Question 19

Write a breadth first search algorithm that visits all nodes and records a path from a source to all vertices

Answer 19

Utilize the edge to array to record each vertices parent vertex. Each vertex in the graph is visited first from their parent vertex.

private void bfs(int s) {
Queue<Integer> queue = new Queue<Integer>();
marked[s] = true;
while(!queue.isEmpty()) {
int v = queue.dequeue();
for(int w : adj.get(v)) {
if (!marked[w]) {
edgeTo[w] = v;
marked[w] = true;
queue.enqueue(w);
}
}
}</Integer></Integer>

}

Question 20

Which graph algorithm finds the shortest path from source vertex s to all vertices?

Answer 20

The breadth first search algorithm finds these paths within a graph

Question 21

What is the worst case time complexity of breadth first search?

Answer 21

The worst case time complexity of this graph algorithm is Edges+Vertices

Question 22

What is the worst case time complexity of breadth first search?

Answer 22

The worst case time complexity of this graph algorithm is Edges+Vertices

Question 23

How can you modify the depth first search algorithm to determine if two vertices are connected?

Answer 23

Modify the depth first search algorithm by assigning a count or id value to every source vertex passed to the DFS method. The count value is a class instance variable. The DFS method is called for every vertex in the graph that has not been marked (visited) yet. Every time a DFS is called, increase the instance count value. This will ensure that every vertex that is reached by the DFS algorithm will be assigned to the same id value. Therefore, all vertices within the same subgraph will have the same id.

Question 24

How could you modify a simple depth first search algorithm to determine if a graph contains a cycle? Assume the graph has no loops nor any parallel edges.

Answer 24

Modify the depth first search algorithm to check if any adjacent vertices are marked but not the source’s parent vertex. If this is true, set a boolean flag equal to true. When calling the depth first search algorithm, pass the adjacent vertex as the source vertex to examine next, along with the current vertex under investigation as the parent to the source vertex.

Question 25

How could you modify a simple depth first search algorithm to determine if a graph is two-colorable (bipartite)? Said another way, can you assign two colors to every vertex in the graph such that two adjacent vertices don’t have the same color?

Answer 25

Modify the depth first search algorithm to assign a color to all adjacent vertices that are not marked, with the color opposite of the current vertices color. For marked adjacent vertices, check that the color of the current vertex is different from the color of the adjacent vertex. If not, set the boolean flag to false. Return this boolean flag.

Question 26

Compare and contrast the marking strategy of the breadth first search algorithm and the depth first search algorithm.

Answer 26

The breadth first search algorthim must mark

Question 27

What is a directed graph or digraph?

Answer 27

A set of vertices and directed edges. Where each directed edge connects one vertex with another vertex in a particular direction.

Question 28

What is a directed path?

Answer 28

A sequence of vertices in a digraph with each vertex in the sequence contains a directed edge point from it to its successor. There are no repeated edges.

Question 29

What is a simple directed path?

Answer 29

A directed path with no repeated vertices.

Question 30

What is a directed cycle?

Answer 30

A directed path with at least one edge whose first and last vertices are the same

Question 31

What is a simple directed cycle?

Answer 31

A directed cycle with no repeated vertices (except the requisite repetition of the first and last vertices).

Question 32

How does depth first search change when solving the reach ability problem (is there a directed path from some source vertex to a target vertex) for a digraph?

Answer 32

There is no change. Instead, the adjacency list which captures all adjacent vertices for each vertex is no longer symmetric.

Question 33

How does depth first search and breadth first search algorithms change when finding paths in digraphs (compared with undirected graphs)?

Answer 33

There is no change and these methods can solve for single-source directed path (is there a directed path from a source to a target vertex) and single source shortest directed path (if there is a directed path, find the shortest path between source and target vertex).

Question 34

Define what a topological sort is in relation to a digraph

Answer 34

Order vertices such that directed edges point towards vertices that are farther down in the order. If vertex a points towards vertex b, vertex b must come after vertex a. If you displayed the vertices in order, in a line, from left to right. All edges would point towards the right.

Question 35

What is a directed acyclic graph?

Answer 35

A digraph with no directed cycles.

Question 36

What type of problems require no cycles in a digraph in order to solve?

Answer 36

If a schedule is represented by a directed graph, where each job must cannot be completed prior to other jobs, (precedence-constrained scheduling) then the graph cannot have cycles. Essentially, if the graph constrains the order vertices are processed, there cannot be loops because there is no start and no end.

Question 37

If you traverse a graph using depth first search the vertices that are visited are marked. Can you utilize this information to determine if a cycle exists in a graph?

Answer 37

For undirected graphs, this information can be used to detect cycles in a graph. If a vertex is marked, it has a path to all other marked vertices in the graph. Therefore, if the current vertex has a marked adjacent vertex, a path already exists between these two vertices. A second path would introduce a cycle. Note, however, that the parent node (the node used to mark the current node) is connected to the current node through the path that is currently under investigation. Therefore, it cannot be used to detect cycles

Directed graphs can not use this information. While mark vertices are indications that a vertex has been visited, we cannot say which directed path(s) contain this vertex. For a directed cycle to occur, we need a directed path with the last vertex equal to the first vertex. This is why it is important to record the current path’s vertices. If you encounter any of the current path’s vertices again, you have a cycle.

Question 38

Depth first search avoids searching vertices twice by marking them as seen or marked. Does this prevent us from seeing paths that may contain cycles?

Answer 38

No, in the undirected case, encountering an adjacent marked vertex that is not the current vertex’s parent is an indication that the graph has a cycle.

For directed graphs, if the current directed path pursued by the DFS is stopped by a marked vertex, it is impossible for that vertex to contribute to a cycle unless it is in the current call stack. This is because a path is terminated once no more unmarked adjacent vertices are available. If your current vertex was not encountered, it was not apart of this vertex’s path.

Question 39

If a path exists from vertex s to vertex v, does a path exist from v to s?

Answer 39

For undirected graphs, yes. For directed graphs, not necessarily. This is why we have directed paths in directed graphs.

Question 40

Implement directed cycle detection for a digraph. It should record a path containing a cycle if one exists.

Answer 40

Utilize, marked array to record vertices that are visited. Utilize edgeTo array to record each vertice’s parent vertex (the vertex that first visited and marked edgeTo[v] vertex v). Utilize a stack to store the directed path containing the cycle. Utilize the onStack array to record the vertices in the current recursion stack. This is equivalent to the vertices in the current directed path.

Note, to check the entire graph, apply this DFS method to all nodes who are not marked.

private void dfs(int v) {
onStack[v] = true
marked[v] = true
for (int w : adj.get(g)) {
if (cycle != null) return
else if (!marked[w])
{ edgeTo[w] = v; dfs(w); }
else if (onStack[w])
{
cycle = new Stack<>();
for (int x = v; x != w; x = edgeTo[x])
cycle.push(x);
cycle.push(w);
cycle.push(v);
}
onStack[v] = false;
}
}

Question 41

What prevents a graph from having topological order?

Answer 41

A directed cycle or a digraph with loop will not allow for this type of its vertices.

Question 42

What prevents a graph from having topological order?

Answer 42

A directed cycle or a digraph with loop will not allow for this type of its vertices.

Question 43

What is reverse postorder in a depth first search algorithm

Answer 43

An order of vertices in a graph that is equivalent to the topological order of the graph. Vertices are put onto a stack after a recursive call is made.

Question 44

Write an algorthim that returns the vertices in a topologically sorted manner.

Answer 44

Utilize the depth first search algorithm. Capture vertices in reverse post order by saving them to a stack after the recursion call. Note that this algorthim assumes a digraph. Check for cycles prior to using.

private void dfs(int v) {
marked[v] = true;
for (int w : adj.get(v)) {
if (!marked[w]) dfs(w);
}
reversePost.push(v);
}

Question 45

Why does reverse postorder in depth first search produce a topologically sorted list of vertices?

Answer 45

for an edge V->W, when dfs(V) is called, only three scenarios are allowed

dfs(w) has already been called and has returned (w is marked)

dfs(w) has not been called and will be called (w is unmarked). The fire, dfs(w) comes before dfs(v)

dfs(w) has been called but has not returned. This can only happen when a cycle exists (there is another path from v to w).

If there is no cycle, dfs(w) finishes before dfs(v). Reversed post order will place dfs(w) on the stack before dfs(v) causing v to always come before w. This is why confirming that a cycle is not present before dfs based topological sort is important.

Question 46

What does it mean if two vertices are strong connected in a digraph.

Answer 46

The two vertices are mutually reachable. A directed path exists from the first vertex to the second vertex, and from the second vertex to the first vertex.

Question 47

What does it mean for a digraph to be strongly connected?

Answer 47

A graph where all of its vertices are strongly connected to one another

Question 48

What is a strongly connected component?

Answer 48

A subgraph that is strongly connected

Question 49

What is the time complexity of a depth first search based algorithm for determining topological order!

Answer 49

The time complexity is E + V where E is the number of edges and V is the number of vertices.

Question 50

Summarize the steps taken to group vertices in a graph into strongly connected components (Kosaraju-Sharir Algorithm)

Answer 50

Calculate the reverse postorder of the reversed digraph (the original digraph but with its edges reversed) using depth first search

Perform depth first search on the digraph, but check the vertices in the order dictated by the reverse postorder of the reverse digraph

While iterating over the list of vertices whose order is outline by the reverse postorder in the reversed digraph, each vertex will be searched using depth first search if and only if the vertex is unmarked. An unmarked vertex indicates the beginning of a strongly connected component. All vertices visited during the depth first search are in the same strongly connected component.

Question 51

Utilize a modified depth first search algorithm to find connected components of a graph

Answer 51

Connected components apply to undirected graphs. Depth first search will be applied to each vertex of the graph that is unmarked. An unmarked vertex indicates a new component of the graph. Count these components and use the count value as an id for all components in the graph that are in the same component

for (int s = 0; s < V; s++) {
if (!marked[s]) { dfs(s); count++}
}

private void dfs(int v) {
marked[v] = true;
id[v] = count;
for (int w : adj.get(v)) {
dfs(w);
}
}

Question 52

What is the difference between an algorithm finding strongly connected components of a digraph and an algorithm finding connected components of an undirected graph?

Answer 52

Both algorithms check every vertex to determine how many components exist within the the graph. An undirected graph does not care about the order of the vertices while a digraph must search vertices in a specific order (reverse postorder of the reversed digraph). In both cases, encountering an unmarked vertex indicates a new component.

Question 53

Given a subgraph of G called C, and a vertex of G but not in C called v. If there is an edge from any vertex in C pointing to v, how will the reverse postorder of G reversed order v and all vertices in C?

Answer 53

The vertex v will appear before every vertex in C if an edge exists between any vertex in C to v in this list.

Question 54

If we visit each vertex in order dedicated by the reverse postorder of the reversed digraph, why will a depth first search stay contained with the strongly connected component?

Answer 54

Because of the Oder of the vertices, strongly connected components accessible by the current component will already be marked. All other components will be unreachable.

Question 55

What is the time complexity of the Kosaraju-Sharir algorithm (the algorithm that determines the strongly connected components of a graph.

Answer 55

The time complexity is equal to number of edges plus number of vertices.

Question 56

What is a minimum spanning tree of an edge-weighted graph?

Answer 56

A spanning tree whose weight (the sum of the weights of its edges) is no larger the weight of any other spanning tree.

Question 57

What two properties of a tree are fundamental for solving for the minimum spanning tree?

Answer 57

The two properties of trees that are fundamental to this algorithm are

(1) adding an edge to two nodes of a tree introduces a unique cycle

(2) removing an edge from a tree breaks the tree into two trees.

Question 58

What is a cut of a graph?

Answer 58

A partition of the graph vertices into two nonempty, disjoint sets.

Question 59

What is a cut of a graph?

Answer 59

A partition of the graph vertices into two nonempty, disjoint sets.

Question 60

What is a crossing edge of a cut?

Answer 60

An edge that connects a vertex in one set with a vertex in the other.

Question 61

What is the relationship between the crossing edge of a cut and the minimum spanning tree of a weight graph?

Answer 61

The crossing edge of minimum weight is in the minimum spanning tree.

Question 62

Describe Prim’s algorithm in words

Answer 62

The algorithm finds the minimum spanning tree of any connected edge-weight graph by building the MST one edge at time. To determine the next edge, it picks the smallest weigh edge connecting the vertices on the tree with the vertices not on the tree (this is the cross edge of the cut containing the MST). Care should be taken to find the minimum edge efficiently.

Question 63

Implement a lazy version of Prim’s algorithm

Answer 63

Utilize a priority queue to keep track of the minimum weighted edge. Add added as you encounter vertices. If the minimum edge is disallowed because both vertices are marked as being in the MST, remove from the stack.

private boolean[] marked;
private Queue<Edge> mst;
private PriorityQueue<Edge> pq;</Edge></Edge>

public class Edge implements Comparable<Edge>{
int weight;
int v;
int w;</Edge>

public double either(){
return v;
}

public int other (int vertex) {
if (vertex == v) return w;
else return v;
}

public int compareTo(Edge that) {
if (this.weight < that.weight) return -1;
else if (this.weight > that.weight) return 1;
else return 0;
}
}

public void LazyPrimMST() {
pq = new PriorityQueue<>((a,b)->(a.weight -b.weight));
marked = new boolean[V];
mst = new LinkedList<>();

visit(0);
while (!pq.isEmpty()) {
Edge e = pq.poll();
int v = e.either(); int w = e.other(v);
if(marked[v] && marked[w]) continue;
mst.add(e);
if (!marked[v]) visit(v);
if(!marked[w]) visit(w);
}
}

private void visit(int v) {
marked[v] = true;
for (Edge e : adj.get(v)) {
if (!marked[e.other(v)]) pq.insert(e);
}
}

Question 64

What is the time and space complexity of Prim’s algorithm with lazy implementation

Answer 64

The time complexity is E log E (worst case) and space equal to E where E is the number of edges. This is determined by the priority queue.

Question 65

Describe how the eager version of Prim’s algorithm reduces the number of vertices on the queue compared to the lazy version of Prim’s algorithm

Answer 65

The algorithm maintains only one edge per non tree vertex on the priority queue. When visiting a non tree vertex, only the minimum vertex connecting vertex with tree is kept.

This is possible because the minimum crossing edge of min weight must be in the minimum spanning tree. All other edges will be removed evetually.

Question 66

Describe Kruskal’s Algorithm

Answer 66

Sort the edges in ascending order based on their weight values. Add the edges in order so long as it doesn’t introduce a loop. Stop once you have V-1 edges where V is the number of vertices in the tree. The edges constitute the minimum spanning tree of the graph

Question 67

What is the shortest-path tree in an edge weighted digraph?

Answer 67

A subgraph containing the source vertex and all the vertices reachable by the source that forms a directed tree rooted at the source. Every tree path is a shortest path.

Question 68

Name two useful data structures for determining the shortest path in weighted digraphs

Answer 68

Edges on shortest-path tree: use a vertex indexed array to represent parent-edges. The array stores directed edge objects. EdgeTo[v] = is the edge that connects vertex v with the tree

Distance to source: vertex indexed array that stores the shortest path distance from source to the vertex.

Question 69

Describe Edge Relaxation

Answer 69

Let’s say we are investigating an edge from v to w. We want to know if the edge v->w lies on the shortest path from the source vertex s, to the vertex w. Calculate a new shortest distance for w by taking the distance from the current shortest distance from a to v (distTo[v]) and add the weight value for the edge v->w to it. If it’s less than the current minimum distance to w, update it!

Question 70

Describe vertex relaxation.

Answer 70

Relax all edges leaving a given vertex. The relaxation process updates both the distTo data structure and edgeTo data structure for all eligible terminating vertices

Question 71

Describe the shortest path optimality condition

Answer 71

Assume we have a digraph with weighted edges. Select a source vertex s with the goal of determining the shortest weighted distance between s and some vertex v in the graph. If we record path lengths within a vertical indexed array called distTo[v], all values in distTo[v] is equal to the shortest path from s to v if and only if distTo[w] <= distTo[v] + edgeWeight(v,w). Where edgeWeight(v,w) is the edge weight for edge going from v to some connected edge w. For distTo[s], the value is equal to zero. For unreachable vertices, the distTo will equal infinity.

To interpret the results, imagine there is a path from s to w that is larger then the path from s to v plus the edge weight from v to w. This would indicate that the shortest path for w is incorrect.

We now have a way to test the validity of the distTo result of any algorithm.

Question 72

Describe the shortest path optimality condition

Answer 72

Assume we have a digraph with weighted edges. Select a source vertex s with the goal of determining the shortest weighted distance between s and some vertex v in the graph. If we record path lengths within a vertical indexed array called distTo[v], all values in distTo[v] is equal to the shortest path from s to v if and only if distTo[w] <= distTo[v] + edgeWeight(v,w). Where edgeWeight(v,w) is the edge weight for edge going from v to some connected edge w. For distTo[s], the value is equal to zero. For unreachable vertices, the distTo will equal infinity.

To interpret the results, imagine there is a path from s to w that is larger then the path from s to v plus the edge weight from v to w. This would indicate that the shortest path for w is incorrect.

We now have a way to test the validity of the distTo result of any algorithm.

Question 73

Describe Dijkstra’s algorithm in words

Answer 73

The algorithm determines the shortest path from a given source vertex to any reachable vertex in the graph. It utilizes the distTo vertex indexed array to record the shortest path (or really, the best shortest path at this point in time). Set the source vertex distTo to zero and all other vertices to positive infinity. Relax the vertex of the non-tree vertex with the smallest distTo value and add the vertex to the shortest path tree. Continue until all vertices are all on the tree or all non-tree vertices have infinite distance.

Question 74

Implement Dijkstra’s algorithm

Answer 74

Utilize the distTo and edgeTo vertex indexed arrays to track the minimum distance to source and the parent vertex, respectively of each vertex in the graph. The reachable vertices within the edgeTo array correspond to a shortest path tree. Utilize a priority queue pq to relax all candidate vertices next.

public class DijkstraSP {
private DirectedEdge[] edgeTo;
private double[] distTo;
private IndexMinPQ<Double> pq;</Double>

public DijkstraSP(EdgeWeightedDigraph G, int s) {
edgeTo = new DirectedEdge[G.V()];
distTo = new double[G.V()];
pq = new IndexMinPQ<Double> pq;</Double>

for (int v = 0; v < G.V(); v++) {
  distTo[v] = Double.POSITIVE_INFINITY;
}
distTo[s] = 0.0;

pq.inserts(s, 0.0);
while(!pq.isEmpty()) {
  relax(G, pq.delMin()); //                                                                         
}   private void relax(EdgeWeightedDigraph G, int v) {
for (DirectedEdge e : G.adj(v)) {
  int w = e.to();
  if (distTo[w] > distTo[v] + e.weight()){
    distTo[w] = distTo[v] + e.weight();
    edgeTo[w] = e;
    if (pq.contains(w)) pq.changeKey(w, distTo[w]);
    else pq.insert(w, distTo[w]);
  }
}   }   } }

Question 75

What is the time and space complexity of the Dijkstra’s algorithm

Answer 75

The space complexity is O(V) and the time complexity is O(E log V) (worst case) where V is the number of vertices and E is the number of edges of the graph.

Question 76

Compare Prim’s algorithm with Dijkstra’s algorithm

Answer 76

Both algorithms build a tree by adding one edge and one vertex to the tree at a time. One is utilized for undirected weight graphs while the other is used for weighted digraphs. The undirected algorithm builds the tree by adding the vertex closest to the tree, while the directed graph builds the tree by finding the vertex closest to the source. In the undirected graph, a marked array is needed. In the directed graph the distTo not being infinity is equivalent to a marked vertex.

Question 78

Compare the Dijkstra algorithm with a shortest path algorithm that utilizes the graph’s topological order.

Answer 78

1. The topological sort based algorithm solves for the shortest path in linear time (E + V) as opposed to E log V
2. The topological sort based approach can handle negative weights while Dijkstra requires nonnegative weights
3. The topological sort based algorithm can find longest path

Question 79

Describe an algorithm that utilizes topological order to find the shortest path in an edge weighted acyclic digraph

Answer 79

Relax vertices in topological order. The distance to source is set to zero while to all others it’s set to infinity.

Question 80

Implement a shortest path algorithm for an acyclic digraph with weighted edges using topological sort

Answer 80

public class AcyclicSP {
private DirectedEdge[] edgeTo;
private double[] distTo;

public AcyclicSP(EdgeWeightedDigraph G, int s) {
edgeTo = new DirectedEdge[G.V()];
distTo = new double[G.V()];

for(int v = 0; v < G.V(); v++) {
  distTo[v] = Double.POSITIVE_INFINITY;
}
distTo[s] = 0.0;

Topological top = new Topological(G);

for(int v: top.order()) relax(G, v);   }

private void relax(EdgeWeightedDigraph G, int v) {
for(DirectedEdge e : G.adj(v)) {
int w = e.to();
if (distTo[w] > distTo[v] + e.weight()) {
distTo[w] = distTo[v] + e.weight();
edgeTo[w] = e;
}
}
}
}

Question 81

Describe how to modify a topological sort based shortest path algorithm for acyclic digraphs with weighted edges to produce the longest path

Answer 81

Negate the weights of the graph and determine the shortest path. Note that negative weight values are allowed in this algorithm.

Question 82

Describe parallel precedence-constrained scheduling

Answer 82

This is a scheduling algorithm where you assume you have infinite workers to handle jobs with a specified duration. The jobs are constrained by precedence. Said another way, some jobs come before other jobs. The jobs may be performed in parallel but must adhere to the precedence constraint. The scheduling algorithm aims to find a schedule with the minimum total time.

Question 84

Describe the parallel precedence-constrained scheduling problem

Answer 84

Let’s say we have jobs that each take a certain amount of time. They are constrained by precedence or some must occur before others. How quickly can we complete all jobs assuming we can do as many jobs as we want at once?

Question 85

How do you solve for the critical path of a parallel precedence-constrained scheduling problem?

Answer 85

Represent the problem using an acyclic digraph. Each job is represented by two nodes connected by a weighted edge whose value equal’s the job’s duration. Jobs that depend on one another are connected with edges equal to zero weight. Add a source vertex and a sink vertex. The source vertex is connected to every job’s start node. The sink to every job’s end node. All edges are zero-weight. It then calculates the longest path in the graph and returns the total time.

Question 86

Give the time complexity of the critical path method used to solve parallel precedence-constrained scheduling.

Answer 86

The time complexity is linear or E + V

Question 87

What is parallel job scheduling with relative deadlines?

Answer 87

This is a job scheduling problem that contains precedence constrains and deadline constraints. To meet the deadline constraint, jobs must begin with in a certain amount of time relative to the start time of another job.

Question 88

How do you solve the parallel job scheduling with relative deadlines problem?

Answer 88

Each job is represented by a start and end node. The weight of the edge connecting each node is weighted to equal the job’s duration. The start node points to each start node and the sync node points to each node node. These edges are zero weighted. Precedence is also captured by zero weighted edges.

If a job with terminations node v has to start within d time units after a job with starting node w, make an edge from v to w with negative weight equal to -d. Negate all weights and solve for the shortest path. This only works if the schedule is feasible.