UIT2201: Tutorial Set 6 (Fall 2016)
(Solution Sketch to Selected Problems)
** NOT TO BE GIVEN TO FUTURE UIT2201 STUDENTS **

Solution sketches are provided as guidelines only. Do not think of them as *model answers*. As you have noticed from our tutorial discussions, there can be many answers and approaches. So keep an open mind. (More importantly, DO NOT CIRCULATE these solution sketches.)

IMPORTANT NOTE:

(Common Error 1:) [Another off-by-1 error] For unsuccessful search, no comparison is done in the square-nodes. (There's no data-element in the square-nodes.) Some students wrongly added 1 comparison to the square-node.

(Common Error 2:) [Inconsistent-middle-element]
In binary search, if you use mid=(left+right)/2, then you *always* use the left-middle element.
If you use the formula mid=(left+right+1)/2, then you *always* use the right-middle element.
BUT, you NEVER use both left-middle AND right-middle.

Common Error 3:): [Standard Seq-Search is not smart]
The standard sequential-search algorithm is not smart. It scans all the n elements before it can conclude that the element is "not found". So, all unsuccessful searches takes n comparisons.

If you want to use the "smart" Seq-Search for sorted data, then do SAY SO!

T6-D1: (Analysis of Binary Search)

The search tree has 9 round nodes for successful searches; and 10 "fictitious square nodes" for unsuccessful searches; Also, this tree uses the middle element A[mid], where mid = (first + last)/2. (This gives the "left" middle element for even-sized sub-arrays.)

(a) Number of comparisons for the different successful searches:
  Amy:3, Becky:2, Cathy:3, Donald:4, Eve:1, Fish:3, Goldie:2, Howard:3, Leo:4

(b) Average (successful) = (3 + 2 + 3 + 4 + 1 + 3 + 2 + 3 + 4) / 9 = 25/9 = 2.67

(c) Number of comparisons for the different unsuccessful searches (use G1 to mean Gap1):
      G1:3, G2:3, G3:3, G4:4, G5:4, G6:3, G7:3, G8:3, G9:4, G10:4

(d) Average (unsuccessful) = (3 + 3 + 3 + 4 + 4 + 3 + 3 + 3 + 4 + 4)/12 = 34/10 = 3.40

Note: For big-data, like n=1,000,000, the avg successful search time is no more than 20 (between 19 and 20), and the avg unsuccessful search time is also no more than 20 (between 19 to 20 also).


T6-D2: (Detailed Analysis of Sequential Search)

(a) (The extended Search Tree for Sequential-Search)
  Amy -> Becky -> Cathy -> Donald -> Eve -> Fish -> Golden -> Howard -> Leo -> []
Note: There is only 1 fictitious square node for all unsuccessful searches.

(b) Number of comparisons for the different successful searches:
  Amy:1, Becky:2, Cathy:3, Donald:4, Eve:5, Fish:6, Goldie:7, Howard:8, Leo:9

(c) Average (successful) = (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9) / 9 = 45/9 = 5

(d) G1:9, G2:9, etc. For all the gaps, we need 9 comparisons.

(e) Average (unsuccessful) = 9 (always 9, so average is also 9)

The standard seq-search algo. needs to test all items before it can conclude "not found".
(Note: If we use the smart seq-search algorithm for sorted data, then things are different.)

Note: For n=1,000,000,
        the average successful search time is 500,000
        and the unsuccessful search time is always 1,000,000.


T6-Q3: (MeSM, MeBG, and MeCool)

(a) Easy and FAST to implement -- reuse the code from MeSM and MeBG. The two different search procedures have already been tested in their respective companies.
(This will buy time for the team to work on better solution for later versions.)

(b) Worst Case: _1000_ Average Case: _(1001)/2 = 500.5_

(b) Worst Case: _1000+20___ (Must first do unsuccessful search in MeSM, followed-by worst-case in MeBG (binary-search).)

UIT2201: CS & IT Revolution; (Fall 2016); A/P Leong HW