Explain What is Meant by Divide and Conquer, Give an Example of How a Divide and Conquer: Algorithm Design & Problem Solving Assignment, UCC

Assignment Questions:

Question 1:

1. (a) Explain what is meant by Divide and Conquer, give an example of how a Divide and Conquer algorithm improved the performance of an algorithm you have studied.

(b) i) Using pseudocode, write an iterative algorithm to calculate the sum of numbers in an array.
ii) Draw a flowchart of your algorithm –use your preferred flowcharting tool and insert an image into your answer document or draw by hand and insert the photo.

(c) For the algorithm in (b), use pseudocode to write a recursive algorithm to find the sum of the numbers. What is its time efficiency – explain your answer with reference to the call stack.

Question 2:

2. (a) The mean of a sequence of numbers is the sum of all numbers in a sequence divided by the number of numbers. Using pseudocode write an algorithm to find the mean of a number sequence in an array.

intgetMean (int a[])

(b) The median is the middle value of a list of numbers. To find the median list the numbers from smallest to largest, then find the midpoint. If the number of numbers is even, add the two numbers adjacent to the midpoint and average them.

Using pseudocode, write an algorithm to calculate the median of a list of numbers.

int getMedian (int a[] )

(c) Using pseudocode, write an algorithm to find the kth smallest element of an unsorted array. What is the time complexity of the algorithm? Describe how you would improve it to run in O(Nlog(N)) or better?

Question 3:

3. (a) The following algorithm has a number of errors in it.

for i = 0 to i < N-1 do
min = A[i]
for j = i to j < N do
if A[j] < A[min] then
min = A[j]
temp = A[min]
A[min] = A[i]
A[i] = temp
End for

What is the name of this algorithm?

(b) Outline 4 issues with the algorithm, clearly explaining each one.

(c) Illustrate how the insertion sort algorithm would sort the following sequence:- 9, 3,4,5,7, 8, 6, 2

Your answer should show the state of the array at the end of each processing cycle in the algorithm.

How does the insertion sort compare the algorithm in (a) if the list to be sorted is:- 1,2,4,3,5,6,7,8