Fall 2006

  1. Select TWO sorting algorithms which are O(nlog n) on average. For each, state the name and describe, mainly with diagrams and pictures, how the algorithm works. Use the following example data of 10 integers:
  2. 44 77 3 9 15 12 32 24 51 19

    Do NOT write code. The description, diagram, etc. does not have to follow the algorithm to the end of sorting, just highlight the main aspects.

  3. Consider a singly-linked list of nodes, where each node contains an integer and a pointer.

  4. a) [7 points] Write an ITERATIVE function that returns TRUE (1) if the list has an EVEN number of nodes; otherwise return FALSE (0). Code in the language of your choice and include the declaration of your data structure.
    The prototype in C is:

    int even(node_ptr p)

    b) [10 points] Repeat using RECURSION.

    c) [3 points] State which solution is better and give a brief justification.

    Special Note: Using a counter is not allowed (NO CREDIT will be assigned).

  5. Consider these two binary trees, where the first tree consists of identical integer elements:
  6.         4                  2
      /   \              /   \
     4     4            5     5
    / \   /            / \
   4   4 4            8   2 
  /       \            \
 4         4            5
  \       /
    4    4

    The problem is: Given a binary tree (but NOT a key x), return TRUE (1) if every node in the tree contains exactly the same element. It does not matter what the value is, just that all values are the same. Otherwise, return FALSE (0). If the tree is empty, return TRUE.

    In the example, the function would return TRUE for the first tree, but FALSE for the second tree.

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

    Do not call any other functions, and do not do any type of ``counting''.

    The prototype in C is: int allSame(tree_ptr p);

  1. Consider page faults in a virtual memory system with demand paging. In particular, consider the behavior of First-In First-Out (FIFO), Least-Recently Used (LRU), Most-Frequently Used (MFU), and Least-Frequently Used (LFU) page replacement strategies. The physical memory has exactly 3 frames (0..2) and the logical memory has only 4 pages (0..3). In each of the following four parts, make up your own 5 element page reference string that guarantees exactly 1 page fault (beyond the 3 faults caused by demand paging) and:

  2. a) FIFO does not behave the same as LRU.
    b) FIFO does not behave the same as MFU.
    c) FIFO does not behave the same as LFU.
    d) LRU does not behave the same as LFU.

    In each case, show the contents of memory as each page is referenced.

  3. Consider the following variations of classical problems.

  4. a) Producer-Consumer system:

    const int N = 5;   // size of the bounded buffer
Semaphore A = N;   // initial value of the semaphore
Semaphore B = 0;   
Semaphore C = 1;   

Producer:                         Consumer:
  while (true) {                    while (true) {
    wait(C);                          wait(C);
    wait(A);                          wait(B);
    // produce into the buffer        // consume from the buffer
    signal(B);                        signal(A);
    signal(C);                        signal(C);
  }

    b) Readers-Writer system (assume the Writer is the standard solution):

    int readcount = 0;
Semaphore read_sem = 1;
Semaphore wrt_sem = 1;

Readers:
  while (true) {
    wait(read_sem);
    readcount++;
    if (readcount == 1) {
      signal(read_sem);
      wait(wrt_sem);
    } else 
      signal(read_sem);
    
    // reader reads from the file 
    
    wait(read_sem);
    readcount--;
    if (read_count == 0) signal(wrt_sem);
    signal(read_sem);
  }

    For both parts, describe how the solution performs correctly or what problems may exist with the solution.

  5. a) Show how to implement a half adder using 2 gates.

  6. b) Representing a half adder with a block diagram, show how to implement a full adder with 2 half adders and an OR gate.

  1. Consider this expression as a "selection" control structure on integer "x":
  2. 0 < x < 10,

    with the intention that the structure returns TRUE if "x" is in the range 1..9.

    a) Explain why a compiler should not accept this expression. (Note that the language has not been specified so you cannot just say, "It's a syntax error in C++/Java".) In particular, what are the issues regarding the binary operator?

    b) Explain how a prefix operator could be introduced so the expression can be successfully processed.

  3. a) Give precise definitions of

  4. i) f ∈ ο(g) ("little-oh")
    ii) f ∈ Θ(g) ("big-theta") .

    b) Let h1(n)=(n+1)! and h2(n)=n!.

    Exactly one of the following statements is true:

    i) h1 ∈ ο(h2)
    ii) h1 ∈ Θ(h2)
    iii) h2 ∈ ο(h1).

    Which one of the 3 statements is the valid one? Prove that your selection is correct. (Do not prove that the other 2 statements are incorrect.)

  5. Consider the following languages over the alphabet = {0, 1}:

  6. L1 = {w : w contains the substring 010}
    L2 = {w : w does not contain the substring 000}

    Give the state diagram for a Turing machine that decides the language L1 ∪ L2.