CSC205::Assignment::#FinalAssessment02018

[0] Record the output...
static void knuth_taocp {  // The Art of Computer Programming 
   Stack stack = new Stack();
   Queue queue = new Queue();
   stack.push(2).push(20).push(400).push(20).push(5);
   queue.enqueue('*').enqueue('+').enqueue('-').enqueue('/');
   int answer = stack.pop();
   while (!queue.isempty()) {
      char op = queue.dequeue();
      int n = stack.pop();
      if (op == '*')      answer *= n;   // answer = answer * n
      else if (op == '+') answer += n;   // answer = answer + n
      else if (op == '-') answer -= n;   // answer = answer - n
      else                answer /= n;   // answer = answer / n
   }
   System.out.println(answer);  
   // hint:  answer % 10 == 0 && answer ≤ 310  evaluates to true
}
[1] Record the output...
static void ritchie_c() {   // dmr created C circa 1972
   char x[] = {'j','a','m','e','s',' ','g','o','s','l','i','n','g'};
   int y[] = {0,1,6};
   System.out.println(logname(x,y) + " is at Amazon Web services.");
}
static String logname(char a[], int[] b) {
   char[] c = new char[b.length];
   c[0] = a[b[0]]; 
   c[1] = a[b[1]]; 
   c[2] = a[b[2]];
   return new String(c);
      // Java API for the  public String(char[] value)  constructor:
      // "Allocates a new String so that it represents the sequence 
      // of characters currently contained in the character array argument. 
}
[2] Record the output...
static void stroustrup_cpp() {  // bs created C++ circa 1985
   double e = 4 / 2;
   int z = (int)e + 1;
   System.out.println(ez_compute(e, z));
}
static double ez_compute(double e, int z) {
   if (0 == z) return 1;
   return e * ez_compute(e, z - 1);
}
[3] Explain...
static void backus_fortran() {  // Fortran created circa 1957
  Number[] n = { new Byte((byte)110), new Short((short)205), 
                 new Integer(240),    new Long(120), 
                 new Float(230),      new Double(220), };
  int max = -1;
  for (int i = 0; i < n.length; i++) {
    int k = n[i].intValue();
    if (k > max) 
      max = k;
  }

Briefly explain the features in Java that result in the max variable being equal to 240 when the for() loop has terminated.

[4] It's tree time...
4a-4e use the following tree description.
 
   node: 50;  left: 10    right: 75
   node: 10;  left: 7     right: 15
   node:  7;  left: null  right: null
   node: 15;  left: 12    right: null
   node: 12;  left: null  right: null
   node: 75;  left: 60    right: null
   node: 60;  left: 55    right: 64
   node: 55;  left: null  right: null
   node: 64;  left: null  right: null

[4a] Record all of the leaf nodes.
[4b] Record the parent of node 60.
[4c] Record the sibling of node 64.
[4d] Record the grandparent of node 15.
[4e] No or Yes:  Node 75 has two children.
[5] One word hint: inheritance...

The boolean-expression new StringBuffer("java").equals(new StringBuffer("java") evaluates to false. What does this tell us about class StringBuffer?

[6] Worst-case runtime (Big-O)...

[6a] Let A be a sorted array of length n. Briefly explain why O(log n) binary search is more efficient than O(n) linear search.

[6b] Let A is an array of length n. Briefly explain why accessing A[0] and A[n-1] are both O(1) [constant time].

[6c] Let L be a singly linked-list of length n with no tail pointer. Briefly explain why accessing the first element of L is O(1) and accessing the last element is O(n).

[7] About abstract classes/methods...

If a class contains an abstract method, then the class must be declared abstract. Briefly explain the motivation for declaring classes and methods to be abstract.

[8] Let's visit every node in a tree...
Record the post-order traversal (left right root) for the following BST.
                           87
                         /    \
                        /      \
                      84        103
                     /  \       / \
                   68    86    90  109
                  /  \        /  \
                32   74      88   97
                    /  \
                  70   80
[9] No dups allowed...
Draw the BST for the following inputs. No duplicates are allowed.

               J A M E S G O S L I N G

the alphabet: ABCDEFGHIJKLMNOPQRSTUVWXYZ
numerically (Unicode): A < B < C < ...
[10] Degenerate trees...

Searching a BST is O(log n), but it can be O(n) when a BST becomes significantly out of balance.

The sorted array 3,5,7,8,11,12,14,15,21, when passed to the bsplit() method results in the following output: 11,14,15,21,12,5,7,8,3,.

   static void bsplit(int[] a, int beg_i, int end_i) {
      if (beg_i > end_i) 
         return; 
      int cur_i = beg_i + (end_i - beg_i) / 2;
      System.out.print(a[cur_i] + ",");
      bsplit(a, cur_i+1, end_i);
      bsplit(a, beg_i, cur_i-1);
   }

The bsplit() method is implemented using an algorithm that is similar to what?

[11] Stack or Queue? Linked-list with no tail...
This exercise is written in pseudo-code.
   head = null
   thompson_unix(new Node(240))
   thompson_unix(new Node(205))
   thompson_unix(new Node(110))
   x = torvalds_linux()

   thompson_unix(n) {
      if head is null
         head = n
      else 
         n.next = head
         head.next = n
   }

   torvalds_linux() {
      if head is null || list is empty
         return null
      rv = head
      head = head.next
      return rv
   }

Rename thompson_unix() and linus_torvalds() using either stack (push()/pop()) or queue (enqueue()/dequeue()) terminology.

[12] Stack or Queue? Linked-list with tail...
This exercise is written in pseudo-code.
   head = tail = null
   page_google(new Node(110))
   page_google(new Node(205))
   page_google(new Node(240))
   x = brin_google()

   page_google(n) {
      if head is null
         head = tail = n
      else
         tail.next = n
         tail = n
   }

   brin_google(n) {
      if head is null || list is empty
         return null
      rv = head
      head = head.next
      return rv
   }

Rename page_google() and brin_google() using either stack (push()/pop()) or queue (enqueue()/dequeue()) terminology.

[13] Record the output...

class Exception and "subclasses that are not also subclasses of class RuntimeException are checked exceptions."

   int x = 42, y = 0;
   try { int a = x / y; }
   catch (ArithmeticException e0) {
      System.out.println("integer divide-by-0; " + (double)x / y);
      String s = null;
      try { s.length(); }
      catch (NullPointerException e1) {
         try { minsky_ai(); }
         catch (Exception e2) {
            System.out.println("Marvin Minsky died at age 88 in 2016");
         }
      }
   }
   static void minsky_ai() throws Exception { throw new Exception(); }
[14] Fill in the blanks with OOP speak...

Java is a __(0)__ inheritance language. A class is an __(1)__ of variables and methods. class __(2)__ is the root of the Java class hierarchy. An object is an __(3)__ of a class. If class Cerf extends class Googler, then class Cerf is a __(4)__ of class Googler. If Cerf vint = new Cerf(), then object vint __(5)__ Googler object. Objects cannot be instaniated from an __(6)__ class. A class decared __(7)__ cannot be extended. If class AdaLovelace implements GraceHopper, then we know GraceHopper is an __(8)__ and not a class.

Each blank will be one of the following words: abstract, child or subclass, class, concrete, encapsulation, extends, final, implements, inherit, instance, instantiated, interface, is-a, multiple, Object, object, override, overload, parent or superclass, polymorphism, static.

Record your answers in the following way.

(0) _____________
(1) _____________
(2) _____________
(3) _____________
(4) _____________
(5) _____________
(6) _____________
(7) _____________
(8) _____________
[15] Another tree traversal...

The following is not a BST, but it is a binary tree and it can be traversed. Record the in-order traversal (left root right) for the following binary tree.


             or
              |
       +------+--------+
       |               |
    program        programmed
                      |
                +-----+
                |
                be
PREVIOUS |


Creator: Gerald Thurman [gthurman@gmail.com]
Created: 12 April 02019
Last Modified: Friday, 12-Apr-2019 03:55:36 MST