Hey could you provide me with the answers to the following quesitons. Thank you!
ID: 670479 • Letter: H
Question
Hey could you provide me with the answers to the following quesitons. Thank you!
Question 1: You are given a sorted array of integers. The numbers in the array are pairwise distinct, namely no value appears more than once. Your goal is to find if there is an index 1 k n so that A[k] = k. (Assume that the first index is 1).
Question 2: You are given an array A[1..n]. You are given that for every A[i], A[i] is at most 20 places from its sorted position (for example, A[30] will be somewhere between A[10] and A[50] in the sorted array. A[5] will be somewhere between A[1] and A[25] in the sorted array.) Give an efficient algorithm to sort A.
Question 3: Given an odd size array of pairwise distinct elements, the median in the number that is smaller than (n 1)/2 of the elements and larger than (n 1)/2 elements. Say that we have an algorithm that finds the median in time O(n). Give an algorithm to find the k smallest number in time O(n).
Question 4: An algorithm is called stable if elements that are of the same value do not change their order after the sorting. (a) Is Merge-sort stable? (b) Find a way to make any sorting algorithm stable (you can add additional data to every number).
Question 5: Say that we want to maintain both a Stack and a Queue of the same elements. A new element that arrives implies a Push to the stack and a ENQUEUE to the Queue. Any Pop operation should remove the element from the QUEUE and from the Stack as well (even though its not the highest propriety element). Dequeue removes the head of the queue, but also removes this element from the Stack (even though its not the last to being inserted). Using two copies of every element and using additional pointers between element, show that we can implement both a stack and a queue so that every operation requires O(1) time.
Explanation / Answer
Question 1: You are given a sorted array of integers. The numbers in the array are pairwise distinct, namely no value appears more than once. Your goal is to find if there is an index 1 k n so that A[k] = k. (Assume that the first index is 1).
Algorithm:
I/P: Array[1:n]
O/P: k
Set k=-1
For i=0 to n do
If Array[i]==i then
k=i
break
end if
end for
if k!=-1
display ‘index’,k
else
display ‘index not available’
Question 2: You are given an array A[1..n]. You are given that for every A[i], A[i] is at most 20 places from its sorted position (for example, A[30] will be somewhere between A[10] and A[50] in the sorted array. A[5] will be somewhere between A[1] and A[25] in the sorted array.) Give an efficient algorithm to sort A.
Algorithm:
I/P: Array[1:n]
O/P: Array[1:n] in sorted order
For i=0 to n do
Temp=Array[i]
If (i+20) <=n then
Array[i] =Array [i+20]
Array[i+20]=Temp
Else
Array[i] =Array [i+20-n]
Array[i+20-n]=Temp
Endif
End for
Question 3: Given an odd size array of pairwise distinct elements, the median in the number that is smaller than (n 1)/2 of the elements and larger than (n 1)/2 elements. Say that we have an algorithm that finds the median in time O(n). Give an algorithm to find the k smallest number in time O(n).
Algorithm:
I/P: Array[1:n], k
O/P:kth smallest number
L=0
H=n
While (L<=H) do
Median=(L+H)/2
If Median==k then
Display ‘kth smallest number’, Array[k]
Else if Median>k then
H=Median-1
Else if Median<k then
L=Median+1
End if
end
Question 4: An algorithm is called stable if elements that are of the same value do not change their order after the sorting. (a) Is Merge-sort stable? (b) Find a way to make any sorting algorithm stable (you can add additional data to every number).