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.

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.
   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.

   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.
      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?

      ---