CS 110: Elements of Computing. Instructor: Jim Aspnes

Final Exam

Work alone. Do not use any notes or books.

Write your answers in the blue book(s).

You have approximately 150 minutes to complete this exam. There are seven problems, for a total of 140 points.

1. An unusual Turing machine (20 points)

Below is the state transition table for a Turing machine:

Old state	Value read	Write	Move	New state
INIT	`0`	`1`	None	HALT
INIT	`1`	`1`	Right	OTHER
OTHER	`0`	`0`	None	HALT
OTHER	`1`	`1`	Right	INIT

Assume that the machine starts in the INIT state with its head on the leftmost cell of a tape containing the string 111100. What string will be stored on the tape when the machine halts?
Assume that the input to the machine always consists of a sequence of n 1 symbols followed by infinitely many 0 symbols. Give a succinct description of what output the machine generates for each input.

Solution:

111110.
The machine makes the tape contain an odd number of 1 symbols, adding an extra 1 if necessary.

2. A very small computer (20 points)

The Mintel Corporation, a minimalist computer manufacturer, has just released a CPU called the 2002 with a 2-bit accumulator.

Assuming the accumulator holds unsigned binary numbers, what are the least and greatest numbers it can hold?
Assuming the accumulator holds signed binary numbers in two's complement representation, what are the least and greatest numbers it can hold?

(For both subproblems, write your answers in decimal.)

Solution:

0 and 3.
-2 and 1.

3. Asymptotic efficiency (20 points)

Five algorithms for solving some unspecified problem have asymptotic running times Theta(n log n), Theta(log n), Theta(n), Theta(2ⁿ), and Theta(n²).

Order these running times from smallest to largest.
Which of these running times puts the corresponding algorithm in the class P?

Solution:

Theta(log n), Theta(n), Theta(n log n), Theta(n²), Theta(2ⁿ).
Theta(log n), Theta(n), Theta(n log n), Theta(n²).

4. An unreliable network (20 points)

You have hired a programmer to develop a new network-based accounting system. The programmer chooses the UDP protocol for all communication within the system, and finds out when testing a prototype for the system that the network is throwing away half of the UDP packets, which will cause massive loss of data, gnashing of teeth, and legal liability when the system is put into use. Suggest a simple solution to this problem.

Solution:

Use TCP instead of UDP.

5. A recursive program (20 points)

Below is a procedure written in a typical modern programming language. Assume that the print procedure prints a single number to the screen, on a line by itself. What output does this procedure produce when called as bouncy(3)?

void bouncy(int n)
{
    if(n > 0) {
	print(n);
	bouncy(n-1);
    }
    print(n);
}

Solution:

6. A higher-order function (20 points)

Recall that Scheme uses the form (lambda (x) expression) to describe a function that takes a single argument x and returns the result of substituting x in expression, that it uses (define variable value) to set the value of a variable, and that in an expression like (+ 2 x) the first item in the list is the action that is then applied to the other items in the list, where variable names like x are replaced by their values.

Suppose that the following definitions are given to a Scheme interpreter:

(define ff (lambda (f) (lambda (x) (f x x))))
(define g1 (ff +))
(define g2 (ff *))

What does (g1 10) evaluate to?
What does (g2 10) evaluate to?

Solution:

7. A database system (20 points)

An employee database for a large academic institution holds two tables: EMPLOYEES and SALARIES. Each row in EMPLOYEES has fields NAME and JOBTITLE. Each row in SALARIES has fields JOBTITLE and SALARY. The company has a strict rule that all employees with the same job title are paid the same salary.

A typical query applied to this database might be the following, which prints out the salary of one Richard Levin:

SELECT SALARIES.SALARY FROM EMPLOYEES, SALARIES
WHERE EMPLOYEES.NAME = 'Richard Levin'
AND EMPLOYEES.JOBTITLE = SALARIES.JOBTITLE

Below is a SQL query that attempts to find all employees whose salary is greater than 100,000. Explain what is wrong with it and write a query that works.

SELECT EMPLOYEES.NAME FROM EMPLOYEES, SALARIES
WHERE SALARIES.SALARY > 100000

Solution:

The query doesn't connect the job title in EMPLOYEES with the job title in SALARIES. So it will in fact print out every employee name once for every job title that has a salary greater than 100,000. Below is a revised query that works:

SELECT NAME FROM EMPLOYEES, SALARIES
WHERE EMPLOYEES.JOBTITLE = SALARIES.JOBTITLE
AND SALARY > 100000