##### Question

In: Computer Science

# Design and analyze asymptotically an O(nlgn) transform-conquer algorithm for the following problem: input: an array A[lo..hi]...

Design and analyze asymptotically an O(nlgn) transform-conquer algorithm for the following problem:

• input: an array A[lo..hi] of n real values;
• output: true iff the array contains two elements (at different indices) whose sum is 2020.

## Solutions

##### Expert Solution

# This is a simple C++ solution to the following Problem.

Algorithm:

step1: for each element in array

push occurance of each element in the dictionay

step2: Again for each element in array:

if dictionay[2020-arrary_element] is in the dictionay

print index of the array element

#include <iostream>
#include<bits/stdc++.h>
using namespace std;

int main() {
unordered_map<int, int> m; // creating a dictionary

int n; // array size
cin>>n;
vector<int> arr(n);

// taking array input
for(int i=0; i<n; i++)
{
cin>>arr[i];
}

// storing the occurrence of each element of array in dictionary
for(int i=0; i<n; i++){
m[arr[i]]++;
}

for(int i=0; i<n; i++){
if (m[2020-arr[i]]){
cout<<arr[i]<<" "<<2020-arr[i]<<"\n";
// I an priring the array pairs whose sum is 2020 but according to your requirement
// you can print True/False or index of pairs
}
}
return 0;
}

# Analysis:

The Time complexity of the above program will be O(n), best time complexity

We are traversing the whole array only once

We can use Brout force method for solving the above problem but time complexity will be O(n^2)

But in the above program First we transform whole array in the form of dictionary ( In C++ dictionary refers as map) and then we solve the next subproblem of this problem.

## Related Solutions

##### Divide and conquer approach to find the minimum absolute difference in array A[lo..hi] Input an array...
Divide and conquer approach to find the minimum absolute difference in array A[lo..hi] Input an array A[lo..hi] of n real numbers. Requirement: Shouldn't use a sorting algorithm. Complexity O(nlgn)
##### 5. Design a dynamic programming algorithm to solve the following problem. Input: An array A[1, ....
5. Design a dynamic programming algorithm to solve the following problem. Input: An array A[1, . . . , n] of positive integers, an integer K. Decide: Are there integers in A such that their sum is K. (Return T RUE or F ALSE) Example: The answer is TRUE for the array A = [1, 2, 3] and 5, since 2 + 3 = 5. The answer is FALSE for A = [2, 3, 4] and 8. Note that you...
##### Let A be an integer array of length n. Design a divide and conquer algorithm (description...
Let A be an integer array of length n. Design a divide and conquer algorithm (description and pseudo code) to find the index of an element of the minimum value in the array. If there are several such elements, your algorithm must return the index of the rightmost element. For instance, if A = {0,2,4,5,2,0,3,10}, then the algorithm should return 5, which is the index of the second 0.
##### Design and analyze a divide-and-conquer algorithm for finding the maximum element in a list: L[0: n – 1].
The following submission rules apply:·    For those questions requiring programs, the solutions must be implemented using JavaScript or Java.o Appropriate self-documenting comments in the source code are mandatory, consistent with good programming practices.o Solutions must be provided in plain text so that formatting is not lost.·    All answers must be provided in this document.·    Sources must be given accurate and complete citations sufficient for the instructor to find and confirm them.Design and analyze a divide-and-conquer algorithm for finding the maximum...
##### (a) Implement the following algorithm, which is given a duplicate-free array array as input, in C++....
(a) Implement the following algorithm, which is given a duplicate-free array array as input, in C++. whatDoIDo (array): 1) Build a heap from array (using buildHeap as explained in class), where the heap starts at position array[0]. 2) Starting from j = size of array - 1, as long as j>0: i. Swap the entries array[0] and array[j]. ii. Percolate down array[0], but only within the subarray array[0..j-1]. iii. Decrement j by 1. Provide three input/output examples for duplicate-free arrays...
##### a. Develop a divide-and-conquer algorithm to perform a parallel merge sort of an array. Hint: After...
a. Develop a divide-and-conquer algorithm to perform a parallel merge sort of an array. Hint: After division, each process sorts its part of the array using an efficient algorithm. Then, the subarrays are merged into larger sorted subarrays. b. Analyze the communication and computation times if the number of processes is equal to the number of array elements, n. c. Repeat Part b if the number of processes is less than the number of array elements. Assume that the computation...
##### Given an array of positive integers except one negative integer. Develop a divide-conquer algorithm to find...
Given an array of positive integers except one negative integer. Develop a divide-conquer algorithm to find the index of the negative integer, and compute its average complexity.
##### please write in c++ Algorithm Design problem: Counting inversions: given an array of n integers, find...
please write in c++ Algorithm Design problem: Counting inversions: given an array of n integers, find out the total number of inversions in the given sequence. For example, for the sequence of 2, 4, 1, 3, 5, there are three inversions (2,1), (4,1), and (4,3). Give a brute-force algorithm with running time of O(n^2). Using the technique of divide-and-conquer, design an algorithm with running time of O(nlog n).
##### give an algorithm where given as input an array A[1...n] withthe following property. There exists...
give an algorithm where given as input an array A[1...n] with the following property. There exists an index I such that if we append A[1...i−1] after A[i...n], we get an array in sorted increasing order. For simplicity you can assume that n is a power of 2.Give an efficient algorithm that returns the smallest element in A. Analyze the time complexity of your algorithm.Hint: you may want to compare A[1] and A[n/2].
##### Design an algorithm that will read an array of 200 characters and display to the screen...
Design an algorithm that will read an array of 200 characters and display to the screen a count of the occurrences of each of the five vowels (a, e, i, o, u) in the array. Your string is: The quick brown fox jumped over the lazy dog That is the question for my pseudo code question, I don't know if I have this correct can i have someone look this over and finish this and explain what i needed to...