Introductory quiz
Please answer the following questions after listening to the
overview of the class. The quiz should take no more than 15
minutes. The answers will not affect your grade in the
class, but they will help the instructor organize the
lectures and exercises. The sooner you return the answers
the better.
* What would be the most interesting aspect of a class like this for you?
* List things that you would like to do least in this class.
* We say that a statement is valid if it is true under all
possible interpretations. Answer the following questions.
- Is the following statement valid when x is a real number and f is a function
from reals to reals, and why:
"If (f(x))^2 = 4, then f(x)=2"
- Is the following statement valid (for arbitrary properties
P and Q), and why:
"If for all x, both P(x) and Q(x), then both
1) for all x, P(x), and
2) for all x, Q(x)."
- Is the following statement valid (for arbitrary properties
P and Q), and why:
"If for all x, P(x) or Q(x) hold, then at least
one of the following two is true
1) for all x, P(x), or
2) for all x, Q(x)."
* Let x,y,z be integer variables that satisfy both of these
two conditions:
x + y = 3z
x - 2y = z
What is the strongest property that you can state about
the integer x that does not mention the variables y or z?
* List programming languages in which you wrote more than 20
lines of code. In particular, list any functional and
object-oriented programming languages that you used.
* List the subset of the above languages in which you wrote
500 lines of code or more.
* Consider a simple programming language with the following
kinds of statements where x,y,z denote variables, and c
denotes integer constants:
x = c
x = y + z
while (x > 0) { ... }
if (x > 0) { ... } else { ... }
x = input()
output(x)
where input() returns an integer read at the keyboard and
output(x) outputs the value of variable x.
- Say in 3-5 sentences how you would build an
interpreter for this language.
- What is the class of functions from integers to integers
that can be described in this programming language?
* Suggest (in 3-10 sentences) how you would design an
algorithm for the following problem:
The input of the algorithm is a description of a
function that accepts two integers and produces an
integer as a result. An example of such function,
is the function f:
x = input();
y = input();
result = 0;
while (y > 0) {
result = result + x;
y = y - 1;
}
output(y);
Your algorithm should accept any other such function
that can be written in our simple programming language.
The output of your the algorithm should be "true" if 0
is the only value that the function can return, and
"false" otherwise.
What would your algorithm return on the above example?