CSE6140 Assignment 5 Solved

 



Problem 1
Suppose, for your Thanksgiving break, you decide to drive from Atlanta to New York along Interstate Highways. Your gas tank, when full, holds enough gas to travel ‘K’ miles (assume you know K), and you have a map that gives distances between gas stations along the route. Let d1 < d2 < ··· < dn be the locations of all the gas stations along the route where di is the distance from Atlanta to the ith gas station. Assume that the max distance possible between any 2 gas stations is ‘K’ miles.

Your goal is to make as few gas stops as possible along the way without running out of gas. Give an efficient algorithm (also mention time complexity) to determine at which gas stations you should stop and prove that your strategy yields an optimal solution.

Problem 2
Some DP problems. Kindly prove the optimal substructure and give a recursive expression. Give the corresponding recursive algorithm with memoization or a bottom-up version is fine too. Analyze its time and space complexity.

1.    For any integer x ≥ 1, give an algorithm to find the number of different ways to write x as the sum of 1, 3, 4. Example for x = 5:

5 = 1 + 4 = 4 + 1

= 1 + 1 + 3

(1)

= 1 + 3 + 1

= 3 + 1 + 1

= 1 + 1 + 1 + 1 + 1

Thus, we can express x = 5 in 6 different ways.

2.    Evelyn hosted this year’s Thanksgiving feast at her place. She invited her family andfriends, who all brought gifts for her children. Almost like any other siblings, Charlie and Alan were again fighting over who should get what gifts. Now, to resolve the conflict between them, Evelyn went to seek help from her housekeeper Berta. Now, she suggested Charlie and Alan to play the following game,

She arranged all the n gifts in a row having values from v(1),··· ,v(n), where ith gift has value v(i). Assume n is even. Both of the players get their chances to play, in an alternate fashion. In each turn, a player can either select the first or the last gift, removes it from the row and gains the corresponding value of the gift. Now, as Charlie is always mean to Alan, Evelyn decides that Alan should go first. Determine the maximum possible value that Alan can definitely accumulate.

Problem 3
Let G = (V,E) be a flow network with source s, sink t and integer capacities. Suppose that we are given a maximum flow in G.

1.    Suppose that the capacity of a single edge (u,v) ∈ E is increased by 1. Give an O(|V | + |E|) time algorithm to update the maximum flow.

2.    Suppose that the capacity of a single edge (u,v) ∈ E is decreased by 1. Give an O(|V | + |E|) time algorithm to update the maximum flow.

Problem 4
Consider the maximum flow in a given network between two designated nodes s and t. For all statements below, explain why it is true or provide a counterexample.

1.    If the capacity of every arc is even, then the value of the maximum flow must be even.

2.    If the capacity of every arc is even, then there is a maximum flow in which the flow oneach arc is even.

3.    If the capacity of every arc is odd, then the value of the maximum flow must be odd.

4.    If the capacity of every arc is odd, then there is a maximum flow in which the flow oneach arc is odd.

Problem 5
Let G = (V,E) be a directed graph. A vertex s in G is a source if its in-degree is zero. Similarly, a vertex t in G is a sink if its out-degree is zero.

1.    Propose an O(|V | + |E|) time algorithm to locate all the sources and targets in G.

2.    Prove that a DAG must contain at least one source and at least one target.

3.    Let G = (V,E) be a DAG. Propose an O(|V | + |E|) time algorithm to count the total number of paths from all the sources in G to all the targets in G.