[SOLVED] CSE 321 Homework 3

CSE 321 Homework 3

1-) There are 2n boxes standing in a row; the first n of them are black and the remaining n boxes are white. Design a decrease-and-conquer algorithm that makes the boxes alternate in a black-white-black-white pattern using minimum number of moves. Remember that interchanging any two boxes is considered to be one move. Analyze the worst-case, best-case and average-case complexities of your algorithm. Explain your algorithm in the report file.
2-) Fake coin problem is a famous problem and there are many versions of it in the literature. In our version, there are n coins which look exactly the same but one of them is fake. You can use a weighbridge which has two scales to find the fake coins. Design a decrease-and-conquer algorithm which finds the fake coin. Analyze the worst-case, best-case and average-case complexities of your algorithm. Explain your algorithm in the report file.
3-) Implement the quick sort and insertion sort algorithms and count the number of swap operations to compare these two algorithms. Analyze the average-case complexity of the algorithms. Compare the operations count in your report file to decide which algorithm is better and support your analysis by using the theoretical average-case analysis of your algorithms. Make a comparative evaluation of your experimental analysis with the theoretical analysis. Discuss the results.
4-) Design a decrease and conquer algorithm that finds the median of an unsorted array. Implement your algorithm and analyze the worst-case complexity of your algorithm.
5-) Suppose that there is an array A which consists of n integer values. Design a recursive exhaustive search algorithm that finds the optimal sub-array B such that: 𝑆U𝑀(𝐵)≤(𝑚𝑎𝑥(𝐴)+𝑚in(A)) x 𝑛4
The optimality criterion is to have the minimum number of multiplication of items in the sub-array. For example:
Let’s A = [2, 4, 7, 5, 22, 11], and the sub-arrays that satisfy the condition: 𝑆U𝑀(𝐵)≤36
[22, 11, 4] [22, 11, 2, 5, 7] [22, 7, 5, 2]
[22, 11, 5] [22, 11, 2, 4, 5, 7] [22, 7, 5, 4]
[22, 11, 7] [22, 7, 5, 4, 2] [22, 11, 5, 7]
[22, 11, 4, 2] [22, 11, 4, 2, 7] [22, 11, 4, 5, 7]
[22, 11, 4, 5] [22, 11, 4, 2, 5] [22, 11, 4, 7]
The optimal sub-array is [22, 11, 4].
Implement your proposed algorithm using Python. Analyze the worst-case complexity of the algorithm. Explain your algorithm in the report file.