1.1) In this lab, you will implement a “guess your name” game where the computer

Question

1.1) In this lab, you will implement a “guess your name” game where the computer finds a name in a sorted list of names. The computer will use this method to “guess” your last name:

Start out with a program that reads all names from the "last names" file at https://www2.census.gov/topics/genealogy/1990surnames/dist.all.last. Discard the statistical information. Sort the names, using Collections.sort.

Use this code outline:

What is the code for reading all names and sorting them?

Answer:

1.2) Now you will implement the method that guesses the name, called guessName.

At the beginning of the search, set low to 0 and high to the maximum index of the names list. Set mid to the average of low and high, then ask the user if the name comes before the list entry at index mid. Depending on the answer, update low or high. If low == high, ask if the name matches.

What is the code for your guessName method?

Answer:

Answer this question based on first 2 answers

1.3) How many entries does your names list have? How many guesses does your program need to make until it has guessed the user's name or given up? (Use big-Oh for your answer.)

Explanation / Answer

1.3)

The names list have 88799, enteries.

The guesses taken by program is based on Binary Search algorithm, the list of names is divided into halves and then it is to be figured out is the name is in left or rigth sublist, searchnig for the worst case of the algorithm gives

O(logn) as time complexity,

Now in above case guesses needed to find the user's name is:

O(log 88799) = O(4.94840808)

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.