Question

Please answer this in python pseudocode. It's an algorithm question.

1. [10 marks] Consider the function SumKSmallest(A[0..n – 1), k) that returns the sum of the k smallest elements in an unsorted integer array A of size n. For example, given the array A=[6,-6,3,2,1,2,0,4,3,5] and k=3, the function should return -5. a. [3 marks) Write an algorithm in pseudocode for SumKSmallest using the brute force paradigm. Indicate and justify (within a few sentences) the time complexity of your algorithm. b. [3 marks] Write another algorithm in pseudocode for SumKSmalleast using the transform & conquer paradigm. Your algorithm should strictly run in O(n log n) time. Justify the time complexity of your algorithm. c. [4 marks] Explain with details, how we could implement another SumKSmalleast that strictly runs in less than O(n log n) time, considering k<<n. Demonstrate the time complexity of your approach as a function of n and k.

Answer 1

Note: You have given in question as "Please answer this in python pseudocode. It's an algorithm question." I haven't understood this sentence. So I hereby just providing the algorithm and pseudocode for every approach. If you want python code also, please mention in comments. Thank you.

(1): Brute force method

Algorithm:

1. Initialise sum to 0
2. Iterate the following steps for k times
3. Get the minimum value of array and store it in minValue variable and store the minimun value index in minIndex variable
4. Add the minimum value to sum
5. Update the minimum value index with some maximum value
6. Atlast after completion of K times iteration return sum.

SumKSmallest(A[],k):

• sum=0
• for i=1 to k do
  • minValue=A[0]
  • minIndex=0
  • for j=0 to n-1 do
    • if A[i]<minValue:
      • minValue=A[i]
      • minIndex=i
  • sum=sum+minValue
  • A[minIndex]=9999999
• return sum

Time Complexity of above algorithm: O(k*n)

(2): Transform and Conquer

Algorithm:

1. Initially sort the array
2. initialise sum to 0
3. Then add first k elements and store it in sum variable and return it

SumKSmallest(A[],k):

• sort(A), inbuilt method that sorts the array
• sum=0
• for i=0 to k do
  • sum=sum+A[i]
• return sum

Time complexity of above algorithm: O(nlogn)

(3): Efficient Approach using Max heap approach

Algorithm:

1. In this algorithm, we make use of max heap data structure, where max heap is a partially complete binary tree whose parent value is greater than children values.
2. So initialise a max heap.
3. Iterate from i=0 to n-1 and add every element of array into max heap. While inserting, if max heap size is greater than k, then remove root node of max heap.
4. Continue step-3 till all the values in array are read.
5. Now, we have K smallest elements in max heap.
6. So add all elements of max heap and return its sum.

SumKSmallest(A[],k):

• Initialise a max heap let it be max_heap
• for i=0 to n-1 do
  • max_heap.add(A[i])
  • if max_heap.size()>k:
    • max_heap.remove()
• sum=0
• while(max_heap.isEmpty()):
  • sum=sum+max_heap.remove()
• return sum

Time complexity of above algorithm : O(nlogk)

Because at any time height of max heap is logk because, we will have at max of k elements in max heap. In first loop, we iterate from i=0 to n-1 which means "n", and for each insertiion and deleteion it takes logk time. So final time complexity is O(nlogk).

Mention in comments if any mistakes or errors are found. Thank you.