### 57. Consider a graph G = (V, E), where V = {v 1 , v 2 , …, v 100 }, E = {(v i , v j )|1≤i≤j≤100}, and weight of the edge (v i , v j ) is |i – j|. The weight of the minimum spanning tree of G is _____.

### 58. For n > 2, let a ∈ {0, 1} n be a non-zero vector. Suppose that x is chosen uniformly at random form (0,1)n. Then, the probability that is an number is _______ .

### 59. Consider the array representation of a binary min-heap containing 1023 element. The minimum number of comparisons required to find the maximum in the heap is ______.

### 60. Consider a non-pipelined processor operating at 2.5 GHz. It takes 5 clock cycles to complete an instruction. You are going to make a 5-stage pipeline out of this processor. Overheads associated with pipelining force you to operate the pipeline processor at 2 GHz. In a given program, assume that 30% are memory instructions, 60% are ALU instructions and the rest are branch instruction. 5% of the memory instructions cause stalls of 50 clock cycles each due to cache misses and 50% of the branch instructions cause stalls of 2 cycles each. Assume that there are no stalls associated with the execution of ALU instructions. For this program, the speedup achieved by the pipelined processor over the non-pipeline processor (round off to 2 decimal places) is ______.