Description
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 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 k
th 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 to
solve the exponentiation problem, which is to compute a
n, 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
