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 1-meter-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, another scientist from the laboratory noticed that the first k-1 number of exper-iments 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 algo-rithm 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 informa-tion is corrupted. Since security is crucial for this operation, they want to
1
know how corrupted the information is. Design a divide-and-conquer algo-rithm 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 to solve the exponentiation problem, which is to compute an, where a > 0 and n is a positive integer.
Notes
1. Late submissions will not be accepted.
2. No collaboration is allowed, the homework must be done individually.
3. The homework will be submitted in ZIP format. The file hierarchy will be like:
CSE321 HW4 [StudentID].zip
| → CSE321 HW4 report [StudentID].pdf | → cutting [StudentID].py
| → worst best [StudentID].py | → meaningful [StudentID].py | → find rop [StudentID].py
| → exponent [StudentID].py
2
