DATA STRUCTURES, ANALYSIS OF ALGORITHMS AND COMPUTATIONAL COMPLEXITY
1. Code any O(n log n) sorting algorithm in the language of your choice. Be sure to state the name of your algorithm. Assume that the data are integer elements stored in an array.
b) Prove: PÍ PSPACE
Consider SAT. Answer each of the following yes/no/unknown, with a brief but complete explanation or proof.
c) SAT is in P
d) SAT is in PSPACE
e) SAT is in NP
OPERATING SYSTEMS AND COMPUTER ARCHITECTURE
1. Consider the critical section problem.
a) Define and describe briefly:
(i) mutual exclusion
(ii) progress
(iii) fairness (no indefinite postponement)
b) Consider the code below, with four line numbers. State TRUE or FALSE, with a brief explanation, whether the code guarantees:
(i) mutual exclusion
(ii) progress
(iii) fairness
Global Variable (shared by both processes):
int lock;
Processes:
Philosopher0() { Philosopher1() {
while (true) { while (true) {
Line#
1: while (lock == 1) { /* empty loop body */ } while (lock == 1) { /* empty loop body */ }
2: lock = 1; lock = 1;
3: << critical section >> << critical section >>
4: lock = 0; lock = 0;
} }
} }
Main Body:
lock = 0;
start asynchronously: Philosopher0();
start asynchronously: Philosopher1();
2. Consider optimal algorithms, usually used as baselines for comparison purposes.
a) In one sentence, what is the optimal CPU scheduling algorithm?
b) In one sentence, what is the optimal page replacement algorithm?
Consider the Shortest-Seek-Time-First (SSTF) disk scheduling algorithm for processing blocks/sectors.
c) Discuss any serious drawbacks to SSTF.
d) Show that SSTF is not optimal. Prove your answer using exactly a sequence of 5 block/sector numbers of your choice.
3. Design a fully simplified 3-bit mod 7 counter with JK flip-flops. The circuit increments with each clock pulse, going through the sequence 0,1,2,3,4,5,6,0,1,2,3,4,5,6,0,1,... . Show the circuit diagram.
4. Draw the circuit diagram for a 4-bit shifter as a combinational circuit. (Note that there are no flip-flops in this problem.) The inputs are A3 A2 A1 A0. The outputs are B3 B2 B1 B0 with the direction of the shift determined by a control input C. If C=1, B3 B2 B1 B0 is a logical left shift of the input. If C = 0, it is a logical right shift.
PROGRAMMING LANGUAGES AND COMPILER DESIGN
1. The below skeleton is in a C-like language. It includes one goto statement. The target of the goto might be any one of the labeled statements, s1...s5.
a) For each possible target, list BRIEFLY and CONCISELY
(i) any semantic problems with a goto to this target, and
(ii) any implementation problems that arrive with a goto to this target?
b) Choose a language of your choice and discuss which gotos would be legal.
int g() {
int x = 5;
...
t1: s1; // first target
...
return x;
}
int f() {
int i,j;
for (i=1;i<20;i++)
{ ...
t2: s2; // second target
...
goto < target ti >; // goto statement
...
}
t3: s3; // third target
...
for (j=1;j<30;j++)
{ int k=3;
...
t4: s4; // fourth target
...
}
...
return (i+j);
}
int main () {
int x=5, y=10;
x=g();
y=f();
t5: return 0; //fifth target
}
2. An e-commerce company has a reply template that asks for a user's email address. You, as an expert in compiler design, are asked to use compiler techniques for language specification to help in validating input by specifying the set of legal strings.
For simplification, suppose that the only characters are:
26 lower case letters: a,b,c,...,z
3 special characters: hyphen (-), atsign (@), dot (.)
And suppose that a legal email address must be a sequence of characters that:
Begins with a letter
Contains exactly one occurrence of the atsign
Ends in one of: .net .edu .com
Never contains two adjacent special characters (i.e, '.@', '...', etc. are illegal)
a) Write a regular expression for legal email addresses.
b) Write a BNF grammar that generates legal email addresses.
3. The XXX Language Reference manual says that "the order of the evaluation of parameters is not specified."
a) Write a simple C function that gives different results depending on the order of evaluation of the parameters. Show the definition of your function and the call to the function. Use no more than two parameters and three lines of code in the function. Show the different outputs possible. Explain why they occur.
b) What effect does the non-specification of parameter evaluation order have on the writer of the compiler for XXX? on programmers who write XXX programs?
4. A compiler writer must choose a data structure to use for building the symbol table. Among the possible choices are:
a. linked list.
b. binary tree.
c. hash table.
In a few sentences for each, list the ADVANTAGES and DISADVANTAGES of each of these. Be sure to list why each is good (or bad) for the special requirements of a symbol table. You may assume a standard block-structured language such as C, Java, or Ada in your answer.