CSC 17 Guide to Final Exam

The final exam will be comprehensive, with emphasis on the materials covered
after the midterm.  You will have to compare the different data structures
we've studied during the semester (circular queues, priority queues,
hash tables, AVL trees) in terms of their relative advantages.  You should
also be able to write segments of code using them.

Subjects to be covered:

       Data Structures, Algorithms and their Characteristics

1. Circular queue versus linked list, amortized versus worst-case complexity.

2. The Binary Heap data structure and its characteristics.

3. Hashtables.  Understand the roles of the key (versus value), what hash
   functions compute and how "hash collisions" are resolved.
   Difference between open hash tables (separate chaining)
   and closed hash tables (open addressing). 

4. Binary Search Trees and AVL trees.  Know the algorithms for
insert/delete.  Know how to apply the AVL rotations to rebalance trees
after insert and delete.  Study and understand the implementation of
BST using dynamic dispatch.  **You may have to write short fragments
of code in this setting** You will also be asked to determine the time
complexity of any functions that you have written.

5. Tries

6. Dynamic programming: when to use, how to use... Top down versus bottom-up
   dynamic programming.

   6b.  The Needleman-Wunsch algorithm in particular, including traceback.

7. Graph search; Dijkstra's algorithm and Algorithm A*.

8. Time complexity of various algorithms on data structures.
   Typical recurrence relations and how to evaluate the complexity
   of recursive algorithms.


                  Advanced Programming Techniques:

1. Classes, inheritance, interfaces, abstract classes. Techniques
   including how and when to type cast.

2. Functional interfaces and lambda expressions.  Know how to write
   lambda expressions that are required to implement an interface.
   
   2b. Where to use `? super` and `? extend`

3. Monadic error handling with java.util.Optional.  Know how to use
   the map, flatMap, orElse, isPresent, ifPresent, ifPresentOrElse
   operations.


=========================================================================
     Practice Problems, sample solutions posted separately.

   (These questions are somewhat on the hard side by design)
----------------

1. Consider the following class structure for (unbalanced) 
   binary trees of integers.

interface node
{
  boolean empty();
  //...
}

class nil implements node
{
  public boolean empty() {return true;}
  //...
}

class vertex implements node
{  int item;         // simplified to an int (don't call .compareTo!)
   node left, right;
   vertex(int h, node l, node r)
     {item=h;  left=l;  right=r;}
    
   public boolean empty() {return false;}
   public boolean leaf() { return left.empty() && right.empty();}
   //...
}

// 1a Write a function to return the total number of nodes in the tree.
add it to the interface and both subclasses.  Choose a recurrence relation
that would describe it's time complexity in BOTH the average and worst
cases.  

// 1b Write a function to search for a value in a binary search tree.
// Determine also its average time complexity class by writing a 
// recurrence relation

2. Given the above class, consider the following code:
   
   nil Nil = new nil();  // single instance of empty tree
   node A = new vertex(6, new vertex(4,Nil,Nil), Nil);

   Explain if the following lines of code are valid, and if not valid,
   whether it will cause a compiler error or runtime error:

2a.   node i = A.left;

2b.   node i = ((vertex)A).right;

2c.   int x = ((vertex)i).item;  // where i is from above

3. Show how to augment (edit) the existing interface classes to implement
   an operation on trees that determines if x is an item in the tree:

   boolean search(int x)

3b. What are the average and worst case complexity classes of your program.

3c. Given the following tree:

      5
    /   \
   2     7
  / \   / \
 1   4 6   8
            \
             9
What order will the values be printed using an INORDER, PREORDER and POSTORDER
traversal.


4. What are the worst-case time complexities of the following operations:

   a.  inserting into priority heap
   b.  searching for a value in a priority heap
   c.  searching for a value in a hash table
   d.  searching for a value in an AVL binary search tree
   e.  Dijkstra's algorithm in general
   f.  removing a value from an AVL tree
   g.  removing a value from the end of a cicular queue
   h.  an in-order traversal on an AVL tree.

4b. What are the (amortized) average case complexities of the following
    operations:

   a. inserting into a priority heap
   b. inserting into an AVL tree
   c. inserting into a hash table


5. Consider the following recursive function:

   int bif(int n)
   {
     if (n<2) return n;
      else return bif(n-1) * bif(n-2);
   }

 5b. Rewrite the program using a dynamic programming matrix.  You may
     choose between bottom-up and top-down dynamic programming (note:
     these simple problems may not actually require dynamic programming
     but you're asked to apply the technique anyway):

 5c. Do the same for this:

  int k(int n, int c)
  {
     if (n<1 || c<2) return 0;
     return Math.max(k(n-1,c), k(n-1,c-2)+2);
  }
 

6.  Explain the difference between nodes in the closed/interior and nodes
    on the open/frontier in Dijkstra's algorithm. 

7. Insert the following nodes into an AVL tree. Show when (and what) rotations
are required.  2 8 6 1 3 9.  Insert additional nodes (make up your numbers)
so that all 4 rotations are used.

8. Give a specific example of deleting from an AVL tree where more
than one rotation is required to balance the tree. There are four
distinct rotations: LL, RR, RL and LR, the rotations "RL" and "LR"
should be counted as ONE rotation, not two.
(If I ask this, it would be considered one of the harder questions.)

9. What's wrong with the following code. Pinpoint where the error is and
   explain why it's an error (don't say how to fix the error).  

   public abstract class shape implements Comparable<shape> {
     public int x, y; // position of shape
     public abstract int area();
     public int compareTo(shape other) {
        return this.area() - other.area();
     }
     public shape(int x0, int y0) { x=x0;  y=y0;}
   }
   //... in some other class:
   public static void main(String[] args) {
      shape[] A = new shape[10];
      for(int i=0;i<10;i++) A[i] = new shape(i,i*2);
   }

10.  Assume that you want to represent a SET of integers (these
integers can, for example, index some values in an array).  You want
to be able to insert, delete and search for values in the set with
maximum efficiency. Furthermore, you also want to be able to determine
quickly both the smallest and the largest index of the "set".  For
example, if the set consists of {3,2,6,1,8,7}, you want to be able to
determine quickly that the smallest value of the set is 1 and that the
largest is 8, as well as be able to search/insert/delete other values.
What kind of data structure would you use and WHY?

11.  Determine the output of the following program:

class A {
    int f() { return 1; }
}

public class B extends A {
    @Override
    int f() { return 2; }
    
    int g(A x) { return 10; }
    int g(B x) { return 20; }    

    public static void main(String[] args) {
        A a = new B();
        B b = new B();
        System.out.println( a.f() );
        System.out.println( b.g(a) );
    }    
}


12. Given the following local variables inside some function:

     Optional<String> Aopt;
     String A;

  a. Write code to print the string inside the optional if it exists

  b. Assign A to the string inside Aopt if it exists, and to "" if it doesn't

Under no circumstances can your code throw an exception.


13. Assume:

class A
{
   public void f() {}
}

class B extends A
{
  public void g() {}
}

...

A m = new A();
A n = new B();


// determine if there's an error in the following code, and whether
// it's a compiler or runtime error:

a.  n = m;

b.  n.f();

c.  n.g();

d.  ((B)n).g();

e.  ((B)m).g();


14. Given a Trie with strings as keys, what advantages would a trie have
    over a hashmap? (hint: this is best answered by an example)

   14a. explain why not all "nodes" in a trie contain values.
   (hint: this is best answered by an example)

   14b. Assume that the trie contains n nodes and m values, what is
   the worst case time complexity of searching, inserting or removing a
   value from the trie?
    

15. Explain how Dijkstra's algorithm avoids cycles.

15b. What is the absolute worst case time complexity of Dijkstra's
algorithm in terms of the number of possible nodes (vertices) in
graph.


15c.  Given the following weighted, DIRECTED graph

  A ----4----> B ----1----> F
  |            |            |
  9            2            3
  |            |            |
  |            |            |
  v            v            v
  C <----2---- D ----3----> E

Apply Dijkstra' single-source shortest path algorithm to source node A

Apply Dijkstra' single-source shortest path algorithm to source node B


16. Apply the Needle-Wunsch algorithm to the following sequences:

A=    .ATGACTG
B=    .TGATGC

with the following scoring scheme:

  int score(int i, int k) {
     if (A.charAt(i)==B.charAt(k)) return 1; else return 0;
  }
  int W() {return 0;}

Show the matrix generated by the algorithm.
Display one optimal alignment (traceback) (without the . at the front)

How about under the following Scheme:

   int score(int i, int k) {
        if (A.charAt(i) == B.charAt(k)) return 2;
        else return -1;
   }
   int W() { return -1; }


17.  java.util.function.Function is an interface equivalent to:

interface Function<A,B> {
  B apply(A x);
}

Explain what's wrong with the following declaration:

Function<? extends A, ? super B> myfunction;