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

T5-D1: (Linear Time Complexity) -- DIY.
They are all Θ(n). (Where are the dominant operations?)

T5-D2: -- DIY. This is Θ(m).
Dominant Operation: (comparing pair of elements R[k] and S[k]) total of m times.

T5-D3: [Sequential Search vs Binary Search] -- DIY to fill up the table.

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

T5-Q1: (10 points) [Tracing the Pattern-Matching Algorithm]
(a) n=35, m=4
(b) The output of the algorithm:
      There is a match at position 1
      There is a match at position 9
      There is a match at position 17
      There is a match at position 24
      There is a match at position 32
(c) The Match (S, k, P, m) is called 32 times. (n+1-m) = (35+1-4)

T5-Q2: (5 points) [Query Processing with Multiple Lists] -- SOLUTION SKETCH 
Algorithm My-Query(Student-ID, Tel-No, Major, n);  
begin
  Print " Name                Tel-No  ";
  Print "=====================================";
  for k<--1 to n do
    if (Major[k] = "CSITR-Go") then
       Print  Name[k], Tel-No[k];
    endif;
  endfor
  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-Q3: (10 points) [Algorithmic Problem Solving. Modified from 2013 Mid-Term]

IMPORTANT NOTE:

1. Whenever you are asked to give an algorithm for a new problem, first give a description of your the key ideas of your method/algorithm. Describe the key steps, illustrating with relevant examples, where appropriate.

2. Why giving algorithms, you can freely quote algorithms that we have already given in the course (lectures, tutorials, textbook). There is no need to rewrite the algorithm. If you need to make small modifications of the algorithm, you can just describe the changes made.


(a) (5 points) Maximum Sum pair
Fact: The maximum sum occurs when we have largest and second-largest.

Idea behind the algorithm;
1. Find largest of P[1..n]; swap it to the end (with P[n]);
2. Find largest of P[1..(n-1)]; swap it to the end (with P[n-1]);
3. Return (P[n] + P[n-1]) 

Algorithm Find-Max-Pair(P, n);  
begin
  loc <- Find-Max (P, n);    swap (A[loc], P[n]);
  loc <- Find-Max (P, n-1);  swap (A[loc], P[n-1]);
  return ( P[n] + P[n-1] );
end;
Time complexity: Θ(n), (Step 1, 2 is Θ(n) each, step 3 is Θ(1). So total is Θ(n).

(b) (5 points) There are many different ways/algorithms to do this:

Algo 1: (Try All pairs) Try all different pairs A[j], A[k] (j not equal to k). 

Idea behind the algorithm;  Have two nested loops; 
    S1: Outer-loop controlled by j, for j=1,2,3,...,n
    S2:   Inner-loop controlled by k, for k=j+1,j+2,j+3,...,n
    S3:     Check if (P[j] + P[k]) = TS) in inner loop!    

Algorithm TryAllPairs-Target-Pair(P, n, TS):
begin
  j <-- 1; 
  while (j <= n) do 
    k <-- j+1;   (* initialize k here for each new value of j *)
    while (k <= n) do
      if (P[j] + P[k] = TS) then {return P[j], P[k]; Stop} endif;
      k <-- k+1;
    endwhile
    j <-- j+1; 
  endwhile
end;
Time complexity: Θ(n2)

Algo 2: (Search partner)
We rewrite (P[j] + P[k] = TS) as (P[k] = TS - P[j]).
Then, if we want to use P[j], then must find its partner (TS - P[j]) in the array P[1..n]. 

Idea behind the algorithm;  
 S1:  Have a loop for j, with j=1,2,3,...,n; 
 S2:    Find (TS - P[j]) in the array P[1..n]; 

Algorithm SearchPartner-Target-Pair(P, n, TS):
  j <-- 1; 
  while (j <= n) do 
    Diff = TS - P[j];
    Loc <-- Seq-Search (P, n, Diff)  (* Find partner in P[1..n] *)
    if (Loc not-equal-to -1)         (* -1 means "not found")
      then return A[j], A[Loc]; Stop 
    endif;
    j <-- j+1; 
  endwhile
end;
Time complexity: Θ(n2), We call Seq-Search primitive n times, each time it takes Θ(n),

Algo 3: (Faster search partner):
Sort the array P[1..n] first! Then can use FAST Binary-Search; 

Idea behind the algorithm;  
 A:  Sort array P[1..n]  (* use the fastest available *) 
 B:  Run Algo 2, but but replace Sequential-Search by Binary-Search;
For A, use MergeSort(P,n) that runs in time Θ(n lg n);
For B, we now call Binary-Search n times; each takes Θ(lg n); total is Θ(nlg n)
Time Complexity: A + B = Θ(n lg n) + Θ(n lg n) = Θ(n lg n).

Algo 4: (Fast sort, then use creative algorithm): [Don't worry if you don't fully understand.]
First use MergeSort to sort the array P[1..n]. (this takes Θ(n lg n).)
Once P[1..n] is sorted, we can get creative! 

Idea behind the creative algorithm:  
 Start with two pointers at two ends of array -- left=1, right=n;
 And we alway track the sum (P[left] + P[right]);
  if you increase left pointer,  the sum (P[left] + P[right]) increases;
  if you decrease right pointer, the sum (P[left] + P[right]) decreases;

Algorithm TwoPointers-Target-Pair(P, n, TS):
  left <-- 1;   right <-- n; 
  while (left < right) do 
    if  (P[left] + P[right] = TS) then return P[left], P[right], STOP
    else if (P[left] + P[right] > TS) then right <-- right-1 (*decrease the sum *)
    else if (P[left] + P[right] < TS) then left  <-- left+1  (*increase the sum *)
  endwhile
end;
Time complexity: Θ(n),

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

UIT2201: CS & IT Revolution; (Fall 2016); LeongHW