Results 1 to 5 of 5

Math Help - Algorithm Question

  1. #1
    Newbie
    Joined
    Aug 2007
    Posts
    2

    Algorithm Question

    Hi guys,

    Took an exam back in June which dealt mainly with algorithms, however I never really put the time into the module so the exam was beyond me at times. Was just wondering if anyone could spare the time to check out a few of the questions I came up against, as I've got a retake around the corner and can't seem to get my head around them. Probably very trivial to you guys!

    Ok, here it goes..

    1) Write an algorithm which calculates both the maximum and minimum of a non-empty array A[1...n]. Examples of its application:

    Input:
    [3,7,0]
    [10,11,2,1]

    Output:
    7 0
    11 1

    When writing the algorithm you are allowed to use only once occurrence of a looping construct; that is one for loop or once occurrence of a while loop.

    and,

    2) Given a non-empty array of numbers A[1....n], the running max of A is an array M[1...n], in which the slot M[i] contains the maximum of the subarray A[1...i]. Examples:

    Input: A
    [10,7,2,11]
    [9]
    [3,2,6,5,1]

    Output: M
    [10,10,10,11]
    [9]
    [3,3,6,6,6]

    Write an algorithm, in the complexity class Θ(n), which inputs an array A[1....n] and outputs the running max of A.

    Also, why is the algorithm in class Θ(n).

    Any kind of help would be much appreciated,

    Cheers!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Aug 2007
    From
    USA
    Posts
    3,111
    Thanks
    2
    Why is 1) hard?

    First Pass
    A) Read the first value. 3
    B) Put it in both places of your MaxMin vector [3,3]

    Subsequent Passes
    A) Read the next value. 7
    B) If it exceeds MaxMin(1), replace it [7,3] <== Replacement
    C) If it exceeded by MaxMin(2), replace it [7,3] <== No action

    That's it.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Algohelp View Post
    Hi guys,

    Took an exam back in June which dealt mainly with algorithms, however I never really put the time into the module so the exam was beyond me at times. Was just wondering if anyone could spare the time to check out a few of the questions I came up against, as I've got a retake around the corner and can't seem to get my head around them. Probably very trivial to you guys!

    Ok, here it goes..

    1) Write an algorithm which calculates both the maximum and minimum of a non-empty array A[1...n]. Examples of its application:

    Input:
    [3,7,0]
    [10,11,2,1]

    Output:
    7 0
    11 1

    When writing the algorithm you are allowed to use only once occurrence of a looping construct; that is one for loop or once occurrence of a while loop.

    and,
    Ask your self what is difficult about:

    Code:
    read n, A[1..n]
    lo = maxint
    hi = minint
     
    for idx=1 to n
      if A[idx]<lo
         lo=A[idx]
      endif
      if A[idx]>hi
         hi=A[idx]
      endif
    endfor
     
    return {lo,hi}
    end
    Then let us know and we can address your real problem

    RonL
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Algohelp View Post
    2) Given a non-empty array of numbers A[1....n], the running max of A is an array M[1...n], in which the slot M[i] contains the maximum of the subarray A[1...i]. Examples:

    Input: A
    [10,7,2,11]
    [9]
    [3,2,6,5,1]

    Output: M
    [10,10,10,11]
    [9]
    [3,3,6,6,6]

    Write an algorithm, in the complexity class Θ(n), which inputs an array A[1....n] and outputs the running max of A.

    Also, why is the algorithm in class Θ(n).
    This is more interesting

    Observe that M[1]=A[1], and M[k]=max(M[k-1],A[k]), n>=k>1.

    It will be of complexity class \Theta(n) as there are exactly n-1 comparisons and assignmets made in the process. So the run time t=C+A(n-1) for some real constants C and A. Then for n large enough:

    An<t<2An

    which is all you need to proove this.

    RonL
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Aug 2007
    Posts
    2
    Thanks for the help CaptainBlack,

    Regarding the first solution I can see exactly what it wants me to write, and I can write most of it, but I never feel very confident with my solution once I've written it. I still have a few problems with basics. Anyway as I say I really didn't put anytime in the module and some of the trivial questions seem harder than they should without someone to point out the obvious, so that's why I posted those up just to work through as a starting point. Have a retake in a few days and I'm gonna attempt some other questions and post the answers up here. Would appreciate if you could tell me if they're right or wrong when I do!

    Cheers again.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] algorithm Question
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: December 6th 2010, 12:30 PM
  2. Division Algorithm question
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: October 26th 2010, 06:42 PM
  3. Euclid's algorithm question
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 2nd 2009, 11:02 AM
  4. Algorithm question
    Posted in the Math Topics Forum
    Replies: 8
    Last Post: August 5th 2009, 06:19 AM
  5. Simple log question for algorithm
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: May 28th 2009, 03:15 PM

Search Tags


/mathhelpforum @mathhelpforum