CSC231 Homework 9 2010
--D. Thiebaut 00:44, 2 December 2010 (UTC)
This assignment is due on Wednesday 12/8 evening, at midnight. It deals with recursion and binary search. You are encouraged to work in pairs on this assignment.
Contents
Assignment
We have seen a sketch of binary search in class, in Python. Your assignment is to write a program that creates a sorted array of positive double words, and allows the user to enter several numbers, one at a time, and for each one the program returns whether the number is in the array, and at what index it can be found. The program will keep on accepting keys from the user until this one enters the number -1, indicating that he or she is done.
Creating the Array
Your array should contain 1,000,000 sorted double-word integers. The first integer in the array should be 1. Figure out a way to create this large an array of sorted numbers without having to sort it. Be ingenious!
User interaction
Here is an example of how your program should interact with the user. Please make sure your program follows the same pattern, as it will be tested by another program that will behave just as the user behaves in the example below:
% ./hw9 Array of 1,000,000 integers initialized. please enter a number (-1 to stop): 12 12 is not in the array please enter a number (-1 to stop): 1000001 1000001 was found at index 788732 please enter a number (-1 to stop): -1 good bye %
Requirements
Your program should pass all its parameters through the stack.
Submission
Call your program hw9.asm, and combine it with driver.c, asm_io.asm, and asm_io.inc to generate the executable.
Submit your program as follows:
submit hw9 hw9.asm
Optional and Extra-Credit
- This is worth 1 full point, i.e. your grade can go from C+ to B+ if you fully implement this question. If you have an A to the first part, then you get A+ for the homework, and an extra 1/2 point to one of your other homework grades.
- Make your program output not only the index where the key was found, but also the number of probes required to find the key. A probe is defined as a comparison of the key to one of the items in the array.
- Here is an example of how your extra-credit program would work.
% ./hw9 Array of 1,000,000 integers initialized. please enter a number (-1 to stop): 12 12 is not in the array 21 probes performed during the search please enter a number (-1 to stop): 1000001 1000001 was found at index 788732 17 probes performed during the search please enter a number (-1 to stop): -1 good bye %
