There are four problems in this homework. The first two are based on our discussion of Recursion (Section 3.5), and the next two are based on our discussion of
Chapter 4 (Analysis Tools).
## Problem A

Given an array *arr* of integers, we want to rearrange its entries
so that all even integers come before the odd ones. The method
*arrange(int [] arr)* from here does
this by invoking a recursive method *recArrange(int [] arr, int left, int right)* that rearranges the sub-array *arr[left..right]* so that
all even integers occur before the odd ones. Complete the method
*recArrange* by supplying the arguments to its two recursive calls.
(2 points)
## Problem B

We say that a string is a palindrome if it is the same when reversed. For
example, *racecar* is a palindrome, while *abdaba* is not.
The method *isPalindrome(String s)* from
here checks is *s* is a palindrome by invoking a recursive
method *isPalindrome(String s, int left, int right)*. The method
*isPalindrome(String s, int left, int right)* checks if the
substring *s[left..right]* of *s* is a palindrome.
Complete the method *isPalindrome(String s, int left, int right)*
by filling in a suitable base case and supplying the arguments for
a recursive call that it makes. (1 point)
## Problem C

This question has five parts. They correspond to reinforcement problems
R-4.35, R-4.36, R-4.37, R-4.38, and R-4.39 of Chapter 4. The problems
are reprocuced here for your convenicence. Each of them is worth 1
point, for a total of 5.
- Algorithm A executes an
*O(log n)*-time computation for each
entry of an *n*-element array. What is the worst-case running time of
Algorithm A?
- Given an
*n*-element array *X*, Algorithm B chooses *log n*
elements in X at random and executes an *O(n)*-time calculation for each.
What is the worst-case running time of Algorithm B?
- Given an
*n*-element array *X* of integers, Algorithm
C executes an *O(n)*-time computation for each even number in
*X*, and an *O(log n)*-time computation for each odd number in
*X*. What is the worst-case running time of Algorithm C? What about
the best-case running time? (Even though we didn't define "best-case running
time" in class, interpret it in the way you think is most appropriate.)
- Given an
*n*-element array *X*, Algorithm D calls Algorithm E on each element *X[i]*. Algorithm E runs in *O(i)* time when it is called on element *X[i]*. What is the worst-case running time
of Algorithm D?
- Al and Bob are arguing about their algorithms. Al claims his
*O(n log n)
*-time method is *always* faster than Bob's *O(n*n)*-time (n-squared time) method. To settle the issue, they perform a set of experiments. To Al's dismay, they find that Bob's method runs faster if *n* is smaller than 100, and
only when *n* is larger than 100 is Al's method faster. Explain how this is possible.

## Problem D

An Array *A* of length *n* contains integers from the range
[0,..,n-1]. However, it only contains *n-1* distinct numbers. So
one of the numbers is missing and another number is duplicated. Write a
Java method that takes *A* as an input argument and returns the
missing number; the method should run in *O(n)*. Program this as the *oddOneOut(int [] A)* method
by filling in the body of the *oddOneOut* method
from here. (2 points)

For example, when *A = [0,2,1,2,4]*, *oddOneOut* should
return *3*; when *A = [3,0,0,4,2,1]*, *oddOneOut* should
return *5*.

## Submission Instructions

For problems A, B, and D it suffices to submit the appropriately
modified version of the file Homework4.java from here. For problem C, submit a text file with your answers in the same dropbox
Homework4 on ICON.