Follow the pseudo code convention discussed in class, write an algorithm for eac
ID: 3561764 • Letter: F
Question
Follow the pseudo code convention discussed in class, write an algorithm for each problem below. Indent your pseudo codes correctly!
Design an algorithm that takes an array, namely theArray, of n positive numbers, and determines the maximum value of A[j ] + A[i ], for j not equal to i. The algorithm returns the maximum value.
b. Consider three arrays that are populated with integers, e.g., positive, negative, or zero. Design an algorithm that takes three arrays, namely arrayA, arrayB, arrayC, each with size n, and checks if there exists a triple which adds up to zero. The three elements in a triple must come from different arrays. The algorithm returns true if such a triple exists, and false otherwise.
c. Consider sorting n integer numbers stored in array theArray with the following algorithm. The algorithm first finds the smallest element of theArray and exchanges it with the element indexed by 0, and then finds the second smallest element of theArray and exchanges it with the element indexed by 1. The algorithms continues in this matter for n - 1 times before it finishes. The algorithm takes theArray and n as inputs, and doesn't return a value
Explanation / Answer
1)
// Return the maximum sum of two elements in arr whose
// indices differ by at least distance.
int max_distant_sum(int[] arr, int distance) {
if (arr.length <= distance) {
// The array is too small. There is no such sum.
return 0;
}
int max_elem = arr[0];
int max_sum = arr[0] + arr[distance];
for (int i = distance; i < arr.length; i++) {
// max_elem is the maximum value encountered at least
// distance indices previously.
max_elem = max_elem > arr[i-distance] ? max_elem : arr[i-distance];
// max_sum is the maximum allowed sum using elements
// up to index i.
max_sum = max_sum > arr[i] + max_elem ? max_sum : arr[i] + max_elem;
}
return max_sum;
}
2)
Sort the array // O(nlogn)
for each i from 1 to len(array) - 1
iter = i + 1
reviter = len(array) - 1
while iter < reviter
tmp = array[iter] + array[reviter] + array[i]
if tmp > 0
reviter--
else if tmp < 0
iter++
else
return true
return false
3) Selection Sort follows very simple idea.
First it finds the smallest element in the array.
Exchange that smallest element with the element at the first position.
Then find the second smallest element and exchange that element with the element at the second position.
This process continues until the complete array is sorted.
SELECTION-SORT(A)
for j ? 1 to n-1
smallest ? j
for i ? j + 1 to n
if A[ i ] < A[ smallest ]
smallest ? i
Exchange A[ j ] ? A[ smallest ]
Please let me know if you face any difficult and please rate the answer..