Problem Set 9. Posted 3/30

Notes: Of the three problems given below, one will be solved by the TAs in next week's discussion section, you will have to solve one in class, and the remaining problem is due in the lecture on Friday, 4/7.

1. Write a recursive function reverseList that takes a doubly linked list and reverses it. Use Lafore's implementation of a doubly linked list. The idea is this: if the given list is two or more links long, remove the first link, reverse the rest of the list, and reattach the removed link to the back of the reversed list. Your implementation should take time that is linear in the number of links in the list.

   Solution: Here is the solution. I have written a function called reverseList as part of the DoublyLinkedApp class. Here is the output I get when I run this program:

   p-lnx203.cs.uiowa.edu% java DoublyLinkedApp
   List (first-->last): 66 44 22 11 33 55
   List (last-->first): 55 33 11 22 44 66
   The list has been reversed.
   List (first-->last): 55 33 11 22 44 66
   List (last-->first): 66 44 22 11 33 55
   List (first-->last): 33 22 44
   List (first-->last): 33 88 22 77 44
   The list has been reversed.
   List (first-->last): 44 77 22 88 33
   p-lnx203.cs.uiowa.edu%
   

2. Here I have placed my implementation of a recursive "search with backtracking" solution of the n-Queens problem. Here are some questions about this code.
   1. The solution I get for an 10 by 10 chessboard contains a queen in position (0, 0). I want to know if there is a solution for the 10 by 10 chessboard that contains a queen in position (1, 0) (this is the second row, first column). Modify the program to answer this question.

      Solution: Here I have placed a modified Queens.java in which the main function places a queen at position (1, 0), marks all threatened positions, and then calls the function placeQueens to place the remaining 9 queens. Here is the solution I get by running the program.

      p-lnx203.cs.uiowa.edu% java Queens
      Type the chess board size.
      10
      Here is a placement of the queens.
      x x Q x x x x x x x
      Q x x x x x x x x x
      x x x x x Q x x x x
      x x x x x x x x Q x
      x x x x Q x x x x x
      x x x x x x x x x Q
      x x x x x x x Q x x
      x x x Q x x x x x x
      x Q x x x x x x x x
      x x x x x x Q x x x
      

   2. Inside the function placeQueens, there is a little question enclosed in comments, that I want you to answer. The question is reproduced below and I elaborate on the question here.

      	//**********************************************
      	// Earlier I had tried board = oldBoard. I got
      	// strange results. Why?
      	//**********************************************	
      

      Once we realize that the current placement of the queen is not going to work, we want to restore the board to how it was earlier and try a new position for the queen. To do this, I kept a copy of board (called oldBoard) before I updated it and then if the current placement of the queen did not work, I want to restore board, by copying oldBoard back into it.

      Without thinking too hard about this, in my first attempt, I simply used

      board =  oldBoard;

      and got strange results. You should try using this to see the results I got. Your task is to explain why I got those strange results.

      Solution: In Java parameters are passed to functions by value. When the 2-d integer array board is passed into the function placeQueens, a local copy of the reference board is made. However, this copy is also pointing to the same 2-d integer array. So any changes that are made to the array using the copy are reflected when we return from the function. However, if during the function, the local copy is made to point to something else, then any changes made via the local copy are lost when we return back from the function. Specifically, the assignment, board = oldBoard; makes the local copy of board point to a new 2-d array that oldBoard is pointing to. Any changes made to this array via board are made to the 2-d array and not to the original array that board was pointing to.

   3. One of our first recursion examples was a function for computing the nth Fibonacci number. Here is the function that we wrote in class:

      	int fibonacci(int n)
      	{
      		if((n == 1) || (n == 2))
      			return 1;
      		else 
      			return fibonacci(n-1) + fibonacci(n-2);
      	}
      

      This function is not very useful for computing large Fibonacci numbers. For example, when I used it to compute the 50th Fibonacci number, it took about a minute and returned the following answer:

      	serv15.divms.uiowa.edu% java FibonacciTest
      	Type a positive integer.
      	50
      	The 50th Fibonacci number is -298632863
      

      1. Why does the function return a negative number? Fix it so that it correctly computes reasonably large Fibonacci numbers. To verify your answer use your program to compute the 60th Fibonacci number. It should be 1548008755920.

         Solution This is due to integer overflow. The 4 bytes that Java sets aside for an integer is not large enough to store the 50th Fibonacci number. The solution below fixes this problem.

      2. In our discussion in class, we remarked that the source of this function's inefficiency is that it does not remember Fibonacci numbers calculated earlier and recalculates them as needed. To fix this, declare an array called answers that is responsible for storing answers already computed. This could be a global variable, that is initialized to all zeros, with the exception of the first two slots. answers[0] and answers[1] will contain fibonacci(1) and fibonacci(2) respectively and therefore will both be initialized to one. In general, the kth Fibonacci number would be stored in answers[k-1] as soon as it is computed. We could then modify the function fibonacci so that it first checks answers[n-2] for fibonacci(n-1) and answers[n-3] for fibonacci(n-2) and makes recursive calls only if these values have not already been computed. Make this change to the function fibonacci. Does it give you the speedup you were anticipating? Can you use this to calculate the 100th Fibonacci number?

         Solution: Here is the program that contains an efficient, recursive fibonacci function using the idea desrcibed above. It uses the BigInteger class to represent integers in arbitrary precision. Here is the output of two test runs of this function.

         p-lnx203.cs.uiowa.edu% javac FibonacciTest.java
         javap-lnx203.cs.uiowa.edu% java FibonacciTest
         Type a positive integer.
         100
         The 100th Fibonacci number is 354224848179261915075
         p-lnx203.cs.uiowa.edu% java FibonacciTest
         Type a positive integer.
         200
         The 200th Fibonacci number is 280571172992510140037611932413038677189525
         

      ---