eduardo (11) OBEIplay: × Assignments × Upload Assigmxy-Upload Assigmx Y Program2

Question

eduardo (11) OBEIplay: × Assignments × Upload Assigmxy-Upload Assigmx Y Program2pdf × Chegg.com ×Y G write a classe This Assignmex Secure l https://blackboard.kean .edu/webapps/assignment/uploadAssignment?content_id--749142-1&course;, id--5708718assign_group_id=&mode-view; w.et / C Please accomplish these problems in JavaScript with HTML. These problems are to refresh your memory with array, functions and sorting a little bit. I have provided the hints accordingly. After Spring break we will move back to Server Side programming starting with Chapter 17 (Apache and Microsoft IIS Express) So the problems are mentioned below Library Problem-1 Bb Technical Support Let A and B two arrays of n elements, each. Given a number K, give an Ofnlogn) time algorithm for determining whether there exists a E A and bE B suck that a Hints: 1. Use Heapsort(A, n) or Quicksort(A) 2. Take Advantage of BinarySearch) Problem-2 There are two sorted arrays A and B. First one is of size mn containing m elements and another one is of size n and containing n elements. Merge these two arrays into the first array of size mn such that the output is sorted. Hints 1. Trick is to start filling the destination array from the back with the largest elements. Problem-3 Given an array A of n elements. Find three elements i, j and k in the array such that A Hints: 2-A 2- 1. Use Heapsort(A, n) 2. For each array index i compute All and store in array 3. Search for two numbers in array from 0 to i-1 which adds to A). ASSIGNMENT SUBMISSION Text Submission Write Submission

Explanation / Answer

Problem-1.

#include <iostream>
using namespace std;

void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}

/* This function takes last element as pivot, places
the pivot element at its correct position in sorted
array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right
of pivot */
int partition (int arr[], int low, int high)
{
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element

for (int j = low; j <= high- 1; j++)
{
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot)
{
i++; // increment index of smaller element
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}

void quickSort(int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[p] is now
at right place */
int pi = partition(arr, low, high);

// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// function to search 'value' in the given array
// 'arr[]' it uses binary search technique as
bool isPresent(int arr[], int low, int high, int value)
{
while (low <= high)
{
int mid = (low + high) / 2;

if (arr[mid] == value)
return true;   

else if (arr[mid] > value)   
high = mid - 1;
else
low = mid + 1;   
}
return false;
}

bool findPair(int arr1[], int arr2[], int m,
int n, int x)
{
int count = 0;   
for (int i = 0; i<m; i++)
{
int value = x - arr1[i];

if (isPresent(arr2, 0, n-1, value))
return true;
}

return false;
}

// Driver program to test above
int main()
{
int arr1[] = {1, 3, 5, 7};
int arr2[] = {2, 3, 5, 8};
  
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
quickSort(arr1,0,m-1);
quickSort(arr2,0,n-1);
int k = 10;
//checking if there is a pair in arr1 and arr2 where sum is k
bool res = findPair(arr1, arr2, m, n, k);
if(res){
cout<<"Pair found";
}
else{
cout<<"No pair found";
}
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.