CPS 1: Computer Science Fundamentals

J. Forbes
November 16, 2001

Name __SOLUTION________________________ _________

Quiz 8 (10 points)

1. What is an algorithm? (2 points)

   An algorithm is an ordered set of unambiguous, executable steps, defining a terminating process.

2. Assume the information in a telephone book has been placed in a computer memory, alphabetized like in a "normal" phone book by name. We would like to search for a particular phone number.
   1. Write an algorithm using pseudocode to find the a particular phone number in a phone book. (6 points)

      procedure Search(Phonebook, TargetPhoneNo)

      if (Phonebook empty)
        then
          (Declare the search a failure)
          return
        else
          Select the first entry in the phone book as the test entry
          while (test entry's phone number != TargetPhoneNo and
                 there remain entries left to be considered) 
            do (Select next entry in Phonebook as test entry)
      
          if (test entry's phone number == TargetPhoneNo)
            then
              (Declare the search a success)
            else
              (Declare the search a failure)
      

   2. Which algorithmic behavior could we expect from your search program? (N is the number of entries in the phone book.) (2 points)
      1. Logarithmic time (t = C * log N)
      2. Quadratic time (t = C * N² )
      3. Linear time (t = C * N)