Purpose: To demonstrate your understanding of analyzing algorithms. Starting with this assignment, only the testing needs to be on empress.csusm.edu
------------------------------------------------------------------------------------------
A) Review Questions [1 pt per question = 10pts]
Your score is:
Type your answers here
1)
What does W(n) mean? (W? N? W(N)?)
A. What is W(n) of sequential search? The W(n) of a sequential search would be n. B. When does it happen?
What does B(n) mean? (B?, N?, B(N)?)
A. What is B(n) of sequential search? .
B. When does it happen?
Why is A(n) difficult to determine for the real world problems?
Why don’t we care about constants and lesser terms in a time complexity expression?
Prove that 3n^2 + 4n = O(n^2) as I did in the notes.
Binary search corresponds to the shortest binary decision tree.
Sequential search corresponds to a tallest tree.
Thus, the fastest ordered list search does W(n)=Theta(log2n) comparisons.
But, the fastest unordered list search does W(n)=Theta(n) comparisons.
B) Programming Binary Search [10 pts] Your score is:
No ADT; Just one source code file - Run my solution program first
Using Notes-3B.doc, implement and test the binary search function.
The pseudo code in the file does not take care of the cases where the element is not found. You must fix the code to take care of such cases and return -1.
Your main() will fill an array of 10 slots with integers 1 3 5 7 9 11 13 15 17 19 It will then ask the user to enter a number to look for.
It will then call binarySearch and display the returned result.
e.g. “The number was found in position 5”
Required Testing and expected results: (must test in this order!;)
Find 1 in position 1 (It is not position 0!)
Find 19 in position 10
Find 5 in position 3
Find 17 in position 9
Find 21 fails
Find 0 fails
Find 6 fails
NOTE: Do you think I listed all possible cases? Always ask yourself if there are other cases you should test to make sure your program is bug free.
Q. State of your program [2pts]
Does your program compile without errors? If not, describe.yes
List any bugs you are aware of, or state “No bugs”: no bugs
Submit these 3 files:
This assignment sheet with your answers.
Binsearch.cpp: The source code file for the program with good comments.
Test: Script of the compilation and test results on Empress.
