CSE 114 – FALL 2017

Computer Science I
RECURSION REVIEW

Please read to the textbook, myProgrammingLab and the lecture notes to excel in the final exam.
Solutions to these questions shall be out by the end of Saturday (16th December, 2017).

Final Exam is scheduled for Monday, December 18, from 8:00 – 10:45 AM in Javits 101, 102,
and 110.
Locations subject to change. Professor Tripathi or Tashbook shall announce the exact locations
and seating arrangements on piazza or blackboard or via email.
Please be on time.
The exam is paper-based, and is CLOSED BOOK, CLOSED NOTES.
You may NOT use any electronic devices (computers, tablets, smartphones, calculators, etc.) for
any reason during the exam; even their mere visibility during the exam will be considered to
be evidence of intent to cheat, and will be treated accordingly.
Bring photo ID (student ID card, driver's license, passport, etc.) to the exam. We will check
IDs, and we will NOT accept exam submissions from anyone without an ID.

These are some practice problems that include only based on recursion.
Although there are better ways of solving the following questions (without using recursion), we
would recommend you to use only recursion.
This is only a sample and is not an exhaustive list. The final exam is comprehensive and shall
not be based only on recursion.
If any clarification is required, post it on piazza.
Please read the instructions carefully.
You can define the functions once and use them anywhere else.

Question 1.
(a) Given an array of integers, write a method selectionSort(int[] L) to implement
the selection sort, recursively.
(b) Write a function, binarySearch(int X, int[] L), which sorts the given list L
and searches for the element X, using the binary search algorithm, recursively.
 For Questions 2 and 3, you can use the jump start code provided.
For Questions 2 and 3, refrain from using loops or other local variables. The methods can be
implemented with the data given in the java file, without using loops and without creating
other local variables.
Question 2.
(a) Write a function setEqual(int[] L1, int[] L2) that finds if two sets,
represented as integer arrays with no duplicates, are equal as sets (i.e., the elements can
be in any order). Examples:
setEqual([1,5,7], [7,5,1,2]) returns false.
setEqual([1,5,7], [7,5,1]) returns true.
Hint: Two sets are equal if each one is a subset of the other.
(b) Write a function union(int[] L1, int[] L2) that finds the union of two sets
represented as integer arrays with no duplicates. The resulting set must also not contain
any duplicates. Examples:
union([1,5,7], [7,5,1,2]) returns [1,5,7,2] (in any order).
(c) Write a function collectNode(int[] L) which given a list of directed edges (e.g.
[[1,2], [3,4], [2,3], [5,6]]) returns the list of nodes in those edges
without duplicates (e.g. [1,2,3,4,5,6]). Example:
collectNodes([[1,2], [3,4], [2,3], [5,6]]) returns
[1,2,3,4,5,6] (in any order).
Question 3.
(a) Write a function findDirectlyReachable(int[] L1, int[][] L2) which
given a integer array of starting nodes L1 (e.g. [1,5]) and an integer array of directed
edges L2 (e.g. [[1,2], [3,4], [2,3], [5,6]]) returns the list of nodes
directly reachable from any of the starting nodes (i.e. using a single edge starting from a
starting node). Example:
findDirectlyReachable([1,5], [[1,2], [3,4], [1,3], [1,6]])
returns [2,6] (in any order, because 2 is directly reachable from 1, and 6 is directly
reachable from 5),
findDirectlyReachable([1], [[1,2], [1,4], [1,3], [1,6]])
returns [2,4,3,6],
findDirectlyReachable([1], [[6,1], [3,4], [2,3], [5,6]])
returns [].
(b) Write a function findReachableFrom(int X, int[][] L) which given a
starting node (e.g. 1) and an integer array of directed edges (e.g. [[1,2], [3,4],
[2,3], [5,6]]) returns the integer array of nodes reachable from X either directly
(i.e., using a single edge starting from X) or indirectly (i.e., using multiple links, for
example 4 is reachable from 1 because there is a link from 1 to 2, from 2 to 3 and from 3
to 4). Example:
findReachableFrom(1, [[1,2], [3,4], [2,3], [5,6]]) returns
[2,3,4] (in any order),
findReachableFrom(1, [[1,2], [2,3], [3,1]]) returns
[2,3,1],
findReachableFrom(1, [[6,1], [3,4], [2,3], [5,6]]) returns
[].
Hint: You can apply findDirectlyReachable() from problem (a) recursively
starting with the starting node until its result is a fix point (applying
findDirectlyReachable() from the previous result will not yield any more
nodes).
Note: You can assume the predicate setEqual() and union() which was
implemented in Question 1, to be check that the result of
findDirectlyReachable() is a fix point, respectively, to continue to the next
iteration. Modifications might be necessary for the functions setEqual() and
union(), to handle 2D array.
(c) Write a function transitiveClosure(int[][] L) which given a list of directed
edges (e.g. [[1,2], [3,4], [2,3], [5,6]]) returns its transitive closure (i.e.,
the maximum list of pairs of nodes, such that one can reach from the first node in the pair
the second node in one or more hops. Examples:
transitiveClosure([[1,2], [3,4], [2,3], [5,6]]) returns
[[1,2], [3,4], [2,3], [5,6], [1,3], [2,4], [1,4]] (in any order).
Question 4.
(a) Towers of Hanoi.
There are n disks labeled 1, 2, 3, . . ., n, where 1 has the smallest diameter and n has the
largest and three towers labeled A, B, and C.
No disk can be on top of a smaller disk at any time.
All the disks are initially placed on tower A, with the smallest disk at the top and the
largest disk at the bottom.
Only one disk can be moved at a time, and it must be the top disk on the tower.
Write a method to print the sequence of steps that is required to taken to move all the
disks from A to B.
(b) Eight Queens.
The Eight Queens puzzle is to place eight queens on a chessboard such that one queen
cannot defeat another queen (i.e. no two queens are on the same row, same column, or
same diagonal).
Write a method to find the positions of the queens on an 8x8 2 dimensional array.
Question 5.
(a) McCarthy’s 91 function.
The McCarthy 91 function is a recursive function, defined by the computer scientist John
McCarthy as a test case for formal verification within computer science. The results of
evaluating the function are given by M(n) = 91 for all integer arguments n ≤ 100,
and M(n) = n − 10 for n > 100. Indeed, the result of M(101) is also 91 (101 – 10 = 91).
All results of M(n) after n = 101 are continually increasing by 1, e.g. M(102) = 92,
M(103) = 93. The function is defined as follows and you are required to implement this
in Java.
𝑛 − 10 𝑖𝑓 𝑛 > 100
𝑀𝑐𝐶𝑎𝑟𝑡ℎ𝑦(𝑛) = {
𝑀𝑐𝐶𝑎𝑟𝑡ℎ𝑦(𝑀𝑐𝐶𝑎𝑟𝑡𝑦(𝑛 + 11)) 𝑖𝑓 𝑛 ≤ 100
(b) The program of Young McML.
Tartan is a pattern consisting of crisscrossed horizontal and vertical bands in multiple
colors. You have to implement a function that prints the tartan of the Young McJava clan
that takes a number n as input and prints a matrix of n rows and n columns of interleaved
vertical and horizontal n and n-1 separated with spaces, starting with n.
Examples: tartan(4) would print:
tartan(3) would print: 4 3 4 3
3 2 3 3 4 3 4
2 3 2 4 3 4 3
3 2 3 3 4 3 4