CSE1030Z Week 09 Homework Problems

Previous Problem Set

• a previous set of 4 problems including proofs of correctness and termination
• hints
• full solutions

Short Problems

1. Implement a recursive method with signature
   
   int sum(int n)
   
   that computes the sum of the integers 1, 2, ..., n.
2. Implement a recursive method with signature
   
   long factorial(int n)
   
   that computes the factorial of n, n! = 1 * 2 * ... * n.
3. Implement a recursive method with signature
   
   String reverse(String s)
   
   that returns the string equal to the characters in s in reverse order. For example, reverse("banana") returns "ananab".
4. Implement a recursive method with signature
   
   String replace(char c, char with, String s)
   
   that returns the string equal to the string s with all characters equal to c replaced with the character with. For example, replace('a', 'u', "banana") returns "bununu".

Moderate Problems

1. Implement a recursive method with signature
   
   int binarySearch(List<String> t, String s)
   
   that uses binary search to find an element s in a sorted list t of strings. Binary search recursively examines the middle element of the list to determine which half of the list the target word s must lie in (much like the bisection method for root finding). Your method should return the index of the string s if it is in the list, otherwise it should return -1.

Coming soon.

Hard/Creative Problems

Coming soon.