This page is archived

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.