Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CS 163/265--Graph Algorithms Homework 3
Due: Friday, April 28, 11:45pm
Please answer the following questions, each of which is worth 10 points.
1. (CS 163 students only) Using the graph at the following website, number each vertex according to a topological ordering. http://www.cs.unc.edu/~stotts/145/homes/qualsched/pert_chart.jpg
2. (CS 163 students only) Using the graph at the following website, darken in each edge of the shortest path tree from the node, A.
https://i.stack.imgur.com/kJF5K.png
For each other vertex, v, in this graph, show the values of the label, D[v], as it would be set during Dijkstra’s algorithm (starting with +∞), and going through each update to each such label until it has its final value.
3. Suppose you are given a connected weighted undirected graph, G, with n vertices and m edges, such that the weight of each edge in G is an integer in the interval [1, c], for a fixed constant c > 0. Show how to solve the single-source shortest-paths problem, for any given vertex v, in G, in time O(n + m).
4. In a side-scrolling video game, a character moves through an environment from, say, left-to-right, while encountering obstacles, attackers, and prizes. The goal is to avoid or destroy the obstacles, defeat or avoid the attackers, and collect as many prizes as possible while moving from a starting position to an ending position. We can model such a game with a graph, G, where each vertex is a game position, given as an (x, y) point in the plane, and two such vertices, v and w, are connected by an edge, given as a straight line segment, if there is a single movement that connects v and w. Furthermore, we can define the cost, c(e), of an edge to be a combination of the time, health points, prizes, etc., that it costs our character to move along the edge e (where earning a prize on this edge would be modeled as a negative term in this cost). A path, P, in G is monotone if traversing P involves a continuous sequence of left-to-right movements, with no right-to-left moves. Thus, we can model an optimal solution to such a sidescrolling computer game in terms of finding a minimum-cost monotone path in the graph, G, that represents this game. Describe and analyze an efficient algorithm for finding a minimum-cost monotone path in such a graph, G.
5. Suppose that CONTROL, a secret U.S. government counterintelligence agency based in Washington, D.C., has build a communication network that links n stations spread across the world using m communication channels between pairs of stations (i.e., edges). Suppose further that the evil spy agency, KAOS, is able to eavesdrop on some number, k, of these channels and that CONTROL knows the k channels that have been compromised. Now, CONTROL has a message, M, that it wants to send from its headquarters station, s, to one of its field stations, t. The problem is that the message is super secret and should traverse a path that minimizes the number of compromised edges that occur along this path. Explain how to model this problem as a shortest-path problem, and describe and analyze an efficient algorithm to solve it.
6. (CS 265 students only) Show that it is possible to count the total number of paths from a source vertex, s, to a sink vertex, t, in a directed acyclic graph, G, with n vertices and m edges using O(n + m) additions. Also, show that there is a graph, G, where this number is at least 2n/2 .
7. (CS 265 students only) Design an efficient algorithm for finding a longest directed path from a vertex s to a vertex t of a directed acyclic weighted graph, G. Specify the graph representation used and any auxiliary data structures used. Also, analyze the time complexity of your algorithm.