1. Question 1: You are given a sorted array of integers. The numbers in the arra
ID: 670001 • Letter: 1
Question
1. 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).
2. 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.
3. 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).
4. 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).
5. 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.
Explain Please. no program!!!
Explanation / Answer
1.
All the elements of the array are distinct in a sorted manner. The approach to find an element of the array such that A[k] = k where k is an index of the array and lies in the range 1<=k<=n and n is the size of the array is a sfollows:
· Create a variable k to store the index of an element of the array such that A[k] = k.
· Start a for loop to traverse the array till the last element of the given array.
· Compare each element of the array to its corresponding index in each iteration.
· If the element is found to be equal to the corresponding index, then store the current index of the array into the variable k and break the for loop.
· Display the value of the variable k which is the index of the element of the array at which A[k] = k.
The pseudocode of the given problem is shown as follows:
Input: An array A[1…n] where n is the size of the array.
Output: The index k at which A[k] = k.
Set k = -1
for i = 0 : n
if A[i] = i
k = i
break
end if
end for
if k != -1
display k
else
display “No index found at which A[k] = k.”
2.
The elements of the array are stored in a manner such that an element will be at some position atmost 20 places far away from its sorted position. It means that an element A[k] can be at a place between A[k – 20] to A[k + 20].
The approach to sort the given array is as follows:
· This problem can be solved by heap data structure.
· Create a min heap of size equals to 21 with first 21 elements.
· Remove the minimum element of the heap one by one and store it into the resultant array.
· An element will be added to the min heap from remaining elements after removing a min element from heap.
The pseudocode to apply the above algorithm is a sfollows:
Input: A[1…n]
Output: A[1…n] in the sorted manner.
Sort(A, size, 20)
//Create a min heap with first 21 elements of the given array.
*heapArr = new int[21];
for i = 0 to i <= k and i < n do
heapArr[i] = A[i];
end for
//Call the minHeap function to create a heap with 21 elements.
minHeap(heapArr, 21)
//Start the for loop for the remaining elements of the array till the target index of //the current minimum element in the min heap is less than the size of the array.
for i = 21, target = 0 to target < n do
//Check if there are remaining elements in the array.
If i < n
//Place the root element of the heap at the target index and add the //current element to the min heap.
A[target] = replaceRoot(A[i]);
Else
//If the current index of the array is greater than size, then remove //the min element from heap and store it at the target index in the //resultant array and reduce the size of the heap.
A[target] = removeRoot();
End for
End
minHeap(arr[], size)
sizeOfHeap = size;
heapArray = arr;
heapifyIndex = (sizeOfHeap - 1)/2;
while heapifyIndex >= 0 do
minHeapifyHeap(heapifyIndex);
heapifyIndex = heapifyIndex – 1;
end while
end
//Heapify the subtree by placing the root element at the given index.
minHeapifyHeap(index)
l = left(index);
r = right(index);
smallestIndex = index;
if l < sizeOfHeap and heapArray[l] < heapArray[index];
smallestIndex = l;
if r < sizeOfHeap and heapArray[r] < heapArray[smallestIndex];
smallestIndex = r;
if smallestIndex != index
swapElements(&heapArray[index], &heapArray[smallestIndex]);
minHeapifyHeap(smallestIndex);
end if
end
swapElements(*a, *b)
swappingElement = *a;
*a = *b;
*b = swappingElement;
end
//Method to swap the root element with the target element and return the previous root element.
replaceRoot(targetElement)
rootElement = heapArray[0];
heapArray[0] = targetElement;
//If root element is less than the target element, then heapify the heap at the index //of root element.
if rootElement < targetElement
minHeapifyHeap(0);
return rootElement;
end
//Remove the root element from the min heap.
removeRoot()
rootElement = heapArray[0];
if sizeOfHeap > 1
heapArray[0] = heapArray[sizeOfHeap – 1];
sizeOfHeap = sizeOfHeap – 1;
minHeapifyHeap(0);
end if
return rootElement;
end
3.
The array has distinct elements and the size of the array is odd. The median of the elements in the array will be (n – 1)/2.
The algorithm introselect can be used to find the kth smallest element in the array in O(n) time. The algorithm divides the input array in the groups of size 5 and apply the quick sort algorithm and median of medians.
The algorithm finds median of meadians of each group and find a pivot element using recursive calls to the function introSelect(). The pseudocode to apply the above algorithm is as follows:
introSelect(Array, size, index)
//Divide the input array into the size/5 group of arrays of size 5
//Apply partition on the median of the medians of each group of arrays.
mid = array of each group’s median
//Find the pivot element of the array.
pivotElement = introSelect(mid, size/5, size/10)
//Make left and right array by portioning the array by pivot element.
Left[] = Right[] = partion(Array, pivotElement)
//Find element at the given index and checks whether it lies in the left array or right //array or it is equal to pivotElement.
k = size(Left) + 1
if index = k, return pivotElement
if index > k, return introSelect(Right, size – k, index – k)
if index < k, return introSelect(Left, k – 1, index)
end
4.
(a).
The algorithms which are based on comparision operations are stable by nature. The merge sort divides the input array till it becomes the size equals to 1 and it sorts the elements of the array by comparing each element in the left and right arrays.
If the index of the current element in the left array is less than the index of the current element in the right array and the elements on both indicies in both left and right subarrat are equal, then the element of the left array will appear before the element of the right array in the sorted order.
Hence, merge sort is stable.
(b).
The way to make an unstable sorting algorithm stable is given as follows:
The positions of the element of an array should also be taken care of in sorting. An sorting algorithm can be made stable by adding a smallest number to each element of the array while sorting.
The order of the same elements in the sorted array will be same as in the original array by comparing each element of the array and checking whether the element at the current index is equal to the element at preciding index, in this case, elements should not be swapped.
5.
The stack and queue of same elements can be implemented by inserting an element into the stack and queue at same time.
The stack and queue should be implemented using double linked list to imolement the given functionality. The structure of the linked list will be as follows:
struct doubleLinked
{
int item;
doubleLinkedList* prev;
doubleLinkedList* next;
}
The push(element) operation will add the element after the last node of the list by modifying the next and prev pointers of the linked list.
The ENQUEUE(element) will also add the element at the qtail of the element.
The POP() operation will delete an element at the last node in the queue using DEQUEUE and the DEQUEUE() operation will remove the element at the queue head from the queue and remove the element at the stack head from the stack using POP() operation. Maintain the stack head, stack tail, queue head, and queue tail.
These operations will take O(1) time because the insertion and deletion operation in both stack and queue will be done by the access to queue head, stack head, queue tail, and stack tail.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.