UIT2201: Tutorial Set 5 (Spring 2013)
(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.)

T5-D2: (Order of Growth of Functions) -- SOLUTION SKETCH
(a) The function 50n vs 0.5n2.       (b) The function 50n2 vs 0.5(2n).
Using Excel tables give better insight to the rate of growth of the functions.

T5-Q1: (5 points) [Searching and Query Processing] -- SOLUTION SKETCH 
Algorithm My-Query(Student-ID, Name, Major, Tel-Num, n, AnE);  
begin
  Print " Student-ID   Name  Major  Tel-Num";
  Print "==================================";
  k <-- 1;
  while (k <= n ) do
    if (Major[k] = AnE) then
       Print Student-ID[k], Name[k], Major[k], Tel-Num[k];
    endif;
    k <-- k + 1;
  endwhile
  Print "==================================";
end;
Complexity: Θ(n) -- linear in n.

Note: This is an example of a simply query processing that take a linear time, Θ(n).
These types of operations are commonly done in Database Query.


T5-Q2: (10 points) [Quiz Question from the Past -- Hamming Distance] -- SOLUTION SKETCH
Algorithm Hamming-D(S, R, m); (* Hamming distance of S and R *)  
(* S[1..m], R[1..m] are arrays of size m *)
begin
  count <-- 0;
  k <-- 1;
  while (k <= n ) do
    if (S[k] not equal R[k]) then
       count <-- count + 1;
    endif;
    k <-- k + 1;
  endwhile
  Hamming-Distance <-- count;
  return Hamming-Distance
end;
Complexity: Θ(m) -- linear in m (size of the array).

T5-D3: (Analysis of Binary Search) -- SOLUTION SKETCH
(a) The search tree for binary search algorithm on a SORTED list with 11 names.

(b) Average (successful) = (1 + 2 + 2 + 3 + 3 + 3 + 3 + 4 + 4 + 4 + 4) / 11 = 33/11 = 3.0
(c) Average (unsuccessful) = (3 + 3 + 3 + 3 + 4 + 4 + 4 + 4 + 4 + 4 + 4 + 4)/12 = 44/12 = 3.67

Note: For n=1,000,000, the average successful search time is no more than 20 (between 19 and 20),
and the average unsuccessful search time is also no more than 21 (between 20 and 21).


T5-D4: (Analysis of Sequential Search) -- SOLUTION SKETCH
(a) The search tree for sequential search algorithm.

(b) Average (successful) = (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11) / 11 = 66/11 = 6
(c) Average (unsuccessful) = 11 (always 11, so average is also 11)

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


T5-Q3: (10 points) (Analysis of Binary Search)
(b) 2.9 = 29/10     (c) 3.6363 = 40/11       [Similar to T5-D3]


T5-Q4: (10 points) (Analysis of Sequential Search)
(b) 5.5 = 55/10     (c) 10       [Similar to T5-D4]


T5-Q5: (15 points) [Time Complexity and How Fast They Grows]
(See this page for the table.)

UIT2201: CS & IT Revolution; (Spring 2013); A/P Leong HW