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.
  1. 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?
  2. 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?
  3. 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.)
  4. 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?
  5. 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.