This lab is worth 10 points and accounts for 12.5 percent of your laboratory grade. The points will be subjectively assigned by your TA based upon whether they believe you made a good faith effort toward complete the tasks that are assigned. Showing up on time, respecting your fellow classmates learning environment, and adherance to laboratory policies also factor into the determination of your score.
The following is an outline of the tasks for you to attempt during the lab period.
A framework containing the files and folders you will need can be found here. Download the .tgz file and decompress it in your account using the command:
tar -xzvf <file_name>
Inside the framework folder you will find a folder named guess_recursive. In this folder, implement a recursive function which guesses a number between 0 and 1,000,000 that you have chosen. The function should take the bottom number in the range, and the top number in the range as parameters. The function prototype is as follows:
In the body of the function, you should calculate the midpoint of the range and prompt the user whether that is the number that they are thinking of. The user should then enter "toolow", "yes", or "toohigh" to tell the program whether it's guess was too low, correct, or too high. If the guess was to low, the function should guess the number in the upper half of the given range. If the guess was correct, the function should return. If the guess was to high, the function should guess the number in the lower half of the given range.
Also, write a short main program which calls the guess_num function with the correct beginning range.
Modify the function that you wrote in part 1 so that the function returns the number of guesses that the program made in order to guess your number. Modify the main program so that after the program has guessed your number it tells you how many guesses it made.
Can you choose a number that will take the program more than 20 guesses to guess your number correctly?
Now that you've done a little bit of warming up on recursion, lets take on a slightly larger problem that also has a recursive solution. MergeSort is a common algorithm used to sort a list of items. In the folder mergesort write a function which performs meregsort on a list of integers. Create a list of random integers between 0 and 100,000 and give it to your algorithm to sort. Use the print_list function that you wrote in lab 9 to verify that your bubble sort algorithm works correctly.
If you finish implementing the MergeSort algorithm, try the following.
When people first start learning recursion they often say, "This is stupid, I could do the same thing without using recursion and it would be *so* much easier." Well, here's your chance. Inside the framework folder you will find a folder named guess_iterative. In this folder, try writing a program which does the same thing as the program from part 2 but does not use recursion.
How does the iterative solution compare with the recursive one? Which one used the fewest lines of code? Which one had the simplest control structure?