Starting from:
$30
CSCI570-Homework 2 Minimum - Maximum, Unique MST,Near-Tree and Subsequence Solved
1. Minimum - Maximum
You are given a weighted graph G and two designated vertices s and t. Your goal is to find a path from s to t in which the minimum edge weight is maximized, i.e. if there are two paths with weights 10−1−5 and 2−7−3, then the second path is considered better since the minimum weight (2) is greater than the minimum weight of the first (1). Describe an efficient greedy algorithm to solve this problem and show its complexity. Prove its correctness. (Note: This problem is exactly the same problem to Pr. 8 in HW1.)
2. Unique MST
Suppose you are given a connected graph G, with edge costs that are all distinct. Prove that G has a unique minimum spanning tree.
3. Near-Tree
Let us say that a graph G = (V,E) is a near-tree if it is connected and has at most n + 8 edges, where n = |V |. Give an algorithm with running time O(n) that takes a near-tree G with costs on its edges, and
4. Subsequence
You are trying to find whether a sequence of characters is a subsequence of another sequence. A subsequence of a string is obtained by deleting zero or more symbols of that string. For example,
RACECAR is a subsequence of QRAECCETCAURP. Give a linear algorithm that takes two sequences S ′ of length m and S of length n and decides whether S ′ is a subsequence of S. Prove its correctness.
5. Winter in Canada
Your friends are planning an expedition to a small town deep in the Canadian north next winter break. They’ve researched all the travel options and have drawn up a directed graph whose nodes represent intermediate destinations and edges represent the roads between them.
In the course of this, they’ve also learned that extreme weather causes roads in this part of the world to become quite slow in the winter and may cause large travel delays. They’ve found an excellent travel Web site that can accurately predict how fast they’ll be able to travel along the roads; however, the speed of travel depends on the time of year. More precisely, the Web site answers queries of the following form: given an edge e = (v,w) connecting two sites v and w, and given a proposed starting time t from location v, the site will return a value fe ( t), the predicted arrival time at w. The Web site guarantees that fe ( t) ≥ t for all edges e and all times t (you can’t travel backward in time), and that fe ( t) is a monotone increasing function of t (that is, you do not arrive earlier by starting later). Other than that, the functions fe ( t) may be arbitrary. For example, in areas where the travel time does not vary with the season, we would have fe ( t) = t + le , where le is the time needed to travel from the beginning to the end of edge e.
Your friends want to use the Web site to determine the fastest way to travel through the directed graph from their starting point to their intended destination. (You should assume that they start at time 0, and that all predictions made by the Web site are completely correct.) Give a polynomial-time algorithm to do this, where we treat a single query to the Web site (based on a specific edge e and a time t) as taking a single computational step.
6. Shortest Path
Given a directed graph G = (V,E) with nonnegative edge weights and the shortest path distances d(s,u) from a source vertex s to all other vertices in G. However, you are not given the shortest path tree. Devise a
linear time algorithm, to find a shortest path from s to a given vertex t.
7. Worst Gas Mileage in the World
Suppose you were to drive from USC to Santa Monica along I-10. Your gas tank, when full, holds enough gas to go p miles, and you have a map that contains the information on the distances between gas stations along the route. Let d1 < d2 < ... < dn be the locations of all the gas stations along the route where d i is the
distance from USC to the gas station. We assume that the distance between neighboring gas stations is at most p miles. Your goal is to make as few gas stops as possible along the way. Design a greedy algorithm to determine at which gas stations you should stop and prove that your strategy yields an optimal solution.
Prove its correctness.
8. MST
You are given a minimum spanning tree T in a graph G = (V, E). Suppose we remove an edge from G creating a new graph G1 . Assuming G1 that is still connected, devise a linear time algorithm to find a MST in G1 .
9. Recurrences
Solve the following recurrences by the master theorem.
1. T(n) = 9T(n/3) + n + logn
10. More on Recurrences
The recurrence T(n) = 7T(n/2) + n2 describes the running time of an algorithm ALG. A competing algorithm ALG ′ has a running time of T (n) = aT (n/4) + n2log n. What is the largest value of a such that ALG ′ is asymptotically faster than ALG?
You are given a weighted graph G and two designated vertices s and t. Your goal is to find a path from s to t in which the minimum edge weight is maximized, i.e. if there are two paths with weights 10−1−5 and 2−7−3, then the second path is considered better since the minimum weight (2) is greater than the minimum weight of the first (1). Describe an efficient greedy algorithm to solve this problem and show its complexity. Prove its correctness. (Note: This problem is exactly the same problem to Pr. 8 in HW1.)
2. Unique MST
Suppose you are given a connected graph G, with edge costs that are all distinct. Prove that G has a unique minimum spanning tree.
3. Near-Tree
Let us say that a graph G = (V,E) is a near-tree if it is connected and has at most n + 8 edges, where n = |V |. Give an algorithm with running time O(n) that takes a near-tree G with costs on its edges, and
4. Subsequence
You are trying to find whether a sequence of characters is a subsequence of another sequence. A subsequence of a string is obtained by deleting zero or more symbols of that string. For example,
RACECAR is a subsequence of QRAECCETCAURP. Give a linear algorithm that takes two sequences S ′ of length m and S of length n and decides whether S ′ is a subsequence of S. Prove its correctness.
5. Winter in Canada
Your friends are planning an expedition to a small town deep in the Canadian north next winter break. They’ve researched all the travel options and have drawn up a directed graph whose nodes represent intermediate destinations and edges represent the roads between them.
In the course of this, they’ve also learned that extreme weather causes roads in this part of the world to become quite slow in the winter and may cause large travel delays. They’ve found an excellent travel Web site that can accurately predict how fast they’ll be able to travel along the roads; however, the speed of travel depends on the time of year. More precisely, the Web site answers queries of the following form: given an edge e = (v,w) connecting two sites v and w, and given a proposed starting time t from location v, the site will return a value fe ( t), the predicted arrival time at w. The Web site guarantees that fe ( t) ≥ t for all edges e and all times t (you can’t travel backward in time), and that fe ( t) is a monotone increasing function of t (that is, you do not arrive earlier by starting later). Other than that, the functions fe ( t) may be arbitrary. For example, in areas where the travel time does not vary with the season, we would have fe ( t) = t + le , where le is the time needed to travel from the beginning to the end of edge e.
Your friends want to use the Web site to determine the fastest way to travel through the directed graph from their starting point to their intended destination. (You should assume that they start at time 0, and that all predictions made by the Web site are completely correct.) Give a polynomial-time algorithm to do this, where we treat a single query to the Web site (based on a specific edge e and a time t) as taking a single computational step.
6. Shortest Path
Given a directed graph G = (V,E) with nonnegative edge weights and the shortest path distances d(s,u) from a source vertex s to all other vertices in G. However, you are not given the shortest path tree. Devise a
linear time algorithm, to find a shortest path from s to a given vertex t.
7. Worst Gas Mileage in the World
Suppose you were to drive from USC to Santa Monica along I-10. Your gas tank, when full, holds enough gas to go p miles, and you have a map that contains the information on the distances between gas stations along the route. Let d1 < d2 < ... < dn be the locations of all the gas stations along the route where d i is the
distance from USC to the gas station. We assume that the distance between neighboring gas stations is at most p miles. Your goal is to make as few gas stops as possible along the way. Design a greedy algorithm to determine at which gas stations you should stop and prove that your strategy yields an optimal solution.
Prove its correctness.
8. MST
You are given a minimum spanning tree T in a graph G = (V, E). Suppose we remove an edge from G creating a new graph G1 . Assuming G1 that is still connected, devise a linear time algorithm to find a MST in G1 .
9. Recurrences
Solve the following recurrences by the master theorem.
1. T(n) = 9T(n/3) + n + logn
10. More on Recurrences
The recurrence T(n) = 7T(n/2) + n2 describes the running time of an algorithm ALG. A competing algorithm ALG ′ has a running time of T (n) = aT (n/4) + n2log n. What is the largest value of a such that ALG ′ is asymptotically faster than ALG?
1 file (112.6KB)
