# Programming Problems 8

November 11, 2009 2 Comments

**Reduced Edge MST**

Recall that we can nd a minimum spanning tree of a graph G = (V,E) in O(m+ n log n) time, where m = |E| and n = |V|. Suppose we change the weight of a single arbitrary edge of G to obtain a new graph G’. Show that the new minimum spanning tree of G’ can be found in linear time, given a minimum spanning tree

for the old graph G. More formally, design an algorithm that implements:

NewSpanTree(G, w, e, x, T), which returns the minimum spanning tree of G upon changing the weight of edge e from w(e) to x, where T is a minimum spanning tree of G under the original edge weights w.Your algorithm for NewSpanTree should run in O(m+ n) time.

**Merging Scheme**

Suppose you have k arrays, A1,A2,……, Ak, where each input array Ai is a sorted array of numbers. You would like to output one sorted array of all the numbers in the input. To do this, you repeatedly take a pair of arrays and merge their elements into sorted order, writing the result of this merge to an intermediate

array. To merge a pair of sorted arrays with p and q elements into one sorted array takes p + q time.

The specication of which arrays to merge in this pairwise process is called a merging scheme. Your goal is to nd a scheme that merges all the input arrays into one sorted array and uses the minimum total merge time.

Design an algorithm that nds an optimal merging scheme. Your algorithm should run in O(n + k log k) time, where n is the total length of all the input arrays.

**Arranging Pillars**

You are given N blocks of height 1…N. In how many ways can you arrange these blocks in a row such that when viewed from left you see only L blocks (rest are hidden by taller blocks) and when seen from right you see only R blocks? Example given N=3, L=2, R=1 there is only one arrangement {2, 1, 3} while for N=3, L=2, R=2 there are two ways {1, 3, 2} and {2, 3, 1}.

**Paintings**

You have to paint N boards of length {B1, B2, B3… BN}. There are K painters available and you are also given how much time a painter takes to paint 1 unit of board. You have to get this job done as soon as possible under the constraints that any painter will only paint continuous sections of board, say board {2, 3, 4} or only board {1} or nothing but not board {2, 4, 5}.

**Array Clicking**

You are given an array A of length N. You have to destroy it, given that you have the power to remove any continuous chunk of same numbers with 1 click. Thus the order in which you remove chunk matters. For example given {1, 2, 3, 1} normally it will take you 4 clicks to remove but if you first remove 2 making array {1, 3, 1} then 3 making it {1, 1} and then you can remove this continuous chunk of similar number in one click, thus completing the task in 3 clicks. How to find minimum number of clicks required? Another example is {1, 2, 3, 2, 1} which can be destroyed in 3 clicks

Reduced edge MST

there are two cases to be considered :

1. if the edge which is reduced already belonged to the MST then update the edge. and update the total weight of MST = old weight- weight of the edge earlier + new weight of the edge

2 when the edge whose weight is reduced is not in the old MST then

include the reduced edge in MST. this will form cycle. now from this cycle remove the largest edge. and we will get the new mst

weight of new MST= weight of old MST – weight of edge removed(largest edge in cycle) + weight of new edge added

The “painting”question is not clear to me.can u plz explain?