2018 APCS Semester 1 Midterm Exam and Answers

One of the miseries of life, is that everybody names things a little bit wrong, and so it makes everything a little harder to understand in the world than it would be if it were named differently. A computer does not primarily compute, in the sense of doing arithmetic — strange. Although they call them computers, that’s not what they primarily do. They primarily are filing systems.

People in the computer business say, “They are not really computers, they’re data handlers.” Alright. That’s nice. Data handlers would’ve be’ a better name, because it gives a better idea of the idea of a filing system. There’s a lot of data on cards, and you’re handing ’em. You take cards out, you look at them and put them back, and so on.

— RICHARD FEYNMAN, “Computer Heuristics Lecture” (1985)
https://www.youtube.com/watch?v=EKWGGDXe5MA

Instructions

On one or more separate pieces of paper, write your name and your answers to the 25 exam questions. Answer each question as clearly, concisely, and completely as you can. Write legibly, and label each of your answers with the corresponding question number. Each question is worth 4 points. Partial credit will be given for answers that are partially correct. Some questions refer to the following procedures and source code. 

Procedure H (Happy or sad).

Given any positive integer n, indicate whether n is happy or sad.

Step 1. Replace the value of n with the sum of the squares of its digits in
        base ten.
Step 2. If the value of n is 1, then output "The number is happy." and stop;
        otherwise, go to Step 1.
Step 3. Output "The number is sad."

Procedure E (Exact area).

Given any positive number r, compute the area of the circle with radius r.

Step 1. Set p equal to the exact value of the number Pi.
Step 2. The answer is the product p * r * r, where * denotes multiplication.

(function Prog1() {
  "use strict";
  function mystery(a) {
    const n = a.length;
    let s = 0;
    let i = 0;
    while (i < n) {
      const v = a[i];
      s = s + v;
      i = i + 1;
    }
    return s - i;
  }
  const seq = [3, 2, 1, 0];
  const ans = mystery(seq);
  alert(ans);
})();

public class Prog2
{
    public static int mystery (int[] a)
    {
        final int n = a.length;
        int s = 0;
        int i = 0;
        while (i < n)
        {
            final int v = a[i];
            s = s + v;
            i = i + 1;
        }
        return s - i;
    }
    public static void main(String[] args)
    {
        final int[] seq = {3, 2, 1, 0};
        final int ans = mystery(seq);
        System.out.println(ans);
    }
}

Questions

  1. Donald Knuth tells us that an algorithm is a finite set of rules that gives a sequence of operations for solving a specific type of problem, with the additional stipulation that an algorithm has five important features. What are the five important features of an algorithm?
    1. Finiteness. An algorithm always terminates after a finite number of steps. For an algorithm to be practical as well as finite, it must contain a “reasonable” number of steps — i.e. a “very finite” number of steps. An algorithm that requires a computation — any computation — to be performs a number of times equal to the largest integer ever named, for example, might in theory be finite but certainly wouldn’t be practical. (See Who Can Name the Bigger Number?)
    2. Definiteness. Each step of an algorithm is precisely defined.
    3. Input. An algorithm has zero or more inputs: values that are given to it before the algorithm begins.
    4. Output. An algorithm has one or more outputs: values that are related to the inputs.
    5. Effectiveness. One way of trying to explain effectiveness is to say that it must be possible for a person using pencil and paper to perform all of the operations exactly, in a finite amount of time. If an operation involved, say, printing the exact value of an irrational number expressed as a decimal expansion — the value of the number Pi or the square root of 2, for instance — then the operation would not be effective, because the decimal expansion of an irrational number requires an infinite number of digits to the right of a decimal point. Another example of a noneffective step is “If every problem whose solution can be verified in polynomial time can also be solved in polynomial time, then go to step 1.” Such a statement would not be an effective operation until someone is able to show that there is an algorithm that determines whether P equals NP. (See P vs. NP problem.) Yet another example of a noneffective step in a procedure designed to solve the problem of obtaining a cookie from a cookie jar would be to “put on the Hobbit’s ring so as to become invisible, and then take one”; in contrast, an effective step would be to “wait until no one is looking, and then taken one.”
  2. Are all algorithms computational methods? If not, why not?
    Yes, all algorithms are computational methods. (A computational method has all the features of an algorithm except it might not terminate; a computational method might terminate or it might not.)
  3. Are all computational methods algorithms? If not, why not?
    No, not all algorithms are computational methods, because some computational methods do not terminate, but all algorithms do terminate.
  4. Explain how algorithms and programming languages are related.
    A programming language is a language that can be used to express a computational method (i.e. any algorithm and then some) precisely so that it can be performed by a computer.
  5. What is a computer program?
    A computer program is a computational method expressed using a programming language.
  6. Is Procedure H an algorithm? If not, why not?
    No, Procedure H is not an algorithm, because it might not terminate.
  7. Is Procedure H a computational method? If not, why not?
    Yes, Procedure H is a computational method. (It has all of the characteristics of an algorithm, except it might not terminate.)
  8. Is Procedure H a program? If not, why not?
    No, Program H is not a program, because it is not expressed using a programming language. (It is expressed in English.)
  9. Is Procedure E an algorithm? If not, why not?
    No, Procedure is not an algorithm, because it is not effective. (See answer to Question 1.)
  10. Is Procedure E a computational method? If not, why not?
    Again, Procedure is not a computational method, because it is not effective.
  11. Are the two subprograms named mystery both algorithms? If not, why not?
    Yes, they are both algorithms.
  12. Are the two subprograms named mystery both computational methods? If not, why not?
    Yes, they are both computational methods.
  13. How many distinct values can a single bit of data represent?
    2
  14. How many bits are needed to represent 200 different values?
    8
  15. How many values can you represent using 6 bits?
    64
  16. Convert the number 11110010101011 from binary to hexadecimal.
    11110010101011 → 11 1100 1010 1011 → 3 12 10 11 → 3cab (answer)
  17. What is the decimal value of the hexadecimal literal 0x7d9? (In Java and JavaScript, the literal 0x7d9 is the hexadecimal number 7d9, which may also be written 7D9, #7d9 or #7D9. The prefixes "0x" and "#" are sometimes used to indicate that the digits that follow the prefix are hexadecimal digits.)
    7 * 162 + 13 * 161 + 9 * 160
    7 * 256 + 13 * 16 + 9
    1792 + 208 + 9
    2009
  18. How can you tell, just by looking a sequence of bits, what type of data the bits represent?
    You cannot.
  19. Is a literal value more likely to be used as a parameter (i.e. a formal parameter) or as an argument (an actual parameter)? Why?
    A literal cannot be used as a parameter, because parameters are variables. Literals can be used as arguments, on the other hand. Therefore, a literal value is more likely to be used as an argument.
  20. What parameter are the subprograms named mystery defined in terms of?
    The parameter named a.
  21. In Prog1 and Prog2, when is the value of the variable ans used as an argument?
    The value of the variable ans is used as an argument when it is passed to the function alert in Prog1 and when it is passed to the method System.out.print in Prog2.
  22. For full credit, answer one of the following two questions correctly. For an extra credit point, answer both questions correctly.
    1. If the variable seq referred to the associative array [0,1,2,3] instead of [3, 2, 1, 0], what value would be output by Prog1?
      2
    2. If the variable seq referred to the array {3,2,1} instead of {3, 2, 1, 0}, what value would be output by Prog2?
      3
  23. For full credit, answer one of the following two questions correctly. For an extra credit point, answer both questions correctly.
    1. What are the eight primitive types of data in the Java programming language?
      • byte, short, int, long, float, double
      • char, boolean
    2. What are the six primitive data types in the version of the JavaScript programming language defined by the ECMAScript 2018 language specification?
      • Number
      • String
      • Boolean
      • Undefined
      • Null
      • Symbol
  24. For full credit, answer one of the following two questions correctly. For an extra credit point, answer both questions correctly.
    1. In Prog1, what is the primitive JavaScript data type of the variable s and how many bits are used to encode the value?
      Number (64 bits).
    2. In Prog2, what is the primitive Java data type of the variable s and how many bits are used to encode the value?
      int (32 bits).
  25. Will the Java and JavaScript versions of mystery always return the same value for a given input (an array of integers)? If not, provide an example of an array of integers that relates to different outputs.
    No, the two subprograms will not always return the same value given the same array of integers, because the data type of the variables used to hold the sum (i.e. the variables named s) are different in the two programs. The array of integers [2000000000, 2000000000] (or {2000000000, 2000000000}) is an example of an input that relates to different outputs.
A computer is a high-class, super-speed, nice, streamlined, filing system.

— FEYNMAN