程序代做 CS 344 – Spring 2022 Homework 5

CS 344 – Spring 2022 Homework 5
100 points total + 10 points EC
General Assumption: You can assume that all graphs given in this prob- lem set have zero isolated vertices, so |E| ≥ |V |/2.
1 Problem 1 (30 points total) 1.1 Part 1 (7 points)

Copyright By PowCoder代写 加微信 powcoder

Consider the graph G in the figure below. Now consider running Dijk- stra(G,s). (s is the bottom right vertex.)
Draw a table which indicates what the algorithm looks like after each execution of the while loop inside Dijkstra’s. In particular, for each iteration of the loop you should indicate
• which vertex is explored in that iteration
• what is the label d(v) for every vertex v at the end of that iteration.
• So all in all you should draw a table where each row corresponds to an iteration of the while loop, there is a column for ”explored vertex” which indicates which vertex is explored in that iteration, and there is a column for every vertex v which indicates the value of d(v) at the end of the iteration.

NOTE: for an example of how Dijkstra is executed on a different graph, you may find it helpful to look at Figure 24.6 on page 659 of CLRS. In that example the actual graph is drawn at the end of each iteration. You can do it that way if you prefer, but you can also use a table instead, since that’s easier for typing.
1.2 Part 2 (8 points)
In this problem, we want to show that Dijkstra only works if we assume all weights are non-negative. Your goal in this problem is to give an example of a graph G = (V, E) with the following properties
• All edge weights in G are positive except there is EXACTLY ONE edge (x, y) with a negative weight
• G contains two vertices s and t such that running Dijkstra(G,s) returns the wrong answer for dist(s,t).

WHAT TO WRITE: In your answer, make sure to clearly indicate • Your graph G itself along with all the edge weights
• ThetwoverticessandtinG
• What is the actual shortest s-t distance
• what is the shortest s-t distance returned by Dijkstra
Your graph G should have at most 7 vertices. You can get away with
even fewer than 7 vertices.
1.3 Part 3 (8 points)
Consider the following problem: • INPUT
– A directed graph G where all edges have weight −1, 0, or 1 – Two fixed vertices s,t.
• OUTPUT: dist(s,t)
Consider the following algorithm for this problem:
Bad Algorithm
• Create a new graph G′ which is the same as G except that all weights are increased by 1. So G′ uses weight function w′, where w′(x,y) = w(x,y)+1.
• Run Dijkstra(G’,s)
• Let P be the shortest s-t path in G′ returned by Dijkstra(G’,s)
• Output w(P) as your final answer, where w(P) is the weight of path P in the original graph G.

The Problem: We want to show that the above algorithm does NOT work. Give an example graph G where the above algorithm produces an incorrect solution. Concretely, you need to show a graph G such that the shortest s−t path in G′ is NOT the shortest s−t path in G.
NOTE: your graph should contain at most 7 vertices. you can get with many fewer vertices.
WHAT TO WRITE: In your answer, make sure to clearly indicate • Your graph G itself along with all the edge weights
• ThetwoverticessandtinG
• What is the actual shortest s-t distance
• what is the shortest s-t distance returned by Bad Algorithm. 1.4 Part 4: 7 points
Recall that Dijkstra requires a data structure D that can handle three op- erations. There exists a fancy data structure D with the following running times.
• D.insert(key k, value v) takes O(log(n)) time
• D.decrease-key(value v, key k’) takes O(1) time. • D.delete-min() takes O(log(n)) time.
The Problem: if one used the above fancy data structure inside of Di- jkstra’s algorithm, what would the resulting running time of Dijkstra’s be in big-O notation? How does this runtime compare to the O(|E| log(|V |)) running time we got in class by using a min-heap? For what edge-density of graphs (if any) does the fancy data structure better give a better running time (in terms of big-O) than O(|E| log(|V |))? For what edge-density (if any) does it have the same running time? For what edge-density (if any) does it have a worse running time?

2 Problem 2 (20 points)
We say that an undirected graph G = (V,E) is bipartite if it is possible to color every vertex either red or blue in such a way that for every edge (u, v) ∈ E, u and v have different colors. For example, in Figure 1, the graph on the left is bipartite because such a red-blue coloring is possible, but the graph on the right is not bipartite: you can check for yourself that no matter how you color the vertices of the right graph red/blue, there will always be an edge between two vertices of the same color.
The Question: Assume you are given an undirected graph G that is connected: that is, there is a path from every vertex to every other vertex. Give pseudocode for an algorithm CheckBipartite(G) that outputs TRUE if the graph is bipartite (i.e. if there exists a valid red/blue coloring) or FALSE if the algorithm is non-bipartite. Your algorithm should run in O(|E|) time.
NOTE: you only need to write pseudocode. No justification or running time analysis necessary.
HINT 1: Start by picking an arbitrary vertex s and coloring it red. Now, proceeding from s, try to color the rest of the vertices in a way that doesn’t create any illegal edge (by illegal I mean blue-blue or red-red.)
HINT 2: BFS will prove very useful here. One approach is to modify the BFS algorithm. An even better approach is to just use BFS(G,s) as a black-box. After you run BFS(G,s) you will know dist(s,v) for every vertex v (you don’t have to explain how it works, since BFS is in our library). Is there a way to use all the dist(s,v) to determine if the graph is bipartite?
NOTE: you need to write full pseudocode. So if you modify BFS, you need to write the full pseudocode of your modified BFS. That’s why I recommend using the approach in Hint 2, since then you can use BFS as a black-box, without needing to write any pseudocode for it.
3 Problem 3 – 20 points
So far we have covered graphs where weights are on the edges. We say that a graph H = (V, E) is vertex-weighted if every vertex v has a weight c(v). We say that the weight of a path is the sum of all vertex weights on the path. We let distH(s,v) be the length of the shortest path from s to v in H. Note that all these definitions are essentially the same as before, except that now weights refer to vertices rather than to edges.

Figure 1: Graphs for Problem 2. The left graph is bipartite. It is not hard to check that the right graph is non-bipartite, because no matter how you color the vertices, there will be a red-red edge or a blue-blue edge.
Notation Note: I will always use H to refer to a vertex weighted graph and G to refer to an edge-weighted one. I will always use c(v) to refer to vertex weights and w(u,v) to refer to edge weights. I will let E(G) or E(H) to denote the edge set of a graph.
Vertex-Weighted-SP-Problem
• INPUT: a vertex-weighted directed graph H with non-negative vertex weights c(v) and a source s
• OUTPUT:distH(s,v)forallv∈V Edge-Weighted-SP-Problem
• INPUT: an edge-weighted directed graph G with non-negative edge weights w(u, v) and a source s
• OUTPUT: distG(s, v) for all v ∈ V

3.1 Part 1 – 10 points
Say that your library already has an algorithm EdgeWeightedSP(G,s) that solves the Edge-Weighted-SP-Problem in O(|E(G)|) time. Use this to write pseudocode for an algorithm VertexWeightedSP(H,s) that solves the Vertex- Weighted-SP-Problem in O(|E(H)|) time.
To clarify, in this problem you are given a vertex-weighted graph H and must write an algorithm to compute ll distH (s, v). But the point is that you are allowed to use EdgeWeightedSP as a black box in your algorithm.
NOTE: the algorithm EdgeWeightedSP(G,s) only runs on edge-weighted graphs, so you cannot run in on H directly. The point is to use graph trans- formation!
WHAT TO WRITE: You start with a graph H. You will want to create an edge-weighted graph G and then run EdgeWeightedSP. Make sure to be extremely precise about what vertices/edges are in G, and what the edge weights in G are.
IMPORTANT: Please use c(v) to refer to vertex weights in H. Use w(u, v) when talking about edge weights in G.
3.2 Part 2 – 10 points
In this problem, we go in the opposite direction.
Say that your library already has an algorithm VertexWeightedSP(H,s)
that solves the Vertex-Weighted-SP-Problem in O(|E(H)|) time. Use this to write pseudocode for an algorithm EdgeWeightedSP(G,s) that solves the Edge-Weighted-SP-Problem in O(|E(G)|) time.
To clarify, in this problem you are given a edge-weighted graph G and must write an algorithm to compute ll distances distG(s,v) in G. But the point is that you are allowed to use VertexWeightedSP as a black box in your algorithm.
NOTE: the algorithm VertexWeightedSP(H,s) only runs on vertex-weighted graphs, so you cannot run in on G directly. The point is to use graph trans- formation!
WHAT TO WRITE: You start with a graph G. You will want to create an vertex-weighted graph H and then run VertexWeightedSP. Make sure to be extremely precise about what vertices/edges are in H, and what the vertex weights in H are.

IMPORTANT: Please use c(v) to refer to vertex weights in H. Use w(u, v) when talking about edge weights in G.
4 Problem 4 (30 points)
The goal of this problem is to show that any graph with a lot of edges must contain a short cycle. In particular, we will prove the following theorem:
theorem: Consider any unweighted, undirected graph G = (V,E) with |V| = n and |E| = m. If m ≥ 100n5/4 then the graph G contains a cycle with ≤ 8 edges.
We will prove the theorem in two parts. Note that the two parts are unrelated, and even if you are stuck on one you can solve the other.
4.1 Part 1 (15 points)
first we need the following definitions. Given graph G = (V,E) and any subset of vertices V ′ ⊆ V , we define the induced graph G[V ′] to the graph whosevertexsetisV′,andwhoseedgesareE′ ={(u,v)∈E|u∈V andv∈ V }. In words, G′ is the graph G restricted only to vertices/edges in V ′.
We can now state the following claim Consider any unweighted, undirected graph G = (V, E) with |V | = n and |E| = m.
Claim: Consider any unweighted, undirected graph G = (V,E) with |V|=nand|E|=m. Ifm≥100n5/4 thenthereexistsasetV′ ⊆V such that every vertex in G[V ′] has degree at least 3n1/4 in G[V ′]. Note that we are considering the degree in G[V ′], not in the original graph G. Formally, every vertex v ∈ V ′ must have at least 3n1/4 neighbors in V ′; that is , there must be at least 3n1/4 vertices x ∈ V ′ such that edge (v, x) ∈ E.
We will prove the above claim by explicitly giving a procedure for con- structing V ′.
• Start with V ′ ← V
• While there exists v ∈ V ′ with [degree of v in G[V ′]] < 3n1/4 – remove v from V ′ • return V ′ The Problem: Prove that what the above procedure terminates, V ′ is non-empty. NOTE: note that even if a vertex v initially has degree ≥ 3n1/4 in V , as we start removing from V ′, [deggree of v in V ′] will drop. So in theory it’s possible that we will end up removing all vertices using the procedure above. Your goal is show that this doesn’t actually happen. NOTE: I am looking for a convincing justification. The justification I have in mind is only a few lines long. You should NOT write a very long justification for this problem, as that means you are on the wrong track. In particular, you do not need to use induction or proof by contradiction or anything like that. 4.2 Part 2 (15 points) We now conclude the theorem by proving a second claim. Claim: Consider any undirected, unweighted graph G′ = (V ′, E′) with the property that every vertex in V ′ has degree at least 3n1/4 in G′. Prove that G′ contains a cycle with ≤ 8 edges. NOTE: By proof I just mean that you need a convincing explanation. You do not need to use induction or proof by contradiction or anything like that. HINT: consider doing a BFS from some vertex in the graph and use the fact that every vertex has high degree. HINT:: you do not need anything from part 1 to solve this problem. It’s unrelated to part 1. conclusion It’s not hard to check that the claims from part 1 and part 2 combined imply the theorem statement at the beginning of the HW. You don’t have to do show this – just wanted to draw your attention to it as motivation for the problem. 5 Problem 5 – Extra Credit – 10 points We showed in class that by using the min-heap data structure inside Dijkstra we can achieve runtime O(|E| + |V | log(|V |)). The goal of this problem is to use a different data structure that works well when all dist(s,v) are small. Say that you are given a directed graph G = (V, E) where all edge weights are positive integers. Let s be a source vertex and say that you are guaranteed that all shortest paths from s have length at most B, for some parameter B; that is, you are told in advance that dist(s,v) ≤ B for all v ∈ V. Show a data structure D such that if we run Dijkstra using data structure D on graph G then the runtime is O(m + B). Make sure to write pseudocode for how to implement each of the three operations of the data structure (the three operations we need for Dijkstra, covered in class, and also specified in problem 1.4) IMPORTANT: You must also justify why if you plug in the above data structure into Dijkstra, the runtime is O(m + B). NOTE: the data structure is simple and doesn’t require you to use any- thing beyond basic things such as arrays and lists. 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com