CMSC 100, FALL 2012
ALGORITHMS - PSEUDOCODE SUMMARY AND EXAMPLES

Suggested use:  review the summary of expressions, then
try to write each of the algorithms from the description
in the headers without looking at my answers.  (There are
many different possible solutions; mine are just one
possible way to solve the problem.)  Start with the 
"Basic Algorithms" and work you way up -- they get
progressively harder.  


PSEUDOCODE SUMMARY:

(Remember you don't have to use this EXACT syntax -- as
long as your meaning is clear, and you don't assume that
the computer can "do magic" (by including statements like
"sort the list" or "find the largest value"), I don't care
how you write your pseudocode.)


Variables/values:  
  integers, real numbers, characters, strings, lists
  Boolean values (True/False)
  VAR = VALUE        // assign VALUE to variable VAR

Expressions:  
  +, -, *, /
  X^Y  [raise X to the Yth power]
  X mod Y  [give the remainder of X / Y]
  and, or, not, nor, xor
  == (test for equality), <, <=, >, >=, <> or != (not equal)
  //  Comment (does not get interpreted by the computer!)

Input/Output:
  get    [read a value]
  print

Control:
  if EXPRESSION then { ... }
  if EXPRESSION then { ... } else { ... }
  end   // end the algorithm (don't continue to the next statement)

Loops:
  while EXPRESSION do { ... }
  until EXPRESSION do { ... }
  do { ... } while EXPRESSION
  do { ... } until EXPRESSION
  for <x> in <list> do { ... }
  for <x> from <min> to <max> do { ... }



BASIC ALGORITHMS


// PRINT NUMBERS FROM 1 to N

  get (N)
  for i from 1 to N {
    print (i)
  }



// PRINT EVEN NUMBERS FROM 2 TO N

  get (N)
  for i from 1 to (N/2) {    // Note:  "/" should truncate if N is odd
    print (i*2)
  }



// PRINT NUMBERS FROM 1 TO N, WITH A NEW LINE AFTER EVERY 10
// NUMBERS

  get (N)
    for i from 1 to N {
        print (i)
        if ( (i mod 10) == 0 ) {    // or: "if i is evenly divisible by 10"
            print (Newline)
        }
    }



// PRINT A LIST IN REVERSE ORDER, TAKE ONE
// Method number one:  Count upwards, and compute the
// list index in reverse

  get (List)
  for i from 1 to length(List) do {
    print (List[N-i+1])     // or:  "print the ith number from the end of the list"
  }



// PRINT A LIST IN REVERSE ORDER, TAKE TWO
// Method number two:  Count down from N to 1, using a
// while loop

  get (List)
  i = length(List)
  while ( i > 0 ) {
    print (List[i])
    i = i-1
  }



// ANALYZE A LIST:
// Print the number of negative numbers, the number of zeros,
// and the number of positive numbers in the list.

  get (List)
  count1 = 0
  count2 = 0
  count3 = 0
  for i from 1 to length(List) do {
    if ( List[i] < 0 ) then {
      count1 = count1 + 1
    } else if ( List[i] == 0 ) then {
      count2 = count2 + 1
    } else {
      count3 = count3 + 1
    }
  }
  print (count1, count2, count3)
}



// COMPUTE INTEREST ON A LOAN
// Compute compound interest on an investment
// Prints balance after each month

  get (Principal, Rate, Months)  
  print ("Initial investment: ", Principal)
  for i from 1 to Months do {
    Principal = Principal * (1 + Rate)
    print ("After", i, "months, balance is", Principal)
  }
  


// AVERAGE A LIST OF NUMBERS

  get (List)    // User should enter a list of numbers
  Sum = 0
  loop for i from 1 to Length(List) do {
    Sum = Sum + List[i]
  }
  print (Sum / Length(List))



// LINEAR SEARCH, TAKE ONE
// Find a number by looking through a list.  If found,
// print the location (index).

  get (List, Value)
  for i from 1 to Length(List) do {
    if ( List[i] == Value ) do {
      print (Value, " found at index ", i)
    }
  }
 


// LINEAR SEARCH, TAKE TWO
// Find a number by looking through a list.  If found,
// print the location (index) *and stop looking*.  
// If not found anywhere, print "not found."
// This algorithm uses what's called a "sentinel value"
// or "flag" to indicate when the loop should stop

  get (List, Value)
  Found = false
  i = 1
  while ( ( not Found ) and ( i <= Length (List) ) ) do {
    if ( List[i] == Value ) do {
      print (Value, " found at index ", i)
      Found = true
    }
    i = i + 1
  }
  if ( not Found ) do {
    print (Value, " not found in list")
  }



// SMART LINEAR SEARCH (TAKE THREE)
// Same as linear search but assumes list is ordered,
// so stop after you get higher than the number you're
// looking for.  Print location if found, and "not found"
// otherwise.

  get (List, Value)
  i = 1
  while ( ( i <= length (List) ) and ( List[i] < Value ) ) do {
    i = i + 1
  }

  // When we get here, either i is the location of the value, or
  // i is one greater than the length of the list!

  if ( ( i <= Length (List) ) and ( List[i] == Value ) ) do {
      print (Value, " found at index ", i)
  else {
    print (Value, " not found in list")
  }



// MAKE CHANGE FOR A PURCHASE
// Procedure that prints how much of each type of change
// to give for a payment over the amount due
// Due and Paid are in cents (e.g., $2.50 would be the value 250)

  get (Due, Paid)   // Due: amount due, Paid: amount paid (in cents!)
  if (Paid < Due) {
    print ("You owe ", Due, " but you only paid ", Paid, "!")
  } else {
    Change = Paid - Due
    //Largest bill available: $20
    // Figure out how many $20 bills to give, and subtract that
    if ( Change >= 2000 ) {
      print ("You get ", Truncate (Change / 2000), " $20 bills")
      Change = Change - 2000 * Truncate (Change / 2000)
    }
    // Repeat for all smaller bills/coins!
    if ( Change >= 1000 ) {
      print ("You get ", Truncate (Change / 1000), " $10 bills")
      Change = Change - 1000 * Truncate (Change / 1000)
    }
    if ( Change >= 500 ) {
      print ("You get ", Truncate (Change / 500), " $5 bills")
      Change = Change - 500 * Truncate (Change / 500)
    }
    if ( Change >= 100 ) {
      print ("You get ", Truncate (Change / 100), " $1 bills")
      Change = Change - 10 * Truncate (Change / 10)
    }
    if ( Change >= 25 ) {
      print ("You get ", Truncate (Change / 25), " quarters")
      Change = Change - 25 * Truncate (Change / 25)
    }
    if ( Change >= 10 ) {
      print ("You get ", Truncate (Change / 10), " dimes")
      Change = Change - 10 * Truncate (Change / 10)
    }
    if ( Change >= 5 ) {
      print ("You get ", Truncate (Change / 5), "nickels")
      Change = Change - 5 * Truncate (Change / 5)
    }
    if ( Change >= 1 ) {
      print ("You get ", Change, "pennies")
    }
  }



// (*)CHECK WHETHER THREE NUMBERS ARE THE SAME 
// Given three numbers, print either "All same" (if they
// are all the same), "All different" (if no two are the
// same), or "One pair" (if two are the same, and the third
// is different)

  get (x, y, z)
  if ( x == y ) {
    if ( y == z ) {
      print ("All same")
     } else {
      print ("One pair")
     }  // end inner "if"
    } else {   // outer if -- so x != y
      if ( y == z ) {
        print ("One pair")
      } else {
        print ("All different")
      }
    }



// (*)FIND THE STUDENT WITH THE HIGHEST GRADE
// Given two lists -- one with names and one with grades --
// print the name and grade of the student with the highest
// grade.

  get (Names, Grades)   // Names and Grades should be the same length!
  max = 0    // lowest possible grade
  for i from 1 to length(Names) do {
    if ( Grades[i] > max ) {
      max = Grades[i]  // remember top grade (so far)
      maxIndex = i     // keep track of which student is top (so far)
    }
  }
  print ("Top student: ", Names[maxIndex], "; grade: ", Grades[maxIndex]);



// (*)CHECK WHETHER A LIST IS PALINDROMIC
// "Palindromic" means "reads the same forwards and backwards."
//  Print "Yes" if it is, and "No" if it isn't

  get (List)
  bottom = 1
  top = length(List)

  // Count up from 1 with "bottom" and down from end of list with "top"
  // When "bottom" becomes as big or greater than "top", we've
  // crossed in the middle.  As soon as we see a mismatch
  // between List[bottom] and List[top], we know the list isn't
  // palindromic.
  while (top > bottom) {
    if (List[bottom] != List[top]) {
      print ("No")
      end   // halt the algorithm
     }
    top = top - 1
    bottom = bottom +1
  }
  // If we get here without returning, the list was a palindrome
  print ("Yes")