My exams tend to have three to six questions. They are closed book, closed notes. I prefer to ask questions with objective answers. Mainly, I will ask you to draw diagrams and write Java code (although no GUIs). You will have the entire class period to finish the exam. The exam will emphasize the material covered since the last exam. The exam questions are mostly based on the homework and the lecture notes.
There are three levels of understanding. From lowest to highest they are:
Level 1: Able to understand explanations of others
Level 2: Able to solve new problems
Level 3: Able to explain material to others
You need to attain level 2 in order to pass the exam. This means you have read and understood your notes, reviewed your homework, and reviewed previous exams (level 1).
Beyond that, you have invented and solved variations of the problems discussed in class. (Level 2).
To attain Level 3, form a study group and take turns explaining the material to each other. If someone in the group gives a lazy or bad explanation, let him have it!
I tend to give away a lot of information in the review
session.
Not covered on exam.
Write regular expressions for the following languages:
{010, 01110, 0111110, ... }
{101, 1101, 1011, 11011, ... }
all Java numbers. For example: -.003, 1e-50, 0x34L
Write an EBNF Grammar for the following languages:
All strings containing an even number of 1's and 0's.
{101, 11011, 1110111, ... }
{01, 0011, 000111, ... }
The EXP language is defined by the following EBNF grammar:
<EXP> ::= <EXP> + <EXP> | <EXP> * <EXP> | 0 | 1
Arithmetic in this language is mod 2:
a + b = (a + b) % 2
a * b = (a * b) % 2
Draw at least two parse trees for the EXP expression:
0 + 1 * 1
Rewrite this grammar so that it isn't ambiguous. Make * have higher precedence than + and make both operators left-to-right associative.
Hint: An expression is a sum of products of bits. An expression such as:
1 * 1 * 1 + 1 * 1 + 1
should be interpreted as:
(((1 * 1) * 1) + (1 * 1)) + 1
Your boss/teacher asks you to write a program that takes a grammar G as input, and outputs an equivalent grammar G' that is unambiguous. What do you say?
Finish the implementation of the following representation of EXP:
class Exp {
Exp operand1 = null, operand2 = null;
int operator; 3 = *, 2 = +, 1 = 1, 0 =
0
Exp(List tokens) throws Exception { /*
tricky, see hints */ }
int eval() throws Exception { ??? }
}
Hint: Exp(tokens) should first check to see if tokens consists of a single token. If this token is "0" or "1", then set op to 0 or 1, respectively, otherwise throw an exception.
If the expression to be parsed is a sum of products:
p_1 + p_2 + ... + p_N-1 + p_N
Then recursively parse p_1 + p_2 + ... + p_N-1 into operand1, recursively parse p_N into operand2, and set op = 2.
If the expression to be parsed is a product of bits:
b_1 * b_2 * ... + b_N-1 * b_N
Then recursively parse b_1 * b_2 * ... * b_N-1 into operand1, recursively parse b_N into operand2, and set op = 3.
Else throw an exception.
Here's some sample code:
index = tokens.lastIndexOf("+");
if (index != -1) {
operand1 = new Exp(tokens.subList(0,
index));
operand2 = new Exp(tokens.subList(index
+ 1, tokens.size());
op = 3;
} else ...
You have downloaded Guava, a language that is identical to Java in almost every respect, except possibly it doesn't implement conditional evaluation. What experiment can you perform to determine if this is true?
Assume Guava is an expression-oriented language. In otherwords, unlike Java, Guava has no commands, but it does have declarations and expressions, including the conditional expression. Why is conditional evaluation necessary in this language? (Hint: How would you implement the factorial function in this language?)
Give an example in Java of a situation where a conditional expression can be used but not a conditional command. Give an example in Java of a situation where a conditional command can be used but not a conditional expression.
Same questions except replace conditional evaluation by short circuit evaluation.
Trig is a language with the syntax:
<Exp> ::= <Num> | <Trig> <Exp>
<Num> ::= <Digit>+.<Digit>*
<Trig> ::= sin | cos | tan
Assume Trig expressions are represented by the instances of the class:
class Exp {
int op; // 3 = tan, 2 = sin, 1 = cos, 0
= Num
Object arg; // = Double if op == 0, Exp
otherwise
Exp(List tokens) throws Exception {
// ???
double eval() throws Exception {
// ???
}
}
Complete the implementations of Exp() and eval().
What output is produced by main(), assuming the following declarations:
class Reactor {
double temp;
Reactor(double temp) {
this.temp
= temp;
}
void temp() {
System.out.println("temp
= " + temp);
}
void incTemp() throws Exception {
temp();
if (1000 <= temp) throw new
Exception("too hot!");
temp
+= 100;
temp();
}
}
public class PowerPlant {
static void morePower(Reactor r) throws
Exception {
System.out.println("entering
morePower");
r.incTemp();
r.incTemp();
r.incTemp();
}
static void morePower(double temp)
throws Exception {
System.out.println("entering
morePower");
System.out.println("temp
= " + temp);
if (1000 <= temp) throw new
Exception("too hot!");
temp
+= 100;
System.out.println("temp
= " + temp);
if (1000 <= temp) throw new
Exception("too hot!");
temp
+= 100;
System.out.println("temp
= " + temp);
if (1000 <= temp) throw new
Exception("too hot!");
temp
+= 100;
}
static void test1() {
Reactor
smokey = new Reactor(850);
try {
morePower(smokey);
morePower(smokey);
} catch (Exception e) {
System.err.println(e.getMessage());
}
smokey.temp();
}
static void test2() {
Reactor
smokey = new Reactor(850);
try {
morePower(smokey.temp);
morePower(smokey.temp);
} catch (Exception e) {
System.err.println(e.getMessage());
}
smokey.temp();
}
public static void main(String[] args)
{
test1();
test2();
}
}
+++++
What output is produced by running the following Java program:
public class FinalTest {
static void S(int i) {
System.out.println("S_" + i); }
int a = 100, b = 200;
void test1(int a) {
int x = b + 3; int b = 5;
System.out.println("Entering
test1");
S(a);
S(x);
}
void test2(int i) {
System.out.println("entering
test2");
while(++i
< 10) {
S(1);
if
(i == 2) continue;
S(2);
if
(i == 4) break;
S(3);
}
S(4);
}
void test3(int n) {
System.out.println("entering
test3");
S(n);
if (n > 0) test3(n/2);
}
void test4(int i) throws Exception {
System.out.println("entering
test4");
if (i%4 == 0) throw new Exception();
S(i);
}
public static void main(String[]
args) {
FinalTest st = new FinalTest();
st.test2(6);
int a = -10, b = -20;
st.test1(0);
st.test3(5);
try {
for(int
i = 15; i > 0; i--) st.test4(i);
S(10);
} catch(Exception e) {
S(200);
}
S(20);
}
}
Assume the following Delta declarations have been made:
[const x 2]
[const y 10]
[const z 20]
What value is produced by the Delta expression:
(let [[const x 50] [const y (+ x 1)]]
(letseq [[const x (+ y 1)] [const y x]]
(+ x y )))
(let [[const x 50]
[const
y
(letseq
[[const x (+ y 1)] [const y x]]
(+
x y ))]]
(+ x y))
(letrec [[const x (+ y 1)] [const y 20]] (+ x y))
+++++
Guava is just like Java except variables are allowed to be redeclared in nested blocks (like in C++). Are Guava statement blocks sequential, collateral, or recursive. How can you tell?
Assuming Guava uses sequential blocks, what output is produced by the following code:
class Test {
static int x = 10;
public static void main() {
int x = 20;
{
int
y = x + 1;
{
int
x = y + 2;
int
y = x + 3;
System.out.println(x
+ y);
}
}
}
}
Which classes are the fields x, y, and z visible in?
package p1;
class A {
int x = 10;
private int y = 20;
protected int z = 30;
public int w = 40;
}
class B {
A a = new A();
// etc.
}
package p2;
class C extends p1.A { ... }
class D {
p1.A a = new p1.A();
... }
1. pass by value or by reference for simple values
2. pass by text or by name for simple values
3. static or dynamic scope rule
4. memoization for thunks
5. lazy or eager evaluation
+++++
Assume Epsilon implements the static scope rule and allows non-global functions. Assume the following declarations have been made:
[const x 3]
[const f (let [[const x 10]] (fun (y) (+ x y)))]
[const g (fun (x) (fun (a) (* x a)))]
[const h (g 5)]
What value is produced by the expression:
(letseq [[const x 100]] (f (+ x 2)))
(h 2)
Draw an environment diagram displaying the environment at the moment f is called. At the moment h is called.
accum square [2, 3, 4]
29
accum sin []
0
accum f [] = 0
accum f (head:tail) = f(head) + (accum f tail)
Alternatively:
accum f nums
= sum nums2
where
nums2
= map f nums
sum[]
= 0
sum (head:tail) = head + sum(tail)
Write a function that expects a list of non-empty lists as inputs, vals, and:
1. Returns a list containing the heads of each list in vals. For example:
heads [[1, 2, 3], [2, 5, 6], [9, 0]]
[1, 2, 9]
heads [] = []
heads (h:t)
= head(h): heads(ta)
2. Returns a list which is the result of appending all lists in vals. For example:
append [[1, 2, 3], [2, 5, 6], [9, 0]]
[1, 2, 3, 2, 5, 6, 9, 0]