Homework5: Implementing Binary Search
Due: In class on Thursday, February 28, 2008
Presentation By: Jesse & Shikha
The file FemaleNames contains ~10000 female names many of which were the top 1000 female names given to babies in each of the ten decades from 1900-2000 (the date information has been removed and some additional names have been added). Write a program that inputs these names and then enables the user to look for a particular name in this database. You will use Binary Search to find a given name.
Show the output of your program at least 6 successful searches and 3 unsuccessful searches. Do not hardcode these names in your program. Your program should run interactively, inputing one name at a time from the user (or standard input).
Note, there are duplicates in the file.
Extra credit: Empirically determine the average number of comparisons made by your binary search and compare that with the theoretical analysis of the algorithm. Write a discussion using the results obtained.
What to hand in:
0. A description of your overall algorithm.
1. A printout of the program.
2. A script showing the output of your program for each of the inputs.
3. Results of extra credit, if any.
Notes:
You may write the program in C, C++, Java, Python, or any other language of your choice.
Presentation:
Jesse & Shikha will give a presentation on this project.