Spring 2010

  1. Consider a DOUBLY-LINKED LIST of nodes which contain character elements, and with both head and tail available. For example,

  2. next:   ->   ->   ->   ->        c    a    f    r    q  prev:   <-   <-   <-   <-

    Write a function, in the language of your choice, which creates (and eventually returns) a new SINGLY-LINKED LIST with the same elements but in REVERSE order. For example,

    next:   ->   ->   ->   ->        q    r    f    a    c

    The function should return a pointer to the head of this new list (for example, the node with "q"). An initial call would be:

     shead = reverse(dhead,dtail);

  3. where dhead and dtail point to the doubly-linked list, and shead points to the new list. The running time of your function should be O(n) (where n is the number of list entries) and should only use O(1) extra memory. Declare your data structures (two types of nodes), and do not include a dummy header.

  1. Consider a HASH TABLE (size = 100) in which collisions are handled by chaining with DOUBLY-LINKED LISTS. Assume the keys are integers, and the existence of a hash function which determines the hashing index for a key:

    int hash(int key)

    Write a function which inserts a key into a new node in the table, as specified by the hash function. There are no header nodes in the lists, and do not worry about duplicates. Be sure to consider default situations. Code in the language of your choice and include the declaration of your data structure.

  2. Given a BINARY TREE, write a function which returns TRUE (1) if the the tree ALTERNATES with left child, right child, left child, right child, etc. Otherwise, return FALSE (0).

    For example,

    a)        b)        c)        d)           X         X         X         X   /           \         \         \  X             X         X         X   \           /         /         / \    X         X         X         X   X   /                   /  X                   X                       \                        X

    would yield TRUE for tree a), but FALSE for trees b), c), and d).

    Design your own prototype, and show an initial call. An empty tree or just a single node should return TRUE. Be careful about your choice of parameters.

    Code in the language of your choice, and include a declaration of your data structure.

  1. Consider two processes interacting with semaphores:

  2. Semaphore A = 0;  // initialization of semaphore  Semaphore B = 1;    P0:                       P1:    while (true) {            while (true) {      wait(A);                  wait(B);          signal(B);                signal(A);      signal(B);                wait(B);    }                         }

    In each of the following two parts below, draw a Gantt chart illustrating the execution of the processes. Assume initially that P0 is in front of P1 in the ready queue. A short-hand notation: P1:W(B) indicates that process P1 executes wait(B) without blocking, and P1:W*(B) indicates that P1 blocks on B. Each Gantt chart should consist of 11 semaphore calls.

    a) Use First-Come First-Served (FCFS) scheduling.

    0 1 2 3 4 5 6 7 8 9 10

    b) Use Round Robin (RR) scheduling where one time quantum is represented by one box in the Gantt chart, that is, a semaphore call uses exactly one time quantum.

    0 1 2 3 4 5 6 7 8 9 10

  3. Consider disk arm scheduling algorithms First-Come First-Served (FCFS), Shortest-Seek-Time-First (SSTF), and LOOK. Assume that the disk has 101 blocks numbered 0...100 and that the system is currently processing a request for block number 50. Now, four more requests for particular blocks arrive, one after the other, before the processing of block 50 finishes. The point of this problem is to select the four block numbers, and the order in which the requests arrive, to demonstrate that one algorithm might be better than another algorithm. A "better" algorithm is one in which the disk arm travels a lesser distance for that particular sequence of block requests.

    a) For just this first part, you are given the 4 blocks which follow 50:

    50 ___45 ___25 ___60 __100

    Draw the disk arm movement for FCFS and for SSTF, and accumulate the total distance for each algorithm.

    b) Now, pick your own set of 4 blocks such that FCFS is worse than SSTF. List this sequence on your solution paper and, again, draw the arm movement, and accumulate the distance for each algorithm.

    50 _____ _____ _____ _____

    c) Repeat, but such that LOOK is better than FCFS. Again, prove your result. Of course, it might be easy to do this just because of the current direction of the swinging arm movement. To eliminate this coincidental case, assume that the number which arrives immediately after block 50 determines the initial direction of the LOOK arm movement.

  4. Construct a 4-bit binary counter using T or JK flip-flops. There is only one input x.

    x = 1: increment the 4-bit value (on the clock pulse)
    x = 0: do not change the value

  1. Consider the definition (syntax) of a BOOK. A book has a book title, followed by a table of contents, followed by chapters. The table of contents has a listing of chapter titles, along with the page number (of the first page) of each chapter. A chapter itself has a chapter title, and many pages, each with their own page number at the end of the page itself.

    Do NOT consider any more detail of a page (i.e. sentences and words are not relevant here). A book may be in the construction phase in that it has ZERO chapters, or a chapter may have ZERO pages.

    Construct a Backus-Naur Form (BNF) grammar for a book. Do not use Extended BNF (EBNF).

    Assume the existence of these terminal symbols (tokens): title, number, page

  2. Consider the following routine to solve the Towers of Hanoi problem.

    void movetower(int n, char start, char finish, char temp) {  // Move a tower of n discs from the start rod to the finish rod, using  // the temp rod for auxiliary storage.    if (n == 1)      cout << start << " to " << finish << endl;    else {      movetower(n-1, start, temp, finish);      cout << start << " to " << finish << endl;      movetower(n-1, temp, finish, start);    }  }

    a) Write a recurrence relation for M(n), the number of times a disc will be moved for a call of size n. (This will be the number of times a cout statement is executed.)

    b) Solve the recurrence. Your answer should be a precise function of n in closed form. (An asymptotic answer is not acceptable.) Show the work you did to obtain the solution.

  3. For each of the following 7 languages, state whether the language is

    a) regular or not regular
    b) context free or not context free
    c) Turing-decidable or not Turing-decidable

    This means you will have 21 answers.

    Recall: Turing-decidable is also called "recursive" or simply "decidable".

    i) {w: w contains more a's than b's}
    ii) {a* b*}
    iii) {an bn : n >= 0}
    iv) {an bn cn: n >= 0}
    v) {an bm cn: n, m >= 0}
    vi) {p: p is a valid C++ program that halts on all properly formatted input}
    vii) {p: p is a syntactically correct C++ program}