I'm working on an assignment for my algorithm class and I need help with the following questions. Note. When asked to give an algorithm that meets a certain time bound, you need to give the algorithm (pseu-docode/description) and analyze its running time to show that it meets the required bound.

 

1. Given a collection of n nuts and a collection of n bolts, arranged in an

increasing order of size, give an O(n) time algorithm to check if there

is a nut and a bolt that have the same size. The sizes of the nuts and

bolts are stored in the sorted arrays NUTS[1::n] and BOLTS[1::n],

respectively. Your algorithm can stop as soon as it nds a single match

(i.e, you do not need to report all matches).

 

 

2. Let A[1::n] be an array of distinct positive integers, and let t be a

positive integer.

 

(a) Assuming that A is sorted, show that in O(n) time it can be

decided if A contains two distinct elements x and y such that

x + y = t.

 

(b) Use part (a) to show that the following problem, referred to as

the 3-Sum problem, can be solved in O(n2) time:

3-Sum

Given an array A[1::n] of distinct positive integers that

is not (necessarily) sorted, and a positive integer t, de-

termine whether or not there are three distinct elements

x, y, z in A such that x + y + z = t.

 

3. Let A[1::n] be an array of positive integers (A is not sorted). Pinocchio

claims that there exists an O(n)-time algorithm that decides if there

are two integers in A whose sum is 1000. Is Pinocchio right, or will his

nose grow? If you say Pinocchio is right, explain how it can be done

in O(n) time; otherwise, argue why it is impossible.

 

 

4. Suppose that we are given an array A[1::n] of integers such that

A[1] < A[2] <    < A[n]. Give an O(lg n) time algorithm to decide if

there exists an index 1  i  n such that A[i] = i.

 

 

5. Let A[1::n] be an array of numbers. To nd the largest number in

A, one way is to divide A into two halves, recursively nd the largest

number in each half, and pick the maximum between the two.

 

(a) Write a recursive algorithm to implement the above scheme. Write

a recurrence relation describing the running time of the algorithm

and solve it to give a tight bound on the running time of this al-

gorithm.

 

(b) Does this recursive algorithm makes fewer comparisons than an

incremental algorithm that computes the largest element in A by

iterating through the elements of A? Explain.

ComputerScienceExpert

(11)

Status NEW Posted 25 Apr 2017 07:04 AM My Price 9.00

-----------

Attachments

file 1493107177-Solutions file 2.docx preview (51 words )

H-----------ell-----------o S-----------ir/-----------Mad-----------am ----------- Th-----------ank----------- yo-----------u f-----------or -----------you-----------r i-----------nte-----------res-----------t a-----------nd -----------buy-----------ing----------- my----------- po-----------ste-----------d s-----------olu-----------tio-----------n. -----------Ple-----------ase----------- pi-----------ng -----------me -----------on -----------cha-----------t I----------- am----------- on-----------lin-----------e o-----------r i-----------nbo-----------x m-----------e a----------- me-----------ssa-----------ge -----------I w-----------ill----------- be----------- qu-----------ick-----------ly -----------onl-----------ine----------- an-----------d g-----------ive----------- yo-----------u e-----------xac-----------t f-----------ile----------- an-----------d t-----------he -----------sam-----------e f-----------ile----------- is----------- al-----------so -----------sen-----------t t-----------o y-----------our----------- em-----------ail----------- th-----------at -----------is -----------reg-----------ist-----------ere-----------d o-----------n -----------THI-----------S W-----------EBS-----------ITE-----------. ----------- Th-----------ank----------- yo-----------u -----------

Not Rated(0)

• Buy Answer