Algorithms

When automatically checking coding exercises, we often run the programs in
question against test cases, which are made up of one input and one output file. As expected,
the program is fed the input file and then its output is compared with the output file. If these
match for all test cases, we deem the program correct.
Coming up with these test cases is tricky. Specifically, we want to create test cases for the
following problem: ‘Given a complete weighted graph G, compute its minimum spanning tree
T’. We have already created the desired output files containing the different minimum spanning
trees, we now want to find the corresponding input files.
It is known that a graph can have many different MST’s. To make testing easier, we want
to ensure that the minimum spanning tree in every output file is unique for the graph described
in the respective input file. The test cases also need to be able to tell apart algorithms that
are wrong, but happen to find the correct MST by chance. For example, if all edges not in the
MST have very large weights, a naive algorithm could find the MST by including only the light
edges. Of course this algorithm would be incorrect in general. To avoid this, we want the input
files to contain complete graphs G whose sum of edge weights is minimum. You need to design
a program that can generate these input files.
Goal: Given a weighted tree T with n nodes, find the complete graph G of minimum weight
such that T ⊆ G and T is the unique minimum spanning tree of G. Assume all edge weights
are integer.
1. Find an algorithm whose run time is polynomial in n.
2. Improve the complexity to O(n · log n).
Hint: One way to do this is by thinking of Kruskal’s algorithm and the cut property of minimum
spanning trees.

can you help me to find a solution ?

Philip decided to supplement his income by participating in the popular game
show ‘Open the Boxes and keep the Best!’. The game is played in turns. At every turn, the
host shows Philip a box that can be opened by paying ci > 0. The box will contain a random
prize: in particular its value could be anything in {0, 1, 2, . . . , n}, uniformly at random.
At every step, Philip can stop playing and keep only one prize, the best found so far. Of course,
the costs he paid are not refunded. All of the boxes are known in advance, as well as the order
the host will present them. Help Philip find the optimal strategy and calculate his expected
payoff, which is the prize he keeps minus the total cost paid.
Goal: Given as input the number of boxes k, the number of different rewards n as well as
the cost ci (which is guaranteed to be integer) of every box:
1. Design a O(n^2· k) algorithm to find the expected optimal reward.
2. Improve the complexity to O(n · k).
Hint: One way is to use dynamic programming

can you help me to find a solution?