5. (a) (5 points) Suppose we are given a sequence S of n elements, each of which
ID: 3915770 • Letter: 5
Question
5. (a) (5 points) Suppose we are given a sequence S of n elements, each of which is colored red or blue. Assuming S is represented by an array, give a linear-time in-place algorithm for ordering S so that all the blue elements are listed before all the red elements. What is the running time of your method? (b) (5 points) Let A and B be two sequences of n integers each. Give an integer m, describe an O(n logn time algorithm for determining if there is an integer a in A and an integer b in B such that m-a b.Explanation / Answer
5(a) To segregate all the blue and red elements, we can devise a linear time algortihm using the below given method. For this algorithm let us assume, 0 represents Blue color and 1 represents Red color. Here are the steps of the algorithm:
Step 1: Let left_index = 0 and right_index = n-1
Step 2: Do the following steps while left_index < right_index
Step 3: If S[left_index] has 0 in it, then increment left_index by 1.
Step 4: If S[right_index] has 1 in it, then decrement right_index by 1.
Step 5: If left_index < right_index, then swap S[left_index] with S[right_index].
Here is the implementation of the following algorithm in C++:
#include<iostream>
#include<vector>
#include<algorithm>
int main()
{
std::vector<int> S = {0, 1, 0, 1, 1, 1};
int n = S.size();
std::size_t left_index = 0;
std::size_t right_index = n-1;
while (left_index < right_index)
{
while (S[left_index] == 0 && left_index < right_index)
left_index++;
while (S[right_index] == 1 && left_index < right_index)
right_index--;
if (left_index < right_index)
{
std::swap(S[left_index], S[right_index]);
left_index++;
right_index--;
}
}
for (std::size_t i = 0; i < S.size(); i++)
std::cout << S[i];
return 0;
}
The time complexity of the above algorithm is O(n) and space complexity is O(1)
______________________________________________________________________
5(b) To find an algorithm which can find m = a+b, where a belongs to A and b belongs to B, we can use following steps:
Step 1 : Sort both the arrays, A and B. This can be done in O(nlogn) time using Heap Sort/ Quick Sort.
Step 2 : For each and every element in array A, we need to find element (m-A[i]) using binary search. This will take O(n) time to traverse array A and O(logn) time for performing binary search.
Step 3 : If such an element is found then return true else return false.
Here is the implementation in C++:
#include<iostream>
#include<vector>
#include<algorithm>
int main()
{
std::vector<int> A = {1, 0, -4, 7, 6, 4};
std::vector<int> B = {0 ,2, 4, -3, 2, 1};
int m = 10;
std::sort(A.begin(),A.end());
std::sort(B.begin(),B.end());
bool is_present = false;
for (std::size_t i = 0; i < A.size(); i++)
{
int remaining_value = m-A[i];
if(std::binary_search(B.begin(), B.end(), remaining_value))
{
is_present = true;
break;
}
}
if(is_present)
std::cout << "Pair Present ";
else
std::cout << "No Pair Present ";
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.