CPS 4 Summer 2002 : Quiz 1

1. A shampoo bottle has the following instructions:
   1. Lather.
   2. Rinse.
   3. Repeat.

   Which of the following additions would make these instructions into a proper algorithm?

   1. Explain the term "lather" more precisely, but not necessarily "rinse"
   2. Change the last step, "repeat", to "repeat once, then stop"
   3. Both A and B
   4. Neither A nor B --- shampoo bottles do not have algorithms, only computer programs
       
2. Suppose that you have 10 loads of laundry, one washer, and one dryer. Washing a load takes 25 minutes, drying a load takes 25 minutes, and folding the clothes in a load takes 10 minutes, for a total of 1 hour per load (assuming that the time to transfer a load is built into the timings given). All the laundry can be done in 10 hours, 600 minutes, using the method of completing one load before starting the next one. What is the fastest time in which the laundry can be done?
   1. 250 minutes
   2. 275 minutes
   3. 285 minutes
   4. 300 minutes
        
3. In which case would sequential search be faster than binary search?
   1. You know the answer is at the front
   2. You know the answer is exactly the middle
   3. You know the answer is at the end
   4. Never, binary search is always better
       
4. When does binary search not work?
   1. When the collection is sorted in reverse order
   2. When the collection has an even number of elements
   3. When the collection is not sorted
   4. Never, binary search always works
       
5. Design an algorithm that, given two strings of characters, tests whether the first string appears as a sub-string somewhere in the in the second. Your algorithm should report positively (or true) if there exist one or more occurrences of the first string within the second, and negatively (or false) otherwise. For example, given the two strings "up" and "super duper", your procedure should report that it is true the string "up" appears within the string "super duper". On the other hand, given the two strings "down" and "super duper", you procedure should report false.
   

   For the following questions, consider the algorithm below that characterizes the behavior of a student registering for classes. Assume that the student must take at least 4 credit hours to be a full-time student and may take up to 5.5 credit hours.

   1. Make a list of courses for which you want to register.
   2. Label the courses with a priority, giving priority 1 to your highest priority course and priority 10 to your lowest priority course.
   3. Create a number called "Hours Scheduled."
   4. Begin with an empty schedule: Record 0 for "Hours Scheduled."
   5. Choose the highest priority class on the list.
   6. If (the chosen class is not full) and (its class time does not conflict with classes already scheduled) then register for class:
      1. Add the class to your schedule.
      2. Add the class hours to the "Hours Scheduled."
   7. Cross the class off of your list.
   8. Repeat steps 5 through 7 until ("Hours Scheduled" is greater than or equal to 4) or (all classes have been crossed out).
       
6. Under what circumstances will this algorithm complete without allowing you to take a full load?
   1. You only choose to prioritize 8 possible courses
   2. All your possible courses are already full
   3. Some of your courses have lab times that conflict with times of course you have already registered for
   4. Courses are being offered by professors you do not like
       
7. True or False
   Assuming courses can only be one-half or one credit hour, it is not even possible to register for 5.5 credit hours!
    
8. Extra Credit
   Describe a procedure for filling a barrel with exactly eight gallons of water given only two buckets: one that holds exactly seven gallons of water and one that holds exactly six gallons. Do it without wasting any water.