CS1027b Computer Science Fundamentals II

Learning Outcomes

• Understand how to design simple recursive algorithms
• Understand how to compare recursive and iterative algorithms

General Lab Instructions

• Read through the lab instructions before coming to the lab.
• Read the lecture notes on queues and lists.
• Download file AnswersLab10.txt and open it with a text editor.

IMPORTANT. Submit the .java files that you write for this lab and AnswersLab10.txt through OWL by 11:55pm on Friday, March 27.

Exercise 1: Iterative vs Recursive Algorithms

1. Initially prev stores the first Fibonacci number and current stores the second one.
2. Then compute the next Fibonacci number by adding the previous tow ones: next = prev + current.
3. Finally, store in prev and current the last 2 Fibonacci numbers: prev = current and current = next.
4. Repeat steps 2 and 3 until the n-th Fibonacci number has bee computed.

• The first and second Fibonacci numbers are 1 and 1
• The i-th Fibonacci number is equal to the sum of the (i-1)-th and the (i-2)-th Fibonacci numbers

• Run the program and when asked enter the number 20, 30, 40, 45, 50. Enter the running times reported by the algorithm in AnswersLab10.
• Modify the program so it also prints the number of calls that are made to method rfib when the value of the parameter n is 2. Run the program and when asked enter the value 40. How many calls are made to rfib when the value of the parameter n is 2? Write your answer in AnswersLab10.
  Hint. Declare an instance variable methodCalls2 and increase it in method rfib whenever n = 2.
• Explain why the recursive algorithm for computing Fibonacci numbers is so slow compared with the iterative algorithm. Write your answer in AnswersLab10.

  Exercise 2: More Iterative vs Recursive Algorithms

  The Abo series is the following: 0, 1, 2, 4, 3, 6, 5, 5, 4, 8, 7, 7, 6, 7, 6, 6, 5, 10... This series is defined in the following manner:
  • Abo(n) = 0 for n <= 0
  • Abo(1) = 1
  • Abo(n) = 1 + Abo(n/2) if n > 1 is even
  • Abo(n) = 2 + Abo((n+1)/2) if n > 1 is odd
  Write a recursive method that computes Abo(n). Write a program that prints the first 20 Abo numbers: Abo(0), Abo(1), Abo(2), ..., Abo(19).
  Try to write an iterative method that computes Abo(n). Explain why this algorithm is difficult to design. Write your answer in AnswersLab10.

  Exercise 3: Permutations and Recursion

  Given a sequence of characters, in this exercise we examine the problem of printing all possible permutations of these characters. For example, for the sequence of characters "car", the possible permutations are "car", "cra", "acr", "arc", "rca", and "rac".
  Write a recursive method called permutations(String prefix, String suffix) that receives as parameter a String suffix and an initially empty String prefix (i.e. initially prefix = "") and it prints all permutations of the characters in suffix. You also need to write a program that asks the user to enter a string, and it prints all permutations of the characters in that string.
  This is another example of a problem that would be very difficult to solve using an iterative algorithm. However, the following short recursive algorithm can be used to solve this problem. Parameter prefix will store a permutation of several of the characters of the original string, while suffix will store the remaining (and not yet permuted) characters of the original string.
  • The base case is when suffix is equal to the empty string "". In this case prefix contains a permutations of all the characters of the original string, so the algorithm must just print prefix.
  • If suffix is not the empty string, then the algorithm will consider each one of the characters c of suffix and for each one of them it will do the following:
    • remove character c from suffix to get a new string suff
    • append c to prefix to get a new string pre
    • invoke permutations(pre,suff)
  Method length() returns the length of a string, and method charAt(i) returns the character of a string with index i. To concatenate a character c to a string prefix use c+prefix. The following algorithm can be used to remove the character at index i from a string s:
  private static String removeChar(String s, int i) {
     return s.substring(0,i) + s.substring(i+1,s.length());
}