## Question

2) Given any undirected graph, derive a polynomial-time algorithm that finds [V/2] vertices that collectively account for at least three-fourths (3/4) of the edges. Thus, if you select a vertex, all edges incident to that vertex are thus accounted for. The description of your algorithm should be very simple, code is not necessary. However, it is most important that you justify that at least 3/4 of the edges are indeed accounted for in your algorithm. Providing an algorithm,even though a valid algorithm, without the proper justification will result in a major deduction.

3) Given, any undirected, connected graph. Redefine the weight of a spanning tree to be the weight of the maximum weight edge in the tree (i.e. the weight of the tree is no longer the sum of the weights of all the edges in the tree, only the weight of the edge with the maximum weight). Someone tells you that the minimum weight spanning tree under the new definition is also the spanning tree under the normal definition. You are skeptical and investigate. If true, then provide a convincing argument as to why it is but if false, then provide a specific counterexample (i.e. a specific set of vertices, edges, and weights to the edges).

4). Given two sorted arrays N and M, the former of size n, where n is variable and extremely large being well over a million,and the latter of size m, where.1001=m.Describe in simple English (try not to provide any code, if you do provide code you must still provide a description of your algorithm in simple English) how you would find the median of the n+m elements efficiently (provide your analysis)?

5) Jeff Speedy drives his Honda Accord from the west coast to the east coast. His Accord can travel n miles on a full tank of gas. Speedy has already mapped out his route, identifying the distances between gas stations along the way. Speedy wants to stop as few times as possible so describe a strategy that will efficiently allow him to do this and justify your solution as best as you can. You will be graded on the efficiency of your algorithm (provide your analysis).

## Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

Problem 2As solving approach we can consider that algorithm choses randomly |V|/2. Now, if we randomly consider any edge of the graph, then are possible 4 situations: both of its vertices to be chosen, one of its vertices to be chosen (2 cases, one per each vertex) or none of the two vertices to be chosen. So for any given edge, there is a ¾ probability of being accounted by a chosen vertex. This observation leads to the conclusion that the expected number of accounted edges is ¾* |E|. So the selection of ¾ edges exist (this is the non-deterministic solution).

In order to effectively find it, it must be constructed a deterministic algorithm. This can be based on a Greedy approach. We select at the beginning the vertex with the highest degree (this meaning it collects the most edges among all vertices) and update the adjacent/neighbor vertices with the incidence coefficient....