Fall 1998

1. Consider this variation of the Readers-Writer Problem. In this case, there is no Writer; instead, there are two different types of Readers and each type is "incompatible" with the other type.

Assume the existence of these global variables:

Write the code for the Southbound traveler's process.

Be sure to include this comment at the appropriate place in the code:

2. Consider disk arm scheduling algorithms. Assume that the disk has 200 cylinders numbered 0...199. A request for cylinder 99 has already been completed and a request for cylinder 87 is currently being serviced. The current queue of cylinder requests, in order of arrival, is as follows:

a) Briefly describe 3 commonly used algorithms, excluding First-Come, First-Served (FCFS).

b) In what order will each of your algorithms service the requests above?

c) Consider the goal of disk arm scheduling. Which of your three algorithms is best for the specific requests above?

3. Draw the logic diagram for a 5-bit register that increments its value on every clock pulse. Use D flip-flops and 2-input gates.

4. Draw a simplified circuit for>

that uses only NOR and NOT gates.

1. Consider the following fragment of C code.

     int x;
     float y;
     int *pi;
     float *pf;
     x = 12345;
     y = (float) x;        /* 1 */
     printf("%f", y);
     pi = &x;              /* 2 */
     pf = (float *) pi;    /* 3 */
     y = *pf;              /* 4 */
     printf("%f", y);

a) Explain as precisely as possible, from an implementation point of view, what gets copied into the left side by the assignment operator at positions 1, 2, 3, and 4 in the above code. Include in your explanation any effects caused by the "typecasts" in the code.

b)Will the output of the two "printf("%f", y);" statements be the same in both cases? Explain why or why not?

2. Some languages, (e.g., Ada, FORTRAN90) not only support array to array assignment, but support assignment of "slices" of arrays. Consider the Ada declarations below.

A "slice" such as A(15 .. 35) represents the sub-array consisting of all elements of A indexed by the corresponding range. Assignments such as A := B, A(15 .. 17) := B(55 .. 57), and A(20 .. 30) := A(21 .. 31) are all valid. In general A(I .. J) := B(K .. L) is valid if I, J, K, and L are integer variables lying within the index range of MY_ARRAY_TYPE and satisfy J - I = L - K.

a) What checks are done at compile time?

b) What checks are done at run time?

c) What code is generated (use pseudocode or English) for

3. Suppose that you have been given the task of writing a program which will implement a "four function" integer calculator. Specifically, your program should accept non-negative integers, the four binary arithmetic operators +,-,*,/, parentheses, and the equal sign (=), and it should compute and print the value of the resulting expression. It should observe the usual precedence and associativity of operators---all left associative, with + and - having lower precedence than * and /---and the equal sign (=) should be used to signal the end of expression. (There is no "unary minus" operator.)

For example, 37 - 52*(181 + 2) + 750 = should result in 8729 being printed.

You have further been told to construct this program as an implementation of a programming language, with a scanner and a parser which does the arithmetic as it parses (i.e., an interpreter).

a) What tokens will your scanner need to recognize? Explain your choices.

b) Give a correct BNF grammar for your language.

c) Using a pseudocode reasonably close to a standard language (such as C, C++, Java, Pascal, Ada) sketch the implementation of a scanner for this program. Explain your design and explain what the parser should expect to get from your scanner.

b)Will the output of the two "printf("%f", y);" statements be the same in both cases? Explain why or why not?

2. Some languages, (e.g., Ada, FORTRAN90) not only support array to array assignment, but support assignment of "slices" of arrays. Consider the Ada declarations below.

A "slice" such as A(15 .. 35) represents the sub-array consisting of all elements of A indexed by the corresponding range. Assignments such as A := B, A(15 .. 17) := B(55 .. 57), and A(20 .. 30) := A(21 .. 31) are all valid. In general A(I .. J) := B(K .. L) is valid if I, J, K, and L are integer variables lying within the index range of MY_ARRAY_TYPE and satisfy J - I = L - K.

a) What checks are done at compile time?

b) What checks are done at run time?

c) What code is generated (use pseudocode or English) for

3. Suppose that you have been given the task of writing a program which will implement a "four function" integer calculator. Specifically, your program should accept non-negative integers, the four binary arithmetic operators +,-,*,/, parentheses, and the equal sign (=), and it should compute and print the value of the resulting expression. It should observe the usual precedence and associativity of operators---all left associative, with + and - having lower precedence than * and /---and the equal sign (=) should be used to signal the end of expression. (There is no "unary minus" operator.)

For example, 37 - 52*(181 + 2) + 750 = should result in 8729 being printed.

You have further been told to construct this program as an implementation of a programming language, with a scanner and a parser which does the arithmetic as it parses (i.e., an interpreter).

a) What tokens will your scanner need to recognize? Explain your choices.

b) Give a correct BNF grammar for your language.

c) Using a pseudocode reasonably close to a standard language (such as C, C++, Java, Pascal, Ada) sketch the implementation of a scanner for this program. Explain your design and explain what the parser should expect to get from your scanner.

4. The following grammar is expressed in EBNF:

Note: recall that { obj } means to repeat obj zero or more times, and [ obj ] means that obj is optional (occurs zero or one time).

a) Translate the grammar into BNF. You may need to add nonterminals. You may use the alternative symbol "|" but not the empty string in your BNF.

b) Translate the grammar into a single syntax diagram.

1. Write a RECURSIVE algorithm (generateTree) to construct a complete binary tree of height h such that the elements are sequential integers i=1, 2, 3,...,2^(h+1) -1 which fill the tree left-to-right and level-by-level. The algorithm is given h and i and returns a pointer to the root of the constructed tree.

For example, here is a complete binary tree of height h=2 and integer elements i=1, 2, 3, 4, 5, 6, 7:

            1
           / \
          2   3
         / \ / \
        4  5 6  7 

Code your algorithm in C, C++, or Ada. Here are sample declarations, in C, for the data structure and the generateTree function:

Example initial call: root = generateTree(2,1);

2. Suppose we have the following declarations for a linked list of integers:

Assuming that lists have a header node and are unordered, write the following routines:

a) position find(int x, list l) /* returns position of x in list l, or NULL if not found */

b) position findprevious(int x, list l) /* returns position of the element that precedes x in list l, or NULL if x is not in the list */

c) void delete(int x, list l) /* deletes first occurrence of x from list l. You may use the above routines */

3. Let a[0], ... , a[max-1] be an array that can hold up to max floats. Suppose that the first n positions are being used (n < max) and that a[0] < a[1] < ... < a[n-1].

a) Construct an algorithm that inserts a new float x into the ordered list. You may not use a second array for local storage.

b) Assuming that it is equally likely that x belongs anywhere among the n entries, determine the average number of float assignments in your algorithm.

4. Three similar problems are defined below. It is known that PLANAR MAX CUT is in P. It is also known that DEGREE 3 MAX CUT is NP-complete. What, if anything, can you conclude about the complexity of MAX CUT from this? Explain your response.

a) MAX CUT

INSTANCE: A graph G = (V, E), with each edge e having a weight w(e) e N, the positive integers, and given a positive integer K.

QUESTION: Is there a partition of V into disjoint sets V₁ and V₂ such that the sum of the weights of all edges from E which have one endpoint in V₁ and the other in V₂ is at least K?

b) PLANAR MAX CUT

c) DEGREE 3 MAX CUT