What is the running time of your algorithm

Assignment Help Computer Engineering

Reference no: EM132141246

Question :

Suppose we are given a "chain" of n nodes as shown below. Each node i is "neighbors" with the node to its left and the node to its right (if they exist).

An independent set of these nodes is a subset of the nodes such that no two of the chosen nodes are neighbors. In the below example, the first and fourth vertices form an independent set, but the first, third, and fourth vertices do not (because the third and fourth are neighbors). Now suppose each node has a positive weight.

We are interested in computing an independent set such that the sum of the weights of the chosen nodes are as large as possible. In the example, the optimal solution is to choose the second and fourth vertices for a weight of 30.

(15) - (20) - (7) - (10)

(a) A natural attempt of a greedy algorithm for this problem is to take the vertex with the largest weight, then delete that vertex's neighbors (because they cannot also be in an independent set). Repeat this process until there are no more vertices which can be included. Give a counterexample which shows that this algorithm may not give an optimal solution.

(b) Let a[i] denote the weight of a maximum-weight independent set when only considering the first i vertices of the path. Give the values a[1], a[2], a[3], and a[4] for the example given above.

(d) Give a bottom-up dynamic programming algorithm based off your recursive definition. What is the running time of your algorithm?

Reference no: EM132141246

Questions Cloud

How much will it cost to provide disk space : At contemporary memory pricing of $7 / GB, how much will it cost to fill the machine? Knowing what you know about virtual memory.

How this special computer can be used to sort the given n : Suppose you are given n positive integers to sort on a special computer which has access to special memory containing p slots.

Create an algorithm for telling if l and m store the same : Create an algorithm for telling if L and M store the same sequence of elements (but perhaps with different starting points).

Provide again a polynomial time algorithm : Suppose we are given a directed graph G = (V, E), a set of nodes A V (denoted as people) and a set of nodes B V (denoted as exit).

What is the running time of your algorithm : Give a bottom-up dynamic programming algorithm based off your recursive definition. What is the running time of your algorithm?

How many total packets are sent with stop-and-wait : Assume that ACKs are never lost. How many total packets (including retransmissions) are sent with stop-and-wait.

Design an algorithm to update the minimum spanning tre : Design an algorithm to update the minimum spanning tree when the weight of a single edge e is increased.

What speedup is possible with pipelining : What is the maximum execution rate without pipelining? What speedup is possible with pipelining?

Would there be any advantages to using the cts and rts frame : Suppose the IEEE 802.11 RTS and CTS frames were as long as the standard DATA and ACK frames.

User Account

All Pages