Question 1   (4 points)

Give us a tight upper bound in terms of n and m for the running time of the following methods.  (No need to justify your answer)

A  void  func(int  n,  int  m)  {

for(int  i=0;  i<n+m;  i++)  {

for(int  j=0;  j<200;  j++)  {

System .out .println("hello  world");

}

}

}

B  void  func(int  n,  int  m)  {

for(int  i=0;  i<n;  i++)  {

for(int  j=0;  j<i;  j++)  {

System .out .println("hello  world");

}

}

}

C  void  func(int  n,  int  m)  {

for(int  i=0;  i<n;  i++)  {

if  (  i  <  m)  {

for(int  j=0;  j<m;  j++)  {

System .out .println("hello  world");

}

}

}

}

D  void  func(int  n,  int  m)  {

int  k  =  1;

for(int  i=1;  i<m;  i++)  {

k  *=  n;

for(int  j=0;  j<k;  j++)  {

System .out .println("hello  world");

}

}

}

Question 2   (2 points)

Consider the method add(k,  element) which inserts an element at position k in an array list. This operation increases the size of the list by 1. Let n be the number of elements in the list, and let m be the number of slots in the underlying

array when the method is called (i.e. the list capacity).

Analyze the running time of this method and provide:

A  A tight lower bound, and

B  A tight upper bound.

Question 3   (3 points)

The following claim is not true. Give us a counterexample.

If f(n) 2    (g(n)) and f(n) 2    (h(n)) then g(n) 2 (h(n)).

Question 4   (3 points)

Recall the graphics language for drawing presented in the pre-recorded videos. The symbols, L and R mean turn left and right by 90 degrees, respectively, D means draw a line segment (and move the pen state one unit in the direction it’s facing), and [ and ] mean push and pop the pen state using a stack.

Write a sequence of symbols that generates the drawing below. Please note that the initial pen state is (0, 0, 0), none of the segments should be drawn more than once, and the pen should be lifted at most once.  (Please separate each symbol with a space)

Question 5   (3 points)

Given a stack s and a queue q, consider the following sequence of instructions:

s .push(11);

s .push(21);

s .push(36);

s .add();

q .enqueue(s .pop());

q .enqueue(s .pop());

q .enqueue(25);

q .mult();

where the method add() pops the stack twice and pushes the sum of the two popped items back onto the stack and the method mult() dequeues two elements from the queue and enqueues their product back into the same queue.     Assuming s and q are initially empty, what is the content of the queue (from head to tail order) after the instructions above are executed?  (separate each element with a space, e.g., 1 2 3)

Question 6   (2 points)

Suppose a circular array of size 4 is used to implement a queue.  Show the contents of the array after the following three operations:

enqueue(A)

dequeue()

enqueue(G)

Assume the array state before these operations is  [-  ,  P,  F,  -] where P is the head and - means empty.  Please write the content of the array using the same notation.

Question 7   (3 points)

A double-ended queue is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front or back.  Consider the following partial implementation of a generic class which represents a double ended queue.

public myDeque<E>  {

:

public myDeque()  {}

public  boolean  isEmpty()  { . . .}  //  returns  true  if  the  queue  is  empty,  false  otherwise public  void  addFirst(E  e)  { . . .}  //  adds  an  element  to  the  front  of  the  queue

public  void  addLast(E  e)  { . . .}  //  adds  an  element  to  the  back  of  the  queue          public  E  removeFirst()  { . . .}  //  removes  the  element  from  the  front  of  the  queue public  E  removeLast()  { . . .}  //  removed  the  element  from  the  back  of  the  queue

:

}

Write an expression and a statement that would replace ***BLANK_ONE*** and ***BLANK_TWO*** respectively and complete the method below.  The method takes as input an object of type myDeque and creates a new double ended queue with the same elements, but in the reverse order. The method can modify the input queue.

public  static  myDeque<E>  reverseQueue(myDequq<E>  d1)  {

myDeque<E>  d2  =  new  myDeque<E>();

while  (  ***BLANK_ONE***  )  {

***BLANK_TWO***

}

return  d2;

}

Question 8   (8 points)

We would like to write a method which takes as input a String representing a postfix expression and returns its value. You can assume that the input String the method receives is valid: it contains a valid postfix expression that can be evaluated to a single value, and operands and operators are separated by space characters (e.g.  "12  3  *  200 +").  You can also assume that operators are made up by a single character (while you cannot make assumptions in this regards about the operands), that only binary operators are supported, and that the following helper methods are available to us:

•  static  boolean  isDigit(char  d): returns true if d is a digit, false otherwise.

•  static  boolean  isValidOp(char  op: returns true if op is a supported operator, false otherwise.

•  static  double  evaluate(char  op,  double  x,  double  y): takes as input a character representing a valid op- erator and two integers. It returns the value of the expression y  op  x. For example: evaluate('+',  5 .0,  3 .0) returns 8.0, evaluate('/',  2 .0,  10 .0) returns 5.0.

Write four statements to replace ***BLANK_ONE***, ***BLANK_TWO***, ***BLANK_THREE***, and ***BLANK_FOUR*** respectively and complete the method.

public  static  double  evaluate  (String  exp)  {

Stack<Double>  s  =  new  Stack<Double>();

String  n  =  "";

for  (int  i=0;  i<exp .length();  i++)  {

char  c  =  exp .charAt(i);

if  (isDigit(c))  {

***BLANK_ONE***

}  else  if  (c  ==  '  '  &&  !n .equals(""))  {

***BLANK_TWO***

n  =  "";

}  else  if  (isValidOp(c))  {

***BLANK_THREE***

}

}

***BLANK_FOUR***

}

Question 9   (2 points)

Consider the following three Java files:

 

Which method(s) must the class Dog implement for the code to compile?

Question 10   (5 points)

Consider the following UML diagrams with two interfaces and one class which have been implemented correctly.

 

Which of the following snippets of code raises a compile time error? List all the options that apply.

A          Cyborg[]  c  =  new  Cyborg[0];

for  (Human  h   :  c)

h .think();

B

C

D

E

Machine m  =  new  Cyborg();

Human  h  =  (Cyborg) m;

Human  h  =  new  Cyborg();

if  (h  instanceof  Cyborg)

h .act();

Human  h  =  new  Human();

h .think();

Machine m  =  new  Cyborg();

m .move();

Question 11   (6 points)

Assume we have a partial implementation of the following classes:

public  class  Library<E>{

List<E>  collections;

:

}

public  class  Book{

String  title;

ArrayList<String>  authors;

:

}

Consider now the following partial snippet of code:

Library<Book>  x1  =  . . .

Library<Book>  x2  =  . . .

while  (x1 .compareTo(x2)  <  0)  {

for  (Book  b   :  x2){

for  (String  a  :  b .authors)  { . . .}

}

}

From what you can see, which interface(s) (Iterable, Iterator, Comparable) should the class Library and/or Book implement in order for the code above to compile correctly? Indicate only what it is strictly needed to make the code work.  (You should specify which class should implement which interface)

Question 12   (4 points)

Consider the set of positive even numbers E+  = 2, 4, 6, .... Write a recursive definition for this set.

Question 13   (5 points)

Prove using mathematical induction that 1 + 3 + 5 + 7 + . . . + (2n — 1) = n2  for any n  1.

Hint: Start by re-writing the summation of the sequence using the  notation.

Question 14   (4 points)

Consider using the algorithm for mergesort seen in class and assume you’d like to use it to sort the list {7,  6,  3, 11,  9,  81,  23,  8,  15,  1}.

What are list1 and list2 right before the last call to merge is executed?

Question 15   (4 points)

Consider the following list that has just been partitioned after executing the first step of quicksort as seen in class.

{4,  1,  2,  5,  7,  6,  8,  9}

List all the elements that could have been selected as pivot for the list above to represent a valid partition.

Question 16   (5 points)

Solve the following recurrence using backsubstitution, i.e., derive a closed-form expression exactly equivalent to T (n) (not in asymptotic notation). Show the steps you took to derive your expression. Answers that do not show the steps as seen in class will not receive full marks even if correct. As mentioned in class, for simplicity you can assume that n is a power of 2.

T (n) = 3 + 4n + 2 · T (n/2),    T (1) = 5

Question 17   (3 points)

Consider the following tree

 

Consider using the queue-implemented breath-first traversal seen in class to traverse the tree? Indicate the elements left in the queue (from head to tail) right after S is visited.

Question 18   (3 points)

A tree can be represented using strings as follows.

tree                       =    root    |    (  root    listOfSubTrees  )

listOfSubTrees    =    tree    |        tree    listOfSubTrees

Using the definition above, write the string that would define the tree displayed in the previous question.

Question 19   (5 points)

Write a recursive algorithm (you can use pseudocode) that takes as input the root of a tree and returns the number of internal nodes of the tree.

Question 20   (2 points)

Consider a binary tree whose pre-order traversal is J K L M N O P and whose in-order traversal is J M L N K P O. What is the post-order traversal of this tree?

Question 21   (4 points)

Assume the numbers 5; 9; 3; 7; 8; 4; 1; 2; 6 are inserted into an empty BST in that order.

A  Draw the resulting BST.

B  Give the pre-order traversal of the resulting BST.

C  Give the post-order traversal of the resulting BST.