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).
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.
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)
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
- 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.
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
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.