15-105 PRACTICE PROBLEMS - EXAM 3 - SPRING 2009

Use these problems to get an idea about the format for the actual exam and the level of difficulty of the exam questions. The actual exam may or may not have problems that look like these problems, but the amount and difficulty of the problems will be similar. Note that there are additional topics in the course material that you should study that are not included in the problems below.

  1. Consider the following algorithm that computes the sum of the first n non-negative powers of 2: 20 + 21 + ... + 2n-1, where n ≥ 1. 

    1. Input n (assume n ≥ 1)
2. Set sum to 1 
3. Set value to 2 
4. Do the following n-1 times: 
   a. Add value to sum 
   b. Multiply value by 2 
5. Output sum

    1. Counting assignments ("Set ..."), additions and multiplications as operations, exactly how many operations does the algorithm perform in terms of the variable n?

    2. What is the order of complexity of this algorithm in big O notation? Explain your answer.

    3. Use induction to show that the sum that is computed in the algorithm is also equal to 2n-1, n ≥ 1. HINT: Show that the sum is 2n-1 when n = 1. Then show that if the sum is 2n-1 for some n, then the sum = 2n+1-1 for n+1.

    1. Determine a set of boolean values that can assigned to the four variables in the following logical sentence so that it is satisfied (i.e. it evaluates to true), or explain why no assignment is possible.

      (A v B) & (C & ~D) & (A --> C)

    2. If a logical sentence has N boolean variables, at most how many boolean assignments need to be tested for a solution to this satisfiability problem? Explain.

    3. What does your solution to (b) say about the computability of these types of problems?

  3. Let V be a universal virus checker that takes some input program P and determines if P will spread a virus or not.

    1. Explain why this problem is classified as a "decision problem".

    2. Let F be a program that works as follows with an input program P: 

      Run V with program P as its input. 
If V responds that P will spread a virus:  
   output DONE without spreading a virus 
Otherwise: 
   spread a virus

      What happens if F is executed with itself as input?

    3. What does the result of (b) say about the existence of program V?

  4. Consider the following Turing machine:

    1. For each of the following initial tape configurations, what is the final state of the tape if the machine head starts with the rightmost non-blank cell? 

      ...#####101010#####... 
 
...#####1111#####...

    2. Where does the tape head always stop?

    3. In one sentence, state what this Turing machine is computing.

  5. The following questions involve computing concurrently.

    1. A parallel computer has 60 processors. A program run on a single processor sequentially takes 1 hour. What is the fastest time we would expect our program to run if it were run on the parallel computer, ignoring any overhead due to controlling the parallelization? What if only 1/2 of the program can be run in parallel on the 60 processors?

    2. Assume it takes t time units to perform a single assignment operation on a single computer processor, and we wish to compute the following sequence of 5 assignment operations: 

      A <-- A + 1 
B <-- B + 2 
C <-- C + 3 
D <-- D + 4 
E <-- E + 5

      Briefly explain how a single processor can execute all five assignment instructions in less than 5t time units.

    3. Consider computer X communicating with another computer Y. X transmits one packet at a time, waiting until it receives an acknowledgement from Y for each packet before sending the next packet. Y receives one packet at a time, sending an acknowledgement back to X for each packet. Suppose one of the acknowledgements is lost from Y on its way to X. Explain what happens in this situation using this simple protocol.