Problem 1 - 4 Final Exam Solutions

Problem #1




The function power_nt() below, which is not tail-recursive,

computes single-precision X raised to the unsigned int power N.

 

This problem is to:

 

1) create an equivalent function power_tr that transforms

power_nt() to be strictly tail recursive using the technique

shown in the module 2 lecture and class notes

 

2) create an equivalent function power_it that transforms

power_tr() to be iterative using the technique shown in the

module 2 lecture and class notes.

 

Note: this problem will be graded entirely on the application

of the techniques shown in the module2 lecture and class notes.

In other words, this problem is all about the techniques. Work

it out yourself: a function from the web will not serve the

purpose.

 

Include a description in the function headers of how you used

the techniques to transform the non tail-recursive to the tail-

recursive form and the tail-recursive to the iterative form.

Also use internal comments to provide specific details.

 

Do not clean up the code as it will obscure how you applied

the techniques.

/




Problem #2




This program counts the words in a collection of books available

online in plain text format from Project Gutenberg. The program

uses an ExecutorService to run the counting tasks concurrently.

 

The problem is to provide a WordCounter class that implements

Callable<Integer. The call() method counts the number of words

in its input and returns the count as an Integer.The WordCounter

is used in main() to submit tasks to an ExecutorService.

 

The WordCounter is constructed with a URL that represents the URL

of a book. The URL.openStream() method returns an InputStream that

can be used to read lines through a BufferedReader. The reader must

be closed after the last line is read.

 

Use a StringTokenizer on each input line to count the number of

* words, and keep a running total for all the lines.







Problem 3




 

The Counterfeit Coin problem is a reduce and conquer problem.

Given (N-1) genuine coins and 1 counterfeit coin that looks the

same but weights less, determine how to detect the counterfeit

coin using only a balance scale to compare equal numbers of

coins in the smallest number of weighings.

 

If the number of coins is even, compare the two halves and

the lighter half contains the counterfeit coin. If odd, set one

of the coins aside and compare the even number. If the two

halves are equal, the coin set aside is counterfeit. Otherwise

the counterfeit coin is in the lighter half. If only two coins

remain, the lighter one is counterfeit.

 

The problem size decreases by a factor of 2, so the algorithm

performs O(log2 n) comparisons, assuming that dividing and

weighing the coins are O(1) operations.

 

This program represents N coins as a string that contains (N-1)

REGULAR_COINs and 1 COUNTERFEIT_COIN. Substring comparison works

because COUNTERFEIT_COIN is lexically less than REGULAR_COIN.

It is efficient because a substring does not copy characters:

it just refers to the original string.

 

The problem is to implement the function findCounterfeit() that

takes a string representing the coins, and finds the index of

the counterfeit using only string length, substring, and string

comparison to divide the coins into piles and compare the piles

with the balance scale. Do use COUNTERFET_COIN or REGULAR_COIN

in this function.

 

Implement the solution either iteratively or recursively. If

* recursively, you may implement a supporting function if needed.







Problem 4




 

Given an even power-of-2 sized array of elements in

the following format:

[ a1, a2, a3, a4, ……, an, b1, b2, b3, b4, …., bn ]

 

The task is shuffle the upper and lower sub-arrays

without using extra space.

[ a1, b1, a2, b2, a3, b3, ……, an, bn ]

 

The algorithm uses a divide and conquer technique.

Logically divide the given array into half and swap

the second half elements of the lower sub-array with

first half element of upper sub-array. Recursively do

this for the lower and upper sub-arrays.

 

Here is the process with the help of an example with

an 8-element array.

[ a1, a2, a3, a4, b1, b2, b3, b4 ]

 

Split the array into two sub-arrays:

[ a1, a2, a3, a4 : b1, b2, b3, b4 ]

 

Exchange top-half elements of lower array with bottom-

half element of upper array:

[ a1, a2, b1, b2 : a3, a4, b3, b4 ]

'----' '----'

 

Recursively split the lower sub-array [ a1, a2, b1, b2 ]

into sub-arrays:

[ a1, a2 : b1, b2 ]

 

Again, exchange top-half elements of lower array with

bottom-half elements of upper array:

[ a1, b1 : a2, b2 ]

-- --

 

Recursively split [ a1, b1 ] into sub-arrays:

[ a1 : b1 ]

 

This array is size 2, so it is already merged.

 

Recursively repeat the above steps for the upper-arrays.