Jill's number – Jack may not ask "What is your number?" but may ask "Is your number 6?" or "Is your number even and greater than 543?" How should Jack formulate his sequence of questions to find...

Apply algorithm 4.2.1 in P.146 with T=4, n=12 and A=(3,5,8,8,9,16,29,41,50,63,64,67). Draw the corresponding walkthrough as shown in P.146.

p j q p

1 6 12 True 16 False - -

1 6 11 True 16 False - -

1 5 10 True 9 False - -

1 4 8 True 8 False - -

1 1 2 True 3 True T is not in A

Is this correct?

Extracted text: Jill's number – Jack may not ask "What is your number?" but may ask "Is your number 6?" or "Is your number even and greater than 543?" How should Jack formulate his sequence of questions to find Jill's number most quickly; that is, with fewest questions (in the worst case)? Binary Search as given in Algorithm 4.1.2 makes three comparisons with each probe (i.e., asks 3 questions about each number it investigates). If we wanted to reduce the number of comparisons, we could modify it to search for the target value T by making exactly one comparison per probe until the sublist we're searching has only one entry and then testing to see if that single entry equals T. Algorithm 4.2.1: Binary Search #2 // version #2.0 Begin р+1; q + n; While (p < q)="" do="" j-[(p+q)/2];="" if="">< t)="" then="" p="" +j+1;="" else="" q="" +="" j;="" end;="" the="" if="" the="" while="" end;="" now,="" p="q" if="" (a[p]="T)" then="" output="" ("t="" is="" a[",="" p,="" "]");="" else="" output="" ("t="" is="" not="" in="" a");="" end;="" the="" if="" end.="" walkthrough="" with="" n="12" and="" a="(3," 5,="" 8,="" 8,="" 9,="" 16,="" 29,="" 41,="" 50,="" 63,="" 64,="" 67)="" a[1]="3," a[2]="5," a[3]="8," a[4]="8," |="" a[7]="29," a[8]="41," a[9]="50," a[10]="63," a[11]="64," &="" a[12]="67" a[5]="9," a[6]="16," %3|="" if="" t="9," then="" (using="" t="" for="" true="" and="" f="" for="" false)="" and="" t="" for="" target="">

Jun 05, 2022

SOLUTION.PDF

Jill's number – Jack may not ask "What is your number?" but may ask "Is your number 6?" or "Is your number even and greater than 543?" How should Jack formulate his sequence of questions to find...

Get Answer To This Question

Related Questions & Answers

Submit New Assignment