Winter 2005 UCLA CS 31 (Shinnerl)

1. Counting.

   1. Define linear growth. Define exponential growth. Give an example of a linearly increasing sequence and an example of an exponentially increasing sequence.

   2. State Moore's Law, when it began, and how much longer it will probably continue.

   3. In view of Moore's Law, explain why the "computer revolution" may not have happened yet.

   4. Explain very briefly how the diagrams generated by this Java Applet prove the formula 1+2+...+N = N(N+1)/2.

   5. When N is doubled, by approximately what factor does the value of the sum 1+2+...+N increase? Why?

   6. Given N distinct values x₁, x₂, ..., x_N,
      
      1. how many distinct, unordered pairs { x_i, x_j } are there, for i, j both between 1 and N? Explain briefly.
      2. how many different orderings of the sequence x₁ x₂ ... x_N are there? Explain briefly.

   7. 1. How many different values can be represented with just N bits, for a given, fixed integer value N ?
      2. How many bits does it take to represent a given, fixed integer N in binary?

2. Types and Representation.

   1. Explain what is meant by the concept of type and why it is important in C++. What are the basic built-in types in C++? How are they related?

   2. What is type casting? What is promotion? What is truncation? Give simple examples. What makes type casting complicated? What rules of thumb govern casting of the built-in types in C++?

   3. Find the binary and hexadecimal representations of decimal number 386.

   4. 1. Find the binary representation of one tenth (decimal 0.1).
      2. Give an example of a decimal fraction whose binary representation is finite and exact.

   5. Consider a 5-bit floating point representation a * 2^b, with 1 sign bit and 2 bits each for the mantissa a and exponent b. Show the locations of all representable numbers in this system on the number line.

   6. Implement a C++ function that receives a single character as input and returns the following (to the calling function). Do not explicitly use any numerical ASCII values. If the input is an upper-case letter, the function outputs the same letter in lower case. If the input is a lower-case letter, the function outputs the same letter in upper case. Otherwise, the function outputs the same character it receives, unchanged.

3. Define the following.
   1. Compiler.
   2. Operating System.
   3. Expression.
   4. Object.
   5. Variable.
   6. Moore's Law.
   7. Modularity.
   8. Recursion.
   9. Definition.
   10. Declaration.
   11. Scope.
   12. Abstraction; high vs. low levels of.

4. Describe some of the most important elements of good coding style and program design. Why are they important?

5. Implement a function that displays a generic "new" calendar for a month with user-specified numbers of days per week, days per month, and first day of the month. (For convenience, let days of the week be numbered 1,...,N, where the user provides N.)

6. Implement C++ functions that make Egyptian and Mayan pyramids of user-specified number of levels and ASCII characters. E.g.

   Egyptian (3, *) prints out:
         *
        ***
       *****
   Mayan (3, #) prints out:
        ###
       #####
      #######
   

7. Fibonacci numbers. The Fibonacci Sequence is 1,1,2,3,5,8,13,21,.... It can be defined by the following three rules.

     
         F(1) = 1.
         F(2) = 1.
         F(i) = F(i-1) + F(i-2)  for every integer i > 2.
   

   Implement a C++ function that computes the ith Fibonacci number F(i), for any user-specified i >= 1. Make sure that your solution uses a constant amount of storage and a total number of arithmetic operations proportional to input i.