CS 2104 Problem Solving in Computer Science                    OOC Assignment 5
-------------------------------------------------------------------------------
For each question, design an algorithm that satisfies the stated requirements.  
Express your answer using the pseudo-code notation covered in the course notes 
on Algorithms.  Use descriptive names for your variables, and include comments 
as necessary.  Note:  if you do not use the pseudo-code notation form the course 
notes, we will not grade your submission.
	
1.  [30 points] Design an algorithm that will successively subtract one number 
    from another, zero or more times, until the result becomes negative, and 
    report the number of subtractions that were performed.  If it is impossible 
    to achieve the specified result, the algorithm should detect that and halt.
    
    get First                 # the "first number"
    get Second                # the "second number"
    numOfSubtractions := 0    # haven't done any yet
    
    ## Note:  given the problem statement above, you could subtract First from
    ##        Second, or vice versa; either is acceptable.
    
    # It's only possible to do this if First is already negative or if Second
    # is positive, so:
    if ( First < 0 )
       display numOfSubtractions
       halt
    endif
    if ( Second <= 0 )
       display "Error: cannot achieve desired result"   # error msg is optional
       halt
    endif
    
    while ( First >= 0 )
       First := First - Second
       numOfSubtractions := numOfSubtractions + 1
    endwhile
    
    display numOfSubtractions
    halt
    
	
2.  [30 points] Design an algorithm that will compare three different numbers 
    and return the middle value.  You may assume that the given values are, in 
    fact, all different from each other.
    
    ## Here is one solution, using nested if-else statements:
    ##
    get First          # get the numbers
    get Second
    get Third
    
    if ( First < Second )     # answer depends on where Third fits in
       if ( Third < First )      # order is Third < First < Second
          display First
          halt
       else
          if ( Third < Second )  # order is First < Third < Second
             display Third
             halt
          else
             display Second      # order is First < Second < Third
             halt
          endif
       endif
    else
       if ( Third < Second )     # order is Third < Second < First
          display Second
          halt
       else
          if ( Third < First )   # order is Second < Third < First
             display Third
             halt
          else
             display First       # order is Second < First < Third
             halt
          endif
       endif
    endif
    
    ## Here's another that uses a sequence of un-nested if-else statments
    ## with more complex tests:
    ##
    get First
    get Second
    get Third
    
    if ( First < Second AND Second < Third )  # 123
       display Second
       halt
    endif
    
    if ( Second < First AND First < Third )   # 213
       display First
       halt
    endif
    
    if ( Second < Third AND Third < First )   # 231
       display Third
       halt
    endif
    
    if ( First < Third AND Third < Second )   # 132
       display Third
       halt
    endif
    
    if ( Third < First AND First < Second )   # 312
       display First
       halt
    endif
    
    if ( Third < Second AND Second < First )   # 321
       display Second
       halt
    endif
    
    # We could put a halt here, but the if-else clauses above cover all
    # six possible orderings, so there's no way to reach this point.
    
	
3.  [40 points] Design an algorithm that takes a list of numbers and the number 
    of values in the list, and sums up successive elements from the list, 
    starting at the beginning, until the value -99 is encountered or the end of 
    the list is reached.  The algorithm should then report the average of the 
    values that were summed up (not including the -99 if it was found).  The 
    average of a collection of 0 numbers is 0.
	
    ## The following two statements could be skipped, consistent with the
    ## example in the course notes, but logically they should be here:
    get List       # get data for List
    get listSz     # number of elements in List
    
    if ( listSz <= 0 OR List[1] = -99) # if nothing in list,  or first element
                                       # is sentinel value, then nothing to do
       display 0
       halt
    endif

    sumOfValues   := List[1]           # toss in the first list element
    currPosition  := 2                 # now proceed with the next one
    numElemsAdded := 1                 # processed one element so far
    
    ## We want to keep adding up elements until we finish with the list or
    ## see the sentinel value (-99) and stop:
    while ( currPosition <= listSz AND List[currPosition] != -99)
       sumOfValues  := sumOfValues + List[currPosition]
       numElemsAdded := numElemsAdded + 1
       currPosition := currPosition + 1
    endwhile
    
    ## Now report the results; we don't have to worry about division by zero
    ## because of the checks that preceded the while loop.
    Average := sumOfValues / numElemsAdded
    display Average
    halt