Using Java

Problem-1

Let A and B two arrays of n elements, each. Given a number K, give an O(nlogn) time algorithm for determining whether there exists a A and b B suck that a + b = K.

Hints:

Use Heapsort(A, n)

Take Advantage of BinarySearch()

Problem-2

Among Quicksort, Selection sort, Insertion sort and Heap sorts which one needs the minimum number of swaps?

Hints:

Go over the class lecture for individual sorting and simulate with an array.

Problem-3

There are two sorted arrays A and B. First one is of size m + n containing m elements and another one is of size n and containing n elements. Merge these two arrays into the first array of size m + n such that the output is sorted.

Hints:

Trick is to start filling the destination array from the back with the largest elements.

Problem-4

Given an array A of n elements. Find three elements i, j and k in the array such that A[i]² + A[j]² = A[k]².

Hints:

Use Heapsort(A, n)

For each array index i compute A[i]² and store in array

Search for two numbers in array from 0 to i-1 which adds to A[i].