For each question below, explain the algorithm you propose, and analyze its complexity.
1. There is an n-meter-long steel wire and it is needed to be cut into 1meter-long pieces. There is a mechanic who asks money for every cutting. The machine that the mechanic uses allows multiple pieces to be cut at the same time. Before going to the mechanics, you want to calculate the minimum number of cuts that are needed to cut several pieces at the same time. Design a decrease-and-conquer algorithm that gives the minimum number of cuts needed.
2. In a science laboratory, n experiments were performed to generate a new vaccine, and the success rates (size of n) were saved. A scientist from the laboratory will write an article about the outcome of the experiments, and she needs the worst and the best results. Design a divide-and-conquer algorithm to help her.
3. Regarding the experiments mentioned in the previous question, anotherscientist from the laboratory noticed that the first k-1 number of experiments were meaningless when we sort the experiments in terms of the success rates in increasing order. He wants to know the success rate of the first meaningful kth experiment. Design a decrease-and-conquer algorithm to help him without sorting the success rates of the experiments.
4. In a given array containing n real numbers A[1...n], the pair (A[i],A[j]) is called reverse-ordered pair if i < j and A[i] > A[j]. The more the number of reverse-ordered pairs the sequence has, the further from being sorted the sequence is.
In a military location, they receive information as number sequences (with size n) sorted in increasing order from a special telecommunication device. If there are reverse-ordered pairs in the sequence, that means the information is corrupted. Since security is crucial for this operation, they want to
1
know how corrupted the information is. Design a divide-and-conquer algorithm that finds the number of reverse-ordered pairs in the received sequence to help them.
5. Design a brute-force algorithm and a divide-and-conquer algorithm tosolve the exponentiation problem, which is to compute an, where a > 0 and n is a positive integer.
