CS111 Introduction to Computer Science Final Spring 2020
1
• Use your preferred text editor to type your answers, and then save the file in PDF format.
• Submit your answers on Gradescope by May 11th at 7PM.
• This exam is worth 300 points.
Students are expected to maintain the highest level of academic integrity. You should
be familiar with the university policy on academic integrity:
http://academicintegrity.rutgers.edu/academic-integrity-policy/

Violations will be reported and enforced according to this policy.

Use of external sources to obtain solutions to homework assignments or exams is
cheating and a violation of the University Academic Integrity policy. Cheating in the
course may result in penalties ranging from a zero on an assignment of an F for the
course, or expulsion from the University. Posting of homework assignments, exams,
recorded lectures, or other lecture materials to external sites without the permission
of the instructor is a violation of copyright and constitutes a facilitation of dishonesty,
which may result in the same penalties as explicit cheating.


Problem 1: Binary Search (50 points)

a) (10 points) Suppose we are performing a binary search on a sorted array,
numbers, initialized as follows:

int[] numbers = {-1,3,15,18,25,28,32,39,40,42,51,57,71,73,74,85,92};
int index = binarySearch (numbers, 32);

Write the indexes of the elements that would be examined by the binary search and write the
value that would be returned from the search. Refer to the binary search code reference sheet
posted.

Indices: _______________

Value returned: _______________



CS111 Introduction to Computer Science Final Spring 2020
2
b) (10 points) Suppose a sorted array of integers, a, contains no duplicate values.

(i) (6 points) Write a method findNumHigherThan that will return the number of array
elements higher than its integer parameter target. The value target is in the array.

When writing findNumHigherThan, call the method binarySearch to find the
location of target in the array. The method binarySearch works as intended (you do
not need to write this method):
/*
* returns the index of target in the array a;
* returns -1 if target is not found in the array
*/
public static int binarySearch(int[] a, in target){
//code not shown
}

Use the header below in writing your code.

public static int findNumHigherThan (int[] a, int target){}





(ii) (4 points) What is the big-oh running time of your method,
findNumGradesHigherThan? Explain your reasoning.



CS111 Introduction to Computer Science Final Spring 2020
3
Problem 2: MergeSort (10 points)

Trace the complete execution of the MergeSort algorithm when called on the array of integers,
numbers, below.

Show the resulting sub-arrays formed after each call to merge by enclosing them in { }.

For example, if you originally had an array of 5 elements, a = {5,2,8,3,7}, the first call to
merge would result with:
{2, 5} 8, 3, 7 ß Note after the first call to merge, two arrays of size 1 have been
merged into the sorted subarray {2,5} and the values 2 and 5 are sorted in array a

You are to do this trace for the array, numbers, below. Be sure to show the resulting sub-arrays
after each call to MergeSort.

int[] numbers = {23, 14, 3, 56, 17, 8, 42, 18, 5};




CS111 Introduction to Computer Science Final Spring 2020
4
Problem 3: Sorts (20 points)

Assume the existence of an UNSORTED ARRAY of n characters. You are to trace the
CS111Sort algorithm (as described here) to reorder the elements of a given array.

The CS111Sort algorithm is an algorithm that combines the SelectionSort and the InsertionSort
following the steps below:

1. Implement the SelectionSort Algorithm on the entire array for as many iterations as it
takes to sort the array only to the point of ordering the elements so that the last n/2
elements are sorted in increasing (ascending) order.
2. Implement the InsertionSort Algorithm to sort the first half of the resulting array
elements so that these elements are sorted in decreasing (descending) order.

For example, if the original array contained the characters
W A K M B Y C H
After the execution of step 1 of the CS111Sort algorithm, the array would contain
H A B C K M Y W
Notice the last half of the array is ordered in increasing order; The first half is unsorted.
After the execution of step 2 of the CS111Sort algorithm, the array would contain
H C B A K M Y W
Notice the first half of the array is ordered in decreasing order;

The result of the CS111Sort Algorithm is that the first half of the array is sorted in
DECREASING order and the last half of the array is sorted in INCREASING order.

Following the CS111Sort algorithm, write the results of EACH ITERATION of this
algorithm when implemented on the array of characters:
T E D R W B S V A

Also give the number of comparisons for EACH ITERATION and the total number of
comparisons for EACH SORT.

You may find it helpful to create and complete a table similar to the one below.

Iteration Resulting Array Number of Comparisons-Selection Sort
0 T E D R W B S V A ---
…
…

Iteration Resulting Array Number of Comparisons-Insertion Sort
0



CS111 Introduction to Computer Science Final Spring 2020
5
Problem 4: Recursion (75 points)

a) Consider the following recursive methods.

01. public class Recursion {

02. /* Assume that n is no less than 0 and no greater than the
03. length of the array a */
04. public static boolean m1(int[] a, int n) {
05. if (n <= 0) return true;
06. if (!m2(a[n - 1])) return false;
07. else return m1(a, n - 1);
08. }
09. /* Assume that num is never less than 2 */
10. public static boolean m2(int num) {
11. return m3(num, 2);
12. }
13. private static boolean m3(int num, int divisor) {
14. if (num < 2 || (num > 2 && num % divisor == 0))
15. return false;
16. if (divisor <= Math.sqrt(num))
17. return m3(num, divisor + 1);
18. return true;
19. }
20. public static void main(String[] args) {
21. int[] array = {6, 2, 5};
22. m1(array, 3);
23. }
24. }

(i) (10 points) Show the sequence of recursive calls to m2, including arguments, and the
return value for each of the following calls to the method m2:

Call Sequence of recursive calls to m2 Return value

m2(25)




m2(2)




m2(14)




m2(7)




m2(13)





CS111 Introduction to Computer Science Final Spring 2020
6
(ii) (4 points) Describe what is returned by the method call m2 for any n such that n>=2.


(iii) (10 points) Show the sequence of recursive calls to m1, including arguments, and the
return value for each of the following calls to the method m1. A call m1({2, 6, 5},
3) means that the first parameter integer array a has the values 2, 6, 5 and the second
parameter has value 3.

Call Sequence of recursive
calls to m1
Return value

m1({2, 6, 5}, 3)




m1({23, 3, 7, 33}, 3)




m1({23, 3, 7, 33}, 4)




m1({6, 3, 17, 21, 33}, 5)




m1({5}, 1)




(iv) (6 points) Describe what is returned by the method call m1(arr, n) for any integer
array arr and integer n such that 0 <= n <= arr.length.


(v) (30 points) Draw the call stack, or the call tree for the entire execution of the program
when you execute the command java Recursion. In each stack frame, include the
name and value of all arguments and local variables (you can omit the command-line
args). If you choose to draw the call tree, for each method call, you are required to give
the method name, and the value for each parameter.






CS111 Introduction to Computer Science Final Spring 2020
7
b) (15 points) Suppose that a piece of Java code is stored using a String array (e.g, String[]
code). Each line is one element of this array. Assume there is a method boolean
containsMethodCall(String line) that can check whether a line of code specified by
the parameter line contains a method call or not. If the parameter line contains a method
call, the method containsMethodCall returns true, otherwise returns false.

/**
* @precondition arr is non-null
* @precondition max is non-negative
* @precondition count is non-negative
*/
public static boolean noMoreThanNMethod(String[] code, int index,
int max, int count)

Given the method header shown above, write a recursive method to check whether the
parameter array code contains more than max methods. Specifically, if the number of
method calls in the piece of code specified by the parameter code is more than the number
specified by the parameter max, return false, otherwise return true. Use index to keep track
of which array index is being inspected in each recursive call and, count as a counter of the
number of method calls.

Assume that the parameter arr is not null, the parameter max is non-negative and the
parameter count is non-negative. Call the method containsMethodCall(String
line) to check whether a line of code contains a method call or not. Assume that
containsMethodCall works as intended. Assume that there is at most one method call in a
line of code.

Example:
public static boolean m1(int[] a, int n) {
if (n <= 0) return true;
if (!m2(a[n - 1])) return false;
else return m1(a, n - 1);
}

Considering the code given above. We will use the String array (whose name is
codeArray) shown in the table given below to store the code. Then we want to check
whether the code has more than 3 method calls by calling the method:
noMoreThanNMethod(codeArray, 0, 3, 0). Since the piece of code only has two
method calls, namely codeArray[2] and codeArray[3], the noMoreThanNMethod will
return true.

The String array codeArray
Array index String
0 public static boolean m1(int[] a, int n) {
1 if (n <= 0) return true;
2 if (!m2(a[n - 1])) return false;
3 else return m1(a, n - 1);
4 }
CS111 Introduction to Computer Science Final Spring 2020
8
Problem 5: OOP and Arrays (100 points)

This problem deals with items in stock on a grocery store. The Item class is given below:

public class Item {

private String name; // item name
private int quantity; // quantity currently in stock

public Item (String name, int quantity) {
this.name = name;
this.quantity = quantity;
}

public String getName () {
return name;
}

public int getQuantity () {
return quantity;
}

public void increaseQuantityBy (int quantity) {
this.quantity += quantity;
}

public void decreaseQuantityBy (int quantity) {
this.quantity -= quantity;
}

public String toString() {
return " (" + quantity + ") " + name;
}
}

You will be writing code for the Grocery class below.

public class Grocery {

private Item[] stock; // grocery items

/* Initializes Grocery's stock with capacity number of items */
Grocery (int capacity) {
stock = new Item[capacity];
}

/*
* Add the item with itemName add quantity items to stock.
* If itemName is already present in stock, increase the
* number of items otherwise add new item to stock.
*
* If itemName is a new item, insert at the first null
CS111 Introduction to Computer Science Final Spring 2020
9
* position in the stock array.
*
* After the insertion all items are adjacent in the array
* (no null positions between two items).
*
* Additionally, double the capacity of stock array if
* itemName is a new item to be inserted and the stock
* array is full.
*
**/
public void addItemToStock (String itemName, int quantity) {}

/* For the item with itemName decreases quantity items from
* stock. If quantiy is greater the the number of items in
* stock display “Not enough items”
*/
public void decreaseItemFromStock (String itemName, int quantity){}

/*
* Returns an array of items that have quantity equals to zero.
*
* The return array has to be completely full with no empty spots,
* that is the array size should be equal to the number of items
* that have quantity equals to zero.
*/
public Item[] getItemsToRestock () {}

/*
* Print all items in the stock array
*/
public void printAllItems () {}

/*
* Test client
*/
public static void main (String[] args) {

Grocery c = new Grocery(5);
c.addItemToStock("Apple", 35);
c.addItemToStock("Orange", 20);
c.addItemToStock("Rice 5 lb", 21);
c.addItemToStock("Coffee 1/2 lb", 42);
c.addItemToStock("Quinoa 1 lb", 12);

c.printAllItems();
StdOut.println();
c.addItemToStock("Tomatoes", 50);
c.addItemToStock("Coffee 1/2 lb", 30);
c.decreaseItemFromStock("Rice 5 lb", 4);
c.printAllItems();
StdOut.println();

c.decreaseItemFromStock("Orange", 20);
CS111 Introduction to Computer Science Final Spring 2020
10
c.printAllItems();
StdOut.println();

for (Item i : c.getItemsToRestock()) {
StdOut.println(i);
}
}
}

The output when the test client is executed using the command java Grocery is:

java Grocery
(35) Apple
(20) Orange
(21) Rice 5 lb
(42) Coffee 1/2 lb
(12) Quinoa 1 lb

(35) Apple
(20) Orange
(17) Rice 5 lb
(72) Coffee 1/2 lb
(12) Quinoa 1 lb
(50) Tomatoes

(35) Apple
(0) Orange
(17) Rice 5 lb
(72) Coffee 1/2 lb
(12) Quinoa 1 lb
(50) Tomatoes

(0) Orange


a) (45 points) Write the method addItemToStock to add an item into the grocery stock
array. The method will:
• Insert the item with itemName add quantity items to stock.
• If itemName is already present in stock, increase the quantity of the item, otherwise
add new itemName to stock.
• If itemName is not present in stock, insert at the first null position in the stock
array. After the insertion all items are adjacent in the array (no null positions between
two items).
• Additionally, double the capacity of the stock array if itemName is a new item to be
inserted and the stock is full.




CS111 Introduction to Computer Science Final Spring 2020
11
b) (20 points) Write the method decreaseItemFromStock to decrease/decrement the
quantity of an item from the grocery stock array. The method will decrease quantity
items for the item itemName from the stock array. If quantity is greater the current
number of item in stock print “Not enough items”.


c) (25 points) Write the method getItemsToRestock that returns an array of items that have
quantity equals to zero in the stock array. The return array size has to be the number of
items that have quantity equals to zero.


d) (10 points) Write the method printAllItems to print all items in the stock array.


CS111 Introduction to Computer Science Final Spring 2020
12
Problem 6: Complexity (75 points)

a) (30 points) Suppose we have an unsorted array of size and want to search for a particular
element. Two solutions are proposed:
• Use linear search (look at each element in order from index 0 to − 1).
• First sort the array with insertion sort, then use binary search.
(i) (10 points) What is the big-oh complexity of each of these proposed solutions?
(ii) (10 points) Which method would probably be better if we only have a single search
to run? Why?
(iii) (10 points) Which method would probably be better if we have millions of searches
to run? Why?
b) (10 points) Suppose we write an algorithm to search for contacts on Facebook by looking at
friends and friends of friends. If every person has friends, what is the big-oh complexity of
the search described by the pseudocode below, assuming we always use a depth of 2? (Hint:
draw the tree of searches for a few small values of ) Include an explanation (one sentence)
of how you reached your answer.
boolean search(Person person, String name, int depth) {
IF person.name == name
RETURN true

IF depth > 0 THEN
FOR each friend f of person
IF search(f, name, depth - 1) THEN
RETURN true

RETURN false
}

void main() {
// ... initialize network and person p1 ...
search(p1, "Voldemort", 2)
}

c) (15 points) Given the following Java code:
public static boolean f(int [] arr)
{
for (int i = 0; i < arr.length - 1; i++)
{
for (int j = i + 1; j < arr.length; j++)
{
if (arr[i] < arr[j]) // *HERE*
return false;
CS111 Introduction to Computer Science Final Spring 2020
13
}
}
return true;
}
(i) (12 points) Find the number of times the comparison marked by *HERE* will be
evaluated for each input:
i. {1, 2}
ii. {10, 20, 30}
iii. {30, 20, 10}
iv. {-4, 7, 1}

(ii) (3 points) For an array of size , what is the big-oh runtime of this code in the worst
case?
d) (20 points) For each of the following tasks, find the big-oh runtime:
(i) Find the maximum value in a sorted array of size .
(ii) Find the two largest values in an unsorted array of size .
(iii) Find whether an unsorted array of size has any duplicate values.
(iv) Find whether a sorted int array of size has any negative values.
(v) Find the row with the greatest sum in a 2D int array of size × .
(vi) Find the sum of the diagonal (from (0,0) to ( − 1, − 1)) in a 2D int array of size × .
(vii) Combine two sorted arrays of size 2⁄ into a sorted array of size .
(viii) Convert a 2D image of size × from color to grayscale.
(ix) Print all possible -digit binary numbers.
(x) Print an array of size by recursively printing the left half, then the right half (where
the base case is a singleton array, which can be directly printed).