Algo Hw 02 - Algo Hw 2 PDF

Preview

Summary

Algo Hw 2...

Description

ALGO Spring 2019

Section 07

HW02 solution

Problem 1: DPV Problem 3.8.) a. and b. Three container whose sizes are 10 pints, 7 pints, and 4 pints. The 7 pint and 4 pint containers start out full of water, but the 10 pint container is initally empty. We are allowed one type of operation that pour the contents of one container to another, stopping only when source container is empty or destination container is full. We want to know if there is a sequence of pouring that leaves exactly 2 pints in the 7 or 4 pint container. a.) Model this as a graph problem: give a precise definition of the graph involved and state the specific question about this graph that needs to be answered. Let G(V,E) be the directed graph. The nodes will be triples of numbers (a0 , a1 , a2 ). Let the sizes of the containers be S0 = 10, S1 = 7, S2 = 4. ai will represent the amount of pints in the container. For any given node, it must hold 0 ≤ ai ≤ Si . and a0 + a1 + a2 = 11 (total initial amount of water.) An edge between two nodes (a0 , a1 , a2 ) and (b0 , b1 , b2 ) exists if the two nodes differ in exactly two coordinates and if i and j are the coordinates they differ in, then either ai = 0 or aj = 0 or ai = Si or aj = Sj . The question that needs to be answered is if there exists a path between the nodes (0,7,4) and (*,2,*) or (*,*,2) where * is any allowed value for the coordinate. b.) What algorithm should be applied to solve the problem? Given the above description, A DFS algorithm can be applied that returns true if the desired node is reached and false if all the connected components of the starting node have been evaluated and the desired node is not reached.

Page 1

ALGO Spring 2019

Section 07

HW02 solution

Problem 2: DPV Problem 3.15 The police department in the city of Computopia has made all streets one-way. The mayor contends that there is still a way to drive legally from any intersection in the city to any other intersection, but the opposition is not convinced. A computer program is needed to determine whether the mayor is right. However, the city elections are coming up soon, and there is just enough time to run a linear-time algorithm. a.) Formulate this problem graph-theoretically, and explain why it can indeed be solved in linear time. The intersections would be the vertices of a graph and the streets would be the edges. Since they run in one direction, they would be directed edges. The Mayor’s claim would be equivalent to saying the graph is strongly connected since you can supposedly get from any vertex to any other vertex. Then the claim can be proven if the graph has only one strongly connected component, which can be check with kosaraju’s algorithm in linear time. b.) Suppose it now turns out that the mayors original claim is false. She next claims something weaker: if you start driving from town hall, navigating one-way streets, then no matter where you reach, there is always a way to drive legally back to the town hall. Formulate this weaker property as a graph-theoretic problem, and carefully show how it too can be checked in linear time. You assume that town hall is in an SCC and if it runs into another SCC, which means that you cannot get back to the previous SCC where townhall is located, then the Mayor’s statement is false. This would also be in linear time through the use of Kosaraju’s algorithm.

Page 2

ALGO Spring 2019

Section 07

HW02 solution

Problem 3: DPV Problem 3.22 Give an efficient algorithm which takes as input a directed graph G = (V, E), and determines whether or not there is a vertex s ∈ V from which all other vertices are reachable.

To prove that it has a vertex that reaches all other vertices you take the graph G = (V, E) then it runs kosarajus algorithm. If a strongly connected component that contains all vertexes in V then there exists at least one vertex that can reach all other vertexes in V. To find the specific vertex, run a topological sort on the graph counting the number of sources. If there is more than one source, then the case does not exists. If there is only one source, then that source would be the desired s.

Page 3

ALGO Spring 2019

Section 07

HW02 solution

Problem 4: DPV Problem 3.24 Give a linear-time algorithm for the following task. Input: A directed acyclic graph G Question: Does G contain a directed path that touches every vertex exactly once?

Topologically sort the directed acyclic graph G. Take every two consecutive nodes in the DAG and check if there is an edge connecting them, such that vertices vi and vi + 1, where they are both defined, should have an edge between the two nodes. If there exists a edge between every consecutive pair of nodes in a topologically sorted graph, then there exists a path that touches every vertices exactly once.

Page 4

ALGO Spring 2019

Section 07

HW02 solution

Problem 5: DPV Problem 3.25) You are given a directed graph in which each node u V has an associated price pu which is a positive integer. Define the array cost as follows: for each u V cost[u] = price of the cheapest node reachable from u (including u itself ). For instance, in the graph below (with prices shown for each vertex), the cost values of the nodes A, B, C, D, E, F are 2, 1, 4, 1, 4, 5, respectively Your goal is to design an algorithm that fills in the entire cost array (i.e., for all vertices). a.) Give a linear-time algorithm that works for directed acyclic graphs. (Hint: Handle the vertices in a particular order.) Run a topological sort on the DAG. Iterate through the nodes of the sorted DAG in reverse topological order. If the node is a sink, it means cost[u] = pu . If it is not a sink, check all of the children of that node where the child you are looking at is represented by v. If cost[v] < pu then cost[u] = cost[v]. If cost[v] > pu then cost[u] = pu . At the end of the iteration, every node will have the lowest price that it can reach. b.) Extend this to a linear-time algorithm that works for all directed graphs. (Hint: Recall the two-tiered structure of directed graphs.) To get the DAG of all the strongly connected components in the graph, perform Kosarajus algorithm on the graph. Let s represent any of the SCC in the DAG, then ps is equal to the lowest pu for any u in s. Run the algorithm from part a on the new DAG of strongly connected components. Since all u’s in any s (SCC), the u can reach any other u in that s, then cost[u] for all u in s is equal to ps

Page 5...