CPS 4 Summer 2002 : Quiz 2

Binary Numbers

For the following questions, assume that a number is represented using a fixed length of eight bits, i.e., 1 or 0, where the bits are organized as shown below, a 1 in a given position means that the given value is active and should be considered when computing the number, a 0 indicates the given value is not active:

sign bit

26

25

24

23

22

21

20

For example, the following represents the number 100 (where 0 represents the + sign and 1 represents the - sign):

0

1

1

0

0

1

0

0

For example, the following represents the number -99:

1

1

1

0

0

0

1

1

1. Write the following decimal numbers in the format given above:
   1. 0
   2. 5
   3. -16
   4. 71
      
2. What is the range of decimal numbers this format can represent?
    
    
    
3. Describe an algorithm that given two numbers in the format given above, reports the number that has the largest value.
    
    
    
   
   
    
   

Describing Algorithms

1. Explain the difference between the syntax of an algorithm and its semantics.
    
    
    
     
   
   
   
2. Explain why sequential search is called an iterative algorithm and binary search is called a recursive algorithm.
   
   
   
   
   
   
   
   
   

Problem Solving

1. Describe an algorithm that, when given an arrangement of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9, rearranges the digits so that the new arrangement represents the next larger value that can be represented by these digits (or reports no such arrangement exists). For example, given the number 5647382901, your algorithm should report back 5647382910.
    
    
    
    
    
    
    
    
    
   
2. You are given two identical marbles and asked to find the highest floor of a 100-story building from which it is safe to drop a marble without breaking it. In other words, you are to find the highest floor X such that if you drop a marble from any floor below the floor X, it will not break; but if you drop it from the floor X, or from any floor above X, the marble will break. In the process of finding floor X, you are permitted to break both marbles. 

   One wants to find this floor X in the least possible number of tries; a try consists in dropping a marble from some floor (if the marble doesn't break, you can use it for the next try, but if it breaks it is not usable anymore). For example, it is trivial to solve the problem using a sequential search, i.e., starting at the first floor, dropping a marble, walking down the stairs to pick it up, going back up to the second floor, dropping the marble again, walking down the stairs to pick it up, etc. In the worst case for this algorithm, when all 100 floors are safe, it will take one hundred tries. This is not the most efficient technique and it does not even use the second marble! However, binary search is also not the best algorithm because in its worst case, when the first 49 floors are safe, it takes 50 tries (explain why).
    
    
    
    
    

   In the worst case scenario, what is the least number of tries? Remember that you have only two marbles to play with!
    
    
    
    
    

   Describe the algorithm you used to find the least number of tries. How can you be certain of your answer?
    
    
    
    
    
   
   
   
   
   
   
   
   
    

3. Extra Credit
   This riddle, one of the world's oldest, is still good for starting arguments. A man is looking at a portrait. "Whose picture is that?" someone asks, and the man replies: "Brothers and sisters have I none, but that man's father is my father's son." At whose picture is the man looking?