CSCI 310 Exam #2 Spring 2011

Directions: This test is closed book, closed notes, closed neighbor, closed internet, closed cell phone, etc. Read through the entire test before starting on any one question in order to do the short and easy ones first to maximize your grade. Write legibly—if I can’t read it, I have to assume it’s wrong. Not counting the bonus, there should be 100 points on the test. Good luck and have fun!

1. What are three properties of variables that need to be specified when specifying a new programming language?

2. Describe all the legal sequences of letters generated by (a|b)*a(a|b)*

3. Give the precedence and associativity for the four operators in the grammar given below.

E -> E*T | E/T | T

T -> T+F | F-F | F

F -> number

4. Is the following grammar ambiguous or not? Justify your answer.

S -> i ( C ) t S | i ( C ) t S e S | A

5. Give two examples of operators that are usually right associative in a programming language. For each, give an example use where the results would be different if the operator were left associative instead.

6. What is the lifetime of a variable?

7. Are variable scope and variable lifetime the same? If not, give an example showing where they are different.

8. Why aren’t dynamically allocated variables allocated on the stack?

9. What is one problem with the assignment operator in procedural programming languages?

10. Why do procedural languages not allow variable names to start with a digit?

BONUS QUESTIONS: (3 points each)

A. Mr. Slow, Mr. Medium, Mr. Fast, and Mr. Speed must cross a rickety rope bridge in 17 minutes. The bridge can carry at most two people at a time. Furthermore, it's dark, and there is only one flashlight; any single person or pair of people crossing the bridge must have the flashlight with them. (The bridge is too wide for the flashlight to be thrown; it must be carried across.) Each man walks at a different speed. A pair travelling together must walk at the rate of the slower man. Mr. Slow can cross the bridge in at most 10 minutes; Mr. Medium can cross in 5 minutes; Mr. Fast can cross in 2 minutes; Mr. Speed can cross in 1 minute. How do all four men get across in the bridge in 17 minutes?

B. You drive to the store at 20 mph and return by the same route at 30 mph. Discounting the time spent at the store, what was your average speed?

C. At McDonald's you can order Chicken McNuggets in boxes of 6, 9, and 20. What is the largest number of nuggets that it is not possible to obtain by purchasing some combination of boxes?

D. You're a cook in a restaurant in a quaint country where clocks are outlawed. You have a four minute hourglass, a seven minute hourglass, and a pot of boiling water. A regular customer orders a nine-minute egg, and you know this person to be extremely picky and will not like it if you overcook or undercook the egg, even by a few seconds. Is it possible to provide your customer with a 9 minute egg? If so, how?