Spring 1999
1. Given a linked list of integer elements, construct a SELECTION SORT algorithm that puts the integer elements into ascending order. Note that a selection sort does O(n) copies. On each pass, the smallest element is placed into its proper position. For example, on the third pass:
Before: 5 10 55 22 65 12 75
After : 5 10 12 22 65 55 75
The code should NOT re-link nodes - just copy elements. Do not create a new list. The list does not have a dummy/header node.
Write code in the language of your choice. Here is the declaration of the data structure and the prototype in C:
typedef struct node *node_ptr;
struct node {
int element;
node_ptr next;
};
void selection_sort(node_ptr p);
2. A FULL node in a binary tree is a node that has exactly two non-null children. Declare a suitable data structure for a binary tree node and write a RECURSIVE function, in the language of your choice, that returns the number of full nodes in a binary tree.
3. Consider the following problems and their algorithmic solutions in the worst case. State the tightest BIG-OH performance of each algorithm, i.e., THETA (Q). Do not include any proofs, just list the results.
a) Sorting: use n, the number of elements to sort.
1) Quicksort
2) Mergesort
3) Radix sort
b) Graphs: use n, the number of nodes, and m, the number of edges, appropriately.
4) Depth-First Search Spanning Tree
5) Dijkstra's Shortest Path
6) Dijkstra's/Prim's Minimum-Weight Spanning Tree
7) Kruskal's Minimum-Weight Spanning Tree
c) Matrix Multiplication: use n, the size of the square matrices.
8) Strassen's Algorithm
d) Longest Common Subsequence Problem (String Matching): use m, the length of the substring, and n, the length of the string being searched.
9) Straightforward (Brute Force) Comparison
10) Knuth-Morris-Pratt Algorithm
4. Recall these definitions:
HC (Hamiltonian Circuit)
Instance: Undirected graph G = (V,E)
Question: Does G contain a Hamiltonian circuit (a path that begins at some vertex, passes through each other vertex exactly once, and returns to the starting vertex)?
TSP (Traveling Salesman)
Instance: Set C of m cities, with a positive integer distance d(ci, cj) for each pair of cities ci,cj, in C, and a positive integer B.
Question: Is there a tour of C having length B or less? (A tour is a circuit that starts and ends at some cstart visiting each city exactly once and then returns to cstart. )
a) Prove carefully and completely: HC <=p TSP
b) If it is known that HC is NP-complete, what can be said about TSP? Explain carefully and completely.
c) If it is known that TSP is NP-complete, what can be said about HC? Explain carefully and completely.
1. Consider N processes sharing the CPU in a round-robin fashion (N>=2). Assume that each context switch takes S msec and that each time quantum is Q msec. For simplicity, assume that processes never block on any event and simply switch between the CPU and the ready queue.
In the following your answers should be functions of N, S and T.
a) Find the maximum value of Q such that no process will ever go more than T msec between starting times on the CPU?
b) Find the maximum value of Q such that no process will ever go more than T msecs between executing instructions on the CPU?
2. Consider a system with 4200 words of main memory using variable partitions. At some time, the memory is occupied by three blocks of code/data as follows:
| starting | ||
| block | address | length |
| A | 1000 | 1000 |
| B | 2900 | 500 |
| C | 3400 | 800 |
When loading a new block into memory, the following strategy is used:
Try the best-fit algorithm to locate a hole of appropriate size.
If this fails, create a larger hole by shifting blocks in memory toward address zero; this always starts with the block currently at the lowest memory address and continues only until enough space is created to place the new block.
Assume that three new blocks are to be loaded (in the order listed):
| block | size |
| D | 500 |
| E | 1200 |
| F | 200 |
Show the memory contents at the beginning (blocks A, B, and C loaded), and after each new block (D,E,F) has been loaded. Be sure to label each allocated block of memory with its letter and the locations of its boundaries (start, end) in memory.
3. Design a fully-simplified circuit for:
f(x,y,z,w) = x'y'z'w + x'y'zw' + x'yz'w + x'yzw.
No gate may have more than two inputs. For full credit, you can use no more than 5 gates of one or two inputs each. Also, for full credit, you must show the complete boolean function table, you must show and use the Karnaugh Map (K-map), and you must show all details for simplifying the boolean expression derived from the K-map.
4. Construct a sequential circuit for a three-bit device. For each state, the next state is the correct three-bit two's complement of the current value. Change of state always takes place on the rising edge of the positive clock pulse, and no change of state can take place during the "zero" part of the clock pulse. There is no external input. There is no external output.For full credit on this question, you must show the state diagram and the state table including the appropriate flip-flop information, as obtained from the flip-flop excitation table that you must also show. You must show and use the correct Karnaugh maps (K-maps) and produce the optimal circuit for the flip-flop type you have chosen.
1. Consider the small C++ program below.
int a;
int f(int x) {
if ( x < 10 ) {
x = x + a + 3;
return g(x);
} else return 5 * x;
}
int g(int y) {
if ( y < 10 ) {
y = y + a + 2;
return f(y);
} else return y;
}
int main ( void ) {
a =1;
cout << f(a);
return 0;
}
a) Explain what this will write and why. Display the run time stack during the run of this program. Include in your diagram an explanation the values of any local variables involved.
b) Suppose that the functions f and g are changed to have reference parameters, that is, prototypes int f(int& x) and int g(int& y). In this new situation, explain what the modified program will write and why. Display its run time stack. Include in your diagram and explanation the values of any local variables involved.
2. Some languages, like C, allow functions to have both "static" and "automatic" local variables. They also provide for initialization of variables. Consider a C function likeint f( int x) {
int a = 12;
static int b = 97;
...
}
a) What is the difference between "static" and "automatic" local variables?
b) Describe how runtime storage would be allocated for "a" and "b" above.
c) Describe how and when these variables are initialized.
3. The following is a simple grammar with terminal symbols "(", ")", and "a":
A --> (A) | a
a) Construct the SLR (simple LR) parsing table for this grammar.
b) Prove or disprove: this grammar is suitable for SLR parsing.
4. A small programming language has only the following types:
integers
reals
arrays with base type integer, any number of dimensions, lowest index 0
Example declarations:
i : integer;
r : real;
a1 : array[100] of integer; //1 dim array, 0..99
a2 : array[6,9,12] of real; //3 dim array, 0..5,0..8,0..11
It allows nested blocks with redeclaration of variables.
It has been decided that the compiler must:
i) efficiently store all necessary information for each identifier
ii) support re-use of the same name in different blocks
iii) store the entire symbol table for use at run time
Describe:
a) a data structure for each individual symbol table entry
b) an organization to store all necessary symbol table entries