Example final questions

This is not a practice final, but rather just a collection of assorted questions based on exams from previous years, illustrative of the types of questions that will be asked. Since they are from previous years, and the course has been updated this year, they don't cover all of the material the final will; likewise, I dropped a number of previous questions on material we didn't cover. Some of these are relatively short answer, and some require a bit more, so their point values would vary.

  1. What is "abstraction" and why is it useful in the material that we've covered? Provide a concrete example.
  2. Give a precise definition of the term "algorithm".
  3. Briefly describe what overall task is accomplished by the following algorithm. For full credit, your solution must do more than simply recap the steps of the algorithm. 
    to doSomeTask given A[], i:
1.  Set j to i
2.  While i < A.length do
3.    If A[i] < A[j] then
4.       Set j to i
      End of conditional
5.    Add 1 to i
    End of loop
6.  Halt and return j
  4. Same as previous question, for the following algorithm. Your description should specify under what circumstances the algorithm returns the value true, and when it returns the value false. 
    to doSomeTask given A[]:
1.  Set i to 0
2.  While i < A.length-1 do
3.    If A[i] > A[i+1] then
4.      Halt and return false
      End of conditional
5.    Increment i
    End of loop
6.  Halt and return true
  5. Using the algorithm notation from the class notes, write an algorithm called numDuplicates that behaves as follows: Given an array A[] in sorted order, numDuplicates computes the total number of duplicate values in the array. For example, if A = [1,2,2,3,3,3,4], then there is one duplicate of 2 and there are two duplicates of 3, so numDuplicates would return a total of three. For full credit, your algorithm should not modify A or create another array.
  6. Using the algorithm notation from the class notes, write an algorithm findSecondLargest that behaves as follows: Given an array A, it will return the second-largest value in the array. So, for example, if A = [3, 9, 2, 1, -8, 10, 6, 5], it would return 9. You may assume that A contains numbers.
  7. Using the algorithm notation from the class notes, write an algorithm scaleValues which behaves as follows: Given an array M, scaleValues will find the largest and the smallest values in the array, compute their average, and then divide each element of the array by this average, replacing each element with the result of the division. The algorithm should then halt and return the average of the largest and smallest values computed in the first part.
  8. Using the algorithm notation from the class notes, write an algorithm doReverse which behaves as follows: Given an array A, doReverse will re-arrange the elements of A "in-place" (within A itself) so that they are in the reverse of their original order.
  9. Trace the execution of the binary search algorithm given in class for the input array A = [1,4,6,3,5,7], when searching for the value 4. Specifically, write for each iteration the value of low, mid, high, and A[mid].
  10. When should you use binary search rather than sequential search? In those cases where you should use binary search, why is it generally faster than sequential search?
  11. Pick two positive numbers smaller then 100. Write them in binary, and perform binary addition on them, showing carry bits. To verify your answer, compute the decimal value of the sum. If you want exercise more, just change the numbers and repeat.
  12. Provide three different answers to the question "What number is represented by the bits 10101010?" Justify your answers.
  13. What is "Two's complement"? Is this the only way to represent negative integer values in binary? If there is more than one way to do so, how does the computer know which one to pick?
  14. How is text represented in binary?
  15. What is the largest integer you can represent with 4, 8, and 16 bits?
  16. Convert the following decimal numbers to signed mantissa and exponent with 7 bits for the mantissa and 7 bits for the exponent: (a) 12.5; (b) -7.125; (c) 0.0625
  17. Write the truth table and draw a circuit to do the following. There are three inputs, A, B, and C, and one output, D. D is true if and only if A and B are equal to each other, but not equal to C.
  18. Write the truth table and draw a circuit to do the following. There are three inputs, A, B, and C, and one output, D. D is true if and only if A is false and C and B are not equal. If you want exercise more, just change the truth table and repeat.
  19. Draw a circuit for a 3-input OR gate. This gate takes three inputs a,b,c and outputs a+b+c.
  20. Why did we introduce gates (AND, NOT, OR)? Are switches and wires not enough to build every computer?
  21. Briefly describe a fetch-decode-execute cycle in the von Neumann architecture, in terms of what happens at the ALU, MAR, MDR, and PC.
  22. What is the purpose of the control unit?
  23. What is the "address space" of a computer? Why is it important to know its size?
  24. What is something that we can prove that computers cannot do (state this precisely)? What do the Church-Turing thesis and models of computation have to do with it?
  25. What do we mean when we say that something is decidable? Give examples.