-3
$\begingroup$

The following is a pseudo-code named PractOne. It takes a finite list A of real numbers and gives the pair (Alp,Bet), with Alp representing the maximum value of the entry in A and Bet representing the index of Alp in A. Bet is not always unique.

function PractOne(A)
    let Bet = 1
    let Alp = A[Bet]
    for i = 1 to length(A)
        if A[i] > Alp then
        let Bet = i
        let Alp = A[Bet]
    end if
    next i
    return (Alp,Bet)
end function

Please note that the function length (A) takes finite list A=[b_1,..., b_j] and gives the number of elements j in A. Also, A[i] gives the ith element in the finite list A=[b_1,..., b_j].

  1. Create an algorithm (named PractTwo) which takes a finite and non-empty list A of real numbers which are sorted in increasing order and a real number C, if there exists two indices i, j, such that 1<= i<= j<= length(A) and A[i]+A[j]=C, then PractTwo(A,C) gives the pair (A[i],A[j]). When there is a case where more than one pair of indices exists with the required properties, then the function will give one of the valid pairs. Also, if the equality A[i]+A[j]=C is not satisfied for i and j, such that 1<= i<= j<= length(A), then the function will give back an empty pair (,).

    Ensure, PractTwo completes its search with a maximum of d*Length(A) steps, where d>0 is some constant not dependable on on A.

I have an idea...I'm thinking PractTwo requires more steps to factor into it the 1<= i<= j<= length (A), so...

function PractTwo(A)
    let Bet = 1
    let Alp = A[Bet]
    let j = A[i]
    for i = 1 to length(A)
        if A[i] > Alp then
        let Bet = i
        let Alp = A[Bet]
    end if
    next i
    return (Alp,Bet)
end function

I don't think this is complete, is what I've done so far correct?

  1. Also, show that PractTwo gives back the correct value. Also explain how the implementation of PractTwo is completed in at most d*Length(A) steps.
$\endgroup$

closed as unclear what you're asking by David Richerby, Luke Mathieson, Ran G., Nicholas Mancuso, Thomas Klimpel Apr 21 '15 at 7:37

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ This is a problem statement, not a question. If you have a specific question regarding the wording of the problem or about specific steps in your own attempts at solving the problem, feel free to edit accordingly and we can reopen the question. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$ – Raphael Apr 15 '15 at 21:27
  • $\begingroup$ That fact that you were not even able to choose a descriptive title suggests that you don't really understand the task. I don't know what you mean by "where would the loop go" and why there would be two looks. What have you tried, at all? $\endgroup$ – Raphael Apr 15 '15 at 21:28
  • $\begingroup$ Since this is a pretty standard exercise problem I'm quite sure we've discussed it before, but I can't find it right now. $\endgroup$ – Raphael Apr 15 '15 at 21:33
  • $\begingroup$ Ok, thank you for your comments, I will take a look at the links you have provided, if you do find a similar exercise problem which has been discussed please post the link here. Thank you $\endgroup$ – Dalokey Apr 15 '15 at 21:42
3
$\begingroup$

PractOne seems ok. Could be very slightly improved by starting the loop at 2.

PractTwo is wrong, even without considering what it is supposed to do. You write (line 4) : let j = A[i], but i is undefined. I have no idea what you are trying to do.

You have to find A[i] and A[j] in linear time. Linear time is the requirement to use at most d*Length(A) steps.

Achieving linear time requires being a bit more subtle in the computation. You use the fact that the array is sorted in increasing order. You start looking for A[i] starting from one end (say from small indices), and looking for A[j] from the other end (say from large indices), until i meets j, stopping before if you find a solution. Sometimes you increase i and sometimes you decrease j depending on whether the last sum A[i]+A[j] was greater or smaller than C.

I let you work it out in more details, and do the explanation.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.