text: 1. ## 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!
  
  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.
  
  3. Originally Posted by Algohelp
  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,
  
  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
  
  RonL
  
  4. Originally Posted by Algohelp
  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 $\displaystyle \Theta(n)$ as there are exactly $\displaystyle n-1$ comparisons and assignmets made in the process. So the run time $\displaystyle t=C+A(n-1)$ for some real constants $\displaystyle C$ and $\displaystyle A$. Then for $\displaystyle n$ large enough:
  
  $\displaystyle An<t<2An$
  
  which is all you need to proove this.
  
  RonL
  
  5. 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.
explanation: The document contains a series of posts related to algorithm questions from an exam. The first post presents two algorithm questions and requests help with them. The subsequent posts provide answers and explanations for these questions.
  
  1. The first question asks for an algorithm to find the maximum and minimum of a non-empty array using only one looping construct.
  2. The second question asks for an algorithm to compute the running maximum of a non-empty array and to explain why the algorithm is in the complexity class Θ(n).
  
  The document includes both the questions and detailed answers to these questions.
distilabel_metadata.content: Evaluate the user given text extract and determine if it contains a math question and optionally and answer to this question.
  
  Output rules:
  
  1. Briefly describe the document and mention if it contains a question or a question and answer.
  2. Finalize the output with: Label: no-question,question,question-and-answer,multiple-question,multiple-question-and-answer
distilabel_metadata.role: system
distilabel_metadata.content: 1. ## 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!
  
  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.
  
  3. Originally Posted by Algohelp
  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,
  
  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
  
  RonL
  
  4. Originally Posted by Algohelp
  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 $\displaystyle \Theta(n)$ as there are exactly $\displaystyle n-1$ comparisons and assignmets made in the process. So the run time $\displaystyle t=C+A(n-1)$ for some real constants $\displaystyle C$ and $\displaystyle A$. Then for $\displaystyle n$ large enough:
  
  $\displaystyle An<t<2An$
  
  which is all you need to proove this.
  
  RonL
  
  5. 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.
distilabel_metadata.role: user
distilabel_metadata.raw_output_q_a_detector_0: The document contains a series of posts related to algorithm questions from an exam. The first post presents two algorithm questions and requests help with them. The subsequent posts provide answers and explanations for these questions.
  
  1. The first question asks for an algorithm to find the maximum and minimum of a non-empty array using only one looping construct.
  2. The second question asks for an algorithm to compute the running maximum of a non-empty array and to explain why the algorithm is in the complexity class Θ(n).
  
  The document includes both the questions and detailed answers to these questions.
  
  Label: multiple-question-and-answer