Question: Write pseudocode for an algorithm that solves this problem in O(n) time. Consider the following problem: Input: an array A with n distinct numbers (no

Write pseudocode for an algorithm that solves this problem in O(n) time.

Consider the following problem: Input: an array A with n distinct numbers (no duplicates), and an array B with the same n numbers in a different order. The numbers in A and B can be positive or negative. Output: the goal is find the number whose position in A is most similar to its position in B. Formally, say that a pair (i, j) is related if A[i] = B[j]; we want to find the related pair that minimizes lj i, where lj i| denotes the absolute value. If there multiple pairs that minimize lj i, you only have to return one of them. So for example if A 1, 3, 9, 7, 2, -8,6 and B = 2,6, -8,1,9, 3, 7 then the closest related pair is (2, 4) because A[2] = B[4] = 9 and 12 41 = 2; it is easy to check to for every other related pair (i, j) we have lj il > 3. Write pseudocode for an algorithm that solves this problem in O(n) time. No need for a justification; just pseudocode is enough

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer

Step: 1 Unlock blur-text-image

Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock

Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!

Write pseudocode for an algorithm that solves the above problem in O(n^2 ) time. Say that you have n people p, Pn. Some pairs of people are friends. To represent friendship friendships we have sets...

Consider the following problem. Input: n 2 distinct numbers in some arbitrary order. Output: an n n matrix containing the input numbers, and having all rows and all columns sorted in increasing...

Select (A: Array [1..n] of distinct integers, k: integer between 1 and n) 1 for i=n down to k 2 position=i 3 for j=1 to (i1) 4 if A[j]>A[position] then position=j 5 if positioni then 6 temp=A[i] 7...

please help!! Problem 2. (30 points) Let A[1..n] be a sorted array of distinct integers. You want to find out if there is an index i such that Ai - i algorithm that solves this problem and runs in...

3 Problem 3 (25 points total) Let A be some array of n numbers, with no duplicated elements, and re- call that Rank(x)- k if x is the kth smallest element of A. Now define InverseRank(x)-n 1-...

3 . Assume that you have an unlimited supply of coins with integer denominations d 1 , d 2 , d 3 , . . . , dN . In this problem, the denominations are not sorted. We wish to make change for a value...

A. Define the entries of your table in words. E.g. T(i) or T(i, j) is... B. State recurrence for entries of the table in terms of smaller subproblems. C. Write PSEUDOCODE for your algorithm to solve...

How can more disclosure in the notes to the financial statements facilitate the analysis of foreign financial statements?

Southeastern Steel Company (SSC) was formed 5 years ago to exploit a new continuous casting process. SSCs founders, Donald Brown and Margo Valencia, had been employed in the research department of a...

Problem 1 ( 3 0 points ) : ( Box method ) Assume you hold an equally - weighted portfolio of N = 1 0 0 stocks. ( i . e . ) . Variances of individual stock are the same and equal to ' = 8 . Assume all...

On January 15, the end of the first pay period of the year, North Company's employees earned $30,000 of sales salaries. Withholdings from the employees' salaries include FICA Social Security taxes at...

In addition to patterns of interaction, in what ways are organizational structure and strategy responsible for the managerial climate?

What would be an example of line responsibilities that have been inappropriately assumed by a staff function? What would it take for the line operations to reclaim their appropriate role?

Employee participation in organizational decision making was, as McGregor reports, viewed with skepticism at the time he was writing. Is it now more widely valued and utilized? If so, why? If not,...