Your code must be written in C and compile with the gcc compiler on replit.

Use the alphabet for all parts of this homework is:

" !.abcdefghijklmnopqrstuvwxyz"

Question 1

Implement a linear search typing program. Repeatedly ask the user what letter they are thinking until you get the right one. Stop when the user types the exclamation point.

Submit the code in the file main.c. You may supply additional files if you wish to. You main program must be in main.c.

Assumption: You may assume that the user will only type: y, Y, n, or N. The user will only enter exactly 1 character and will not enter any other characters. You do not have to provide any error checking on this input. Remember we are simulating a person who can only give us yes/no answers.

Assumption: You may assume the user will never type more than 100 characters before entering '!'.

Example Execution Trace:

 Are you thinking of the letter ' '? n Are you thinking of the letter '!'? n Are you thinking of the letter '.'? n Are you thinking of the letter 'a'? n Are you thinking of the letter 'b'? n Are you thinking of the letter 'c'? y Are you thinking of the letter ' '? n Are you thinking of the letter '!'? n Are you thinking of the letter '.'? n Are you thinking of the letter 'a'? y Are you thinking of the letter ' '? n Are you thinking of the letter '!'? n Are you thinking of the letter '.'? n Are you thinking of the letter 'a'? n Are you thinking of the letter 'b'? n Are you thinking of the letter 'c'? n Are you thinking of the letter 'd'? n Are you thinking of the letter 'e'? n Are you thinking of the letter 'f'? n Are you thinking of the letter 'g'? n Are you thinking of the letter 'h'? n Are you thinking of the letter 'i'? n Are you thinking of the letter 'j'? n Are you thinking of the letter 'k'? n Are you thinking of the letter 'l'? n Are you thinking of the letter 'm'? n Are you thinking of the letter 'n'? n Are you thinking of the letter 'o'? n Are you thinking of the letter 'p'? n Are you thinking of the letter 'q'? n Are you thinking of the letter 'r'? n Are you thinking of the letter 's'? n Are you thinking of the letter 't'? y Are you thinking of the letter ' '? n Are you thinking of the letter '!'? y You typed: cat 

Question 2

Implement a binary search typing program. Repeatedly ask the user what range of letters their letter is in until you get the right one. Stop when the user types the exclamation point.

Submit the code in the file main.c. You may supply additional files if you wish to. You main program must be in main.c.

Assumption: You may assume that the user will only type: y, Y, n, or N. The user will only enter exactly 1 character and will not enter any other characters. You do not have to provide any error checking on this input. Remember we are simulating a person who can only give us yes/no answers.

Assumption: You may assume the user will never type more than 100 characters before entering '!'.

Example Execution Trace:

 Is your letter between ' ' and 'l'? (y/n) y Is your letter between ' ' and 'e'? (y/n) y Is your letter between ' ' and 'a'? (y/n) n Is your letter between 'b' and 'c'? (y/n) y Is your letter between 'b' and 'b'? (y/n) n Is your letter 'c'? (y/n) y Is your letter between ' ' and 'l'? (y/n) y Is your letter between ' ' and 'e'? (y/n) y Is your letter between ' ' and 'a'? (y/n) y Is your letter between ' ' and '!'? (y/n) n Is your letter between '.' and '.'? (y/n) n Is your letter 'a'? (y/n) y Is your letter between ' ' and 'l'? (y/n) n Is your letter between 'm' and 's'? (y/n) n Is your letter between 't' and 'w'? (y/n) y Is your letter between 't' and 'u'? (y/n) y Is your letter between 't' and 't'? (y/n) y Is your letter 't'? (y/n) y Is your letter between ' ' and 'l'? (y/n) y Is your letter between ' ' and 'e'? (y/n) y Is your letter between ' ' and 'a'? (y/n) y Is your letter between ' ' and '!'? (y/n) y Is your letter between ' ' and ' '? (y/n) n Is your letter '!'? (y/n) y You typed: cat 

Binary Search has an optimization you must take advantage of here.

Sometimes there is no point in asking one of the questions.

Take the following example:

./main Is your letter between ' ' and 'l'? (y/n) n Is your letter between 'm' and 's'? (y/n) y Is your letter between 'm' and 'p'? (y/n) n Is your letter between 'q' and 'r'? (y/n) n Is your letter 's'? (y/n) y Is your letter between ' ' and 'l'? (y/n) y Is your letter between ' ' and 'e'? (y/n) y Is your letter between ' ' and 'a'? (y/n) y Is your letter between ' ' and '!'? (y/n) y Is your letter between ' ' and ' '? (y/n) n Is your letter '!'? (y/n) y You typed: s 

When we type s, there is no need to ask Is your letter between 's' and 's'? (y/n) but for space there is a need to ask Is your letter between ' ' and ' '? (y/n)

Let's look at why:

Alphabet: " !.abcdefghijklmnopqrstuvwxyz" Question: Is your letter between ' ' and 'l'? (y/n) Answer: n

Alphabet: "mnopqrstuvwxyz" Question: Is your letter between 'm' and 's'? (y/n) Answer: y

Alphabet: "mnopqrs" Question: Is your letter between 'm' and 'p'? (y/n) Answer: n

Alphabet: "qrs" Question: Is your letter between 'q' and 'r'? (y/n) Answer: n

Alphabet: "s" Question: Is your letter 's'? (y/n) Answer: n

The number of letters in the set was ODD. That means the options had to be 's. We can skip one question.

That will not be the case in the next example.

Alphabet: " !.abcdefghijklmnopqrstuvwxyz" Question: Is your letter between ' ' and 'l'? (y/n) Answer: y

Alphabet: " !.abcdefghijkl" Question: Is your letter between ' ' and 'e'? (y/n) Answer: y

Alphabet: " !.abcde" Question: Is your letter between ' ' and 'a'? (y/n) Answer: y

Alphabet: " !.a" Question: Is your letter between ' ' and '!'? (y/n) Answer: y

Alphabet: " !" Question: Is your letter between ' ' and ' '? (y/n) Answer: n

Alphabet: " " Question: Is your letter '!'? (y/n) Answer: y

This time, the range was even " !.a". That means when we cut it down we don't know if you want the space or the exclamation point.

We cannot save ourselves the extra question here.

Question 3

The Diving Bell and the Butterfly by Jean-Domininque Bauby was originally written in French. The first sentence of the book is translated to English below.

through the frayed curtain at my window a warm glow announces the break of day

Determine how many yes/no questions need to be asked to type out this sentence.

Punctuation and capitalization have been removed. These were added by an editor later.

Think about how your program work and try to calculate the exact number fo questions needed. You should be able to predict the answer without typing out the sentence yourself.

Write a short reflection on how both your programs worked. Answer the following:

About how many questions were needed to type the sentence using linear search?

About how many questions were needed to type the sentence using binary search?

If you were Jean-Domininque, which program would you rather use?

What was the easiest part of implementing this assignment?

What was the most challenging part of implementing this assigment?

Put your answers in a file readme.txt in the same assignment as your Binary Search implementation.