 # 5 Algorithm Design Problems Involving Greedy, Sorting, Graphs (Minimum Spanning Trees)

Subject Computer Science Data Structures and Algorithms

## Question

1) Given T1 and T2 are distinct MSTs for an undirected graph G. Let (u,v) be the lightest edge that is in T2 and not in T1. Let (x,y) be any edge that is in T1 and not in T2. Can you say something about the weight of (u,v) and (x,y)? Be convincing in your argument.

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 2
As 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....

This is only a preview of the solution. Please use the purchase button to see the entire solution

## Related Homework Solutions

3 Classical Algorithms Involving Greedy and Dynamic Programming \$29.25
Knapsack
Actvity
Selection
Job
Scheduling
Proof
Correctness
Integer
Greedy
Choice
Dynamic
Programming
Compatible
Maximum
Earliest
Duration
Overlap
Start
Time
Item
Weight
Profit
Optimal
Solution
Complexity
Recurrence
Substru
MergeSort Algorithm Applied to the E, X, A, M, P, L, E List \$4.00
Computer Science
Data Structures
Merge-sort
Mergesort
Algorithm
Pseudo
Code
Alphabetical
Order
List
SortedBag Implementation Using Doubly Linked Ring \$43.00
Computer Science
C++ Programming
Data Structures
Algorithms
Sorted Bag
Search Keys
Nodes
Operators
Iterators
Students
Erased Elements
Randomization
Randomization & Probability Questions \$18.00
Randomized
Probability
Algorithm
Dice
Conditional
False
Positive
Negative
Sum
Result
Sample
Dijkstra's Algorithm in C++ \$20.00
Computer Science
Dijkstra's Algorithm
Programming
Variables
Distances
Functions
Vectors
Loops
Conditions
Statements
City Maps
Coordinates
Points
Paths
Intersection
Algorithms Assignment \$1.00
Algorithm
Computer Science
Graphs
Programming Language
Programming
Analysis
Live Chats