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

Remember, when designing algorithms, to first work out a process of what you have to do (then execute it yourself) and fine tune the process. Then, only work on giving the algorithm in pseudo-code or in Scratch.)

When giving ALGORITHMS, DO NOT just give MESSY/COMPLICATED PSEUDO-CODE.
First describe the main ideas behind your algorithm, describe the main steps and illustrate with simple example if possible.
Think of the poor instructor who has to decode your messy algorithm and TRY to THINK LIKE YOU.
(It is very hard to read and decode algorithms from just MESSY PSEUDO-CODE.)

T4-PP1: Probs 1 on page 75 (Ch2.3.3) of [SG6]. (not found in [SG3])
What part(s) of the sequential search algorithm of Figure 2.13 would need to be changed if our phone book contained 1 million names rather than 10,000?

SOLUTION SKETCH:
In the algorithm in Figure 2.13 [SG6], change line 1 (to read in 1000000 names and tel-no, instead of 10000) and most importantly, the loop in line 3, change from "(i <= 10000)" to "(i <= 1000000)".
A better way is to define a variable, let's say N, that represent the size of the list. Then, if there are 1000000 names, we just set N <-- 1000000 and in line 3 (of the loop), change from "(i <= 10000)" to "(i <= N)"

This is much easier for the algorithm Seq-Search given in lecture notes. We have included the the number of entries as an input parameter m in the high-level primitive Seq-Search (N, T, m, Name). So, if there are 1000000 names, we just set m <-- 1000000 before call primitive Seq-Search.
INDEED, this is one of the key advantages of defining high-level primitives.

T4-PP2: Prob 4 on p.75 (Ch2.3.3) of [SG6]. (was Prob 2 of p.66 of [SG3]) -- SOLUTION SKETCH
Program will "bomb"/"crash" in the line Max-SF <-- A[1]. The program tries to access A[1], which does not exist.
One way to fix it: program should first check if (n>0) and should print error message and exit the program.

T4-PP3: Prob 5 on p.75 (Ch2.3.3) of [SG6]. (was Prob 3 of p.66 of [SG3]) -- SOLUTION SKETCH
Program will run normally, if just skip the loop.

T4-PP5: Prob 16 on p.85 of [SG6] (was p.76 of [SG3]) --- SOLUTION SKETCH
(a) If n ≤ 2, then the test would be true, so the loop would be executed. In fact, the test would never become false. Thus, the algorithm would either loop forever, or generate an error when referring to an invalid A[i] value (when i is very large and it "overshoots" the valid range of the array A).
If n > 2, then the test would be false the first time through, so the loop would be skippped and A[1] would be reported as the "largest value". [Of course, in this case, the algorithm would be wrong since it reports the wrong value most of the time.]
(b) The loop will exit when i=n, and so the algorithm would find the largest of the first n-1 elements. It would not look at the last element (A[n]).
(c) If n=2, the loop would execute once, comparing A[1] and A[2]. Then the loop would exit on the next pass, return the larger of the first two values. For any other value of n, the loop would be skipped, reporting A[1] as the largest value.

T4-D1: (Swapping X and Y) -- SOLUTION SKETCH
(a) Don't work.
In Bad-1, old-value of X is gone forever after step 1. After step 2, both X and Y have value 22.
In Bad-2, old-value of Y is gone forever after step 1. After step 2, both X and Y have value 15.
(b) In special case when X=Y, then it just work (by luck!). But, don't depend on it! 
      Algorithm Swap(X, Y)
       1. Temp <-- X; 
       2. X <-- Y; 
       2. Y <-- Temp;

T4-D2: (Simple Cyclic Left Shift Algorithm) -- SOLUTION SKETCH
Several algorithms can be used for cyclic left shift   A <== B <== C <== D <== A (back to A) 
Using a temp variable T;  
  T <-- A;
  A <-- B;
  B <-- C;
  C <-- D;
  D <-- T;
    
Using swap primitive; 
  swap(A,B);
  swap(B,C);
  swap(C,D);
(Note: This may be a bit confusing. So, try it out.)
It may take a while for you to figure out exactly how it is done. It helps to work out a real example with different numbers for A, B, C and D.

Looking Back at the Solution: The first algorithm is a generalization of the algo for Swap operation, while the second algorithm re-uses the Swap operation. So, you might also say that the first re-uses the method, while the second re-uses the result of the Swap operation.

Optional FUN: For fun, I add one tricky algorithm for the cyclic left shift that is a bit of a brain twister (esp. the version on the left). I gave an equivalent but simpler version on the right: 
Without temp variable; 
  D <-- (A+B+C+D); 
  C <-- D - A - B - C; 
  B <-- D - A - B - C; 
  A <-- D - A - B - C; 
  D <-- D - A - B - C;
    
With temp variable S; 
  S <-- (A+B+C+D);      // S is sum of all
  C <-- S - A - B - C;  // C now holds value of "old D"
  B <-- S - A - B - C;  // B now holds value of "old C"
  A <-- S - A - B - C;  // A now holds value of "old B"
  D <-- S - A - B - C;  // D now holds value of "old A"
Note: You can replace "S" with "D" to get the algorithm on the left.
DO NOT WORRY IF YOU DON'T GET THIS BRAIN TWISTER SOLUTION.

T4-D4: (Two Important Processes in CS) -- SOLUTION SKETCH

(a) [RH: Repeated Halving] Start with a number n. Repeatedly "divide by two (and throw away the remainder)" until we reach 0. How many steps will you take? Call this H(n).
(b) [RD: Repeated Doubling] Start with the number 1. Repeatedly multiply by two until we get a number greater than or equal to n. How many steps will you take? Call this D(n).

n   H(n)     D(n)  
1 1 0
2 2 1
3 2 2
4 3 2
5 .. 7 3 3
8 4 3
9 .. 15 4 4
16 5 4
17 .. 31 5 5
32 6 5
   
n   H(n)     D(n)  
33 .. 63 6 6
64 7 6
65 .. 127 7 7
128 8 7
129 .. 255 8 8
256 9 8
257 .. 511 9 9
512 10 9
513 .. 1023 10 10
1,024 11 10
   
n   H(n)     D(n)  
1,000 10 10
106 20 20
109 30 30

(c) The two processes in algorithm pseudo-code. 
  Algorithm Repeated-Doubling(n):
  1. begin
  3.   k <-- 1;
  2.   Count <--0;
  4.   while (k < n) do
  6.     k <-- k * 2;   (*double it*)
  5.     Count <-- Count + 1;
  7.   EndWhile
  8.   answer <-- Count;
  9. end; 
  Algorithm Repeated-Halving(n):
  1. begin
  3.   k <-- n;
  2.   Count <--0;
  4.   while (k > 0) do
  6.     k <-- k div 2; (*half it*)
  5.     Count <-- Count + 1;
  7.   EndWhile
  8.   answer <-- Count;
  9. end;

(d) The general formula for H(n) and D(n) (for all values of n):
    H(n) = ⌈lg2(n+1)⌉.     D(n) = ⌈lg2(n)⌉.
For all n (except when n is a power of two), H(n) = D(n).
When n is a power of two (1,2,4,8,16,32,...), H(n) = H(n) + 1.
Verify this with either the formula above or the table above.)
Finally, note for for n = 103, 106, 109, we have H(n) = D(n) = 10, 20, 30, respectively.

(OPTIONAL: If you *really* want to know how to get H(n), D(n), read Appendix-A, else skip it.)

T4-D3: [Computing Hamming Distance] -- SOLUTION SKETCH 
Algorithm Hamming-D(S,R,m); 
(* Assumes strings S[1..m] and R[1..m] are initialized *) 
1. begin
2.   Distance <-- 0;
3.   k <-- 1;
4.   while (k <= m) do
5.     if (S[k] not equal to R[k]) then
6.       Distance <-- Distance + 1;
7.     endif
8.     k <-- k + 1;
9.   endwhile
10.  return Distance
11.end.
Complexity: Θ(m) -- linear in m.

T4-Q1(a): (5 points) --- SOLUTION SKETCH [Updated values shown in bold.]
(1) [ 2, 6, 5, 2, 1, 7, 9, 8 ] (4 times)
(2) [ 5, 1, 4, 2, 7, 3, 8, 6 ] (3 times)
(3) [ 1, 1, 2, 2, 2, 4, 5, 6 ] (5 times)
(4) [ 8, 5, 3, 1, 7, 8, 4, 7 ] (1 time)
(5) [ 1, 2, 3, 5, 6, 7, 8, 9 ] (8 times)

(b): (5 points) [Algorithm for Counting]--- SOLUTION SKETCH 

Algorithm Count-Occ (A, n, Num);  
(* Counts the #times Num appears in array A[1..n] *)
begin
  Count <-- 0;
  k <-- 1;
  while (k <= n) do
    if A[k] = Num then
      Count <-- Count + 1
    endif
    k <-- k + 1;
  endwhile
  return Count
end;
Complexity: Θ(n) -- linear in n.

T4-Q2: (10 points) [Algorithm for Minima]--- SOLUTION SKETCH
(a) We define a high-level-primitive Find-Min(D,n), for finding the minimum in an array D[1..n].
(Note: This is a direct modification of Find-Max(A,n).) 
Algorithm Find-Min(D,n); 
(* Assumes given list is stored in D[1..n] *) 
1. begin
2.   MinSoFar <-- D[1];
3.   Location <-- 1; k <-- 2;
5.   while (k <= n) do
6.     if (D[k] < MinSoFar) then 
7.       MinSoFar <-- D[k];
8.       Location <-- k;
9.     endif
10.    k <-- k + 1;
11.  endwhile
12.  return MinSoFar, Location
13.end.
Complexity: Θ(n) -- linear in n.

(b) Yes, the algorithm will work correctly. When n=1, it correctly report the minimum as A[1]. (Algorithm does not execute the while-loop, since pre-test condition fails.)
(Note: When you call Find-Min(A,1), you want to find the min number in the list A[1..1], which means only one number, namely A[1]. It doesn't matter how many item the array A really have.)

T4-Q3: (Reversing an Array) --- SOLUTION SKETCH
Sample: [1 2 3 4 5 6 7 8] --> [8 7 6 5 4 3 2 1].

We discussed two version here:
In the first version uses two pointers left and right.
The left pointer starts from 1, right pointers starts from n.
So the first swap(A[left], A[right]) will first swap A[1] and A[n].
Then the left pointer moves to the right (left <-- left + 1), while
the right pointer moves moves to the left (right <-- right - 1),
So, in the next iteration, swap(A[left], A[right]) will swap A[2] and A[n-1].

In the second version, we only use a left pointer (called k). since right = (n + 1 - k).
Everything else is the same.
Note that as the left pointer moves right, (n + 1 - k) moves left.

The detailed algorithms are given below: 

Algorithm ReverseArray2Ptrs(A,n);  
begin
  left <-- 1;
  right <-- n;
  while (k <= (n div 2)) do
    swap (A[left], A[right]);
    left  <-- left + 1; 
    right <-- right - 1;
  endwhile
end;
    
Algorithm ReverseArray(A,n);  
begin
  k <-- 1;
  while (k <= (n div 2)) do
    swap (A[k], A[n+1-k]);
    k <-- k + 1;
  endwhile
end;
Complexity: Θ(n) -- linear in n.

Note: In both versions, you only do n/2 swaps. Not n swaps, otherwise you get back the original array!

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