---

UIT2201: Tutorial Set 4 (Spring 2013)
(Solution Sketch to Selected Problems)
** NOT TO BE GIVEN TO FUTURE UIT2201 STUDENTS **

---

T4-PP1: Problem 2 on page 66 (Ch.2) of [SG]. -- SOLUTION SKETCH
When n=0 (empty list), Algorithm 2.10 will fail in Step 3, when it tries to set the value of "largest so far" to A₁. Note that when n=0, A₁ is undefined (has no value). To fix this problem, insert an if-statement between Steps 2 and 3 as follows:

     if (n=0) then stop
     else 
       Step 3. ....  

T4-PP1: Problem 3 on page 66 (Ch.2) of [SG]. -- DIY

T4-PP2(a): Probs 16 on p76 (Ch2) of [SG]. --- 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-PP2(b): Probs 17 on p76 (Ch2) of [SG]. --- SOLUTION SKETCH
(a) The algorithm would still find the largest element in the list, but if the largest were not unique then the algorithm would find the last occurrence of the largest element in the list.
(b) The algorithm would find the smallest element in the list.
Note: The relational operators in the condition are very important, and care must be taken to choose the correct one, since changing them can drastically change the output of the algorithm.

Using a temp variable;  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.)

As discussed in class, 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, e.
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 that is a bit of a brain twister (esp. the version on the left). To help explain it, I added in an equivalent, but simpler version on the right:

Without temp variable;  a <-- (a+b+c+d); d <-- a - b - c - d; c <-- a - b - c - d; b <-- a - b - c - d; a <-- a - b - c - d;

With temp variable;  x <-- (a+b+c+d); // x is sum of all d <-- x - b - c - d; // d now holds value of "old a" c <-- x - b - c - d; // c now holds value of "old d" b <-- x - b - c - d; // b now holds value of "old c" a <-- x - b - c - d; // a now holds value of "old b"

Note: You can replace "x" with "a" to get back the original algorithm.
DO NOT WORRY IF YOU DON'T GET THIS BRAIN TWISTER SOLUTION.

Question: Can you now try a cyclic shift of n elements:
a[1] <-- a[2] <-- a[3] <-- ... <-- a[n-1] <-- a[n] <-- a[1] (back to a[1])?

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; 

  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; 

(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?
(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?

RH and RD n RH (#steps) RD (#steps) 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

RH and RD n RH (#steps) RD (#steps) 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

RH and RD n RH (#steps) RD (#steps) 1,000 10 10 106 20 20 109 30 30

(d) From the table above, it is easy to see that, very roughly, both RH and RD takes (lg₂n) steps. [Here, all logarithms are logarithms-to-the-base-2.]
When n is not a power of 2, then #steps for both RH and RD are the same -- namely is (lg n). If n=2^k, then the number of steps differs by ONLY 1; (i) for Repeated-Doubling, #steps is k (or lg n), while (ii) for Repeated-Halving, #steps is k+1 (or (lg n)+1).
(Note the #steps when n=1000, n=10⁶, and n=10⁹ given in third table!)

Algorithm Count-List(D, n, X);   (* Counts the #times X appears in array D[1..n] *) begin Count <-- 0; k <-- 1; while (k <= n) do if D[k] = X then Count <-- Count + 1 endif k <-- k + 1; endwhile return Count end;

Complexity: O(n) -- linear in n.

Algorithm Find-Min(X,n); 
(* Assumes given list is stored in X[1..n] *) 
1. begin
2.   MinSoFar <-- X[1];
3.   Location <-- 1; k <-- 2;
5.   while (k <= n) do
6.     if (X[k] < MinSoFar) then
7.       MinSoFar <-- X[k];
8.       Location <-- k;
9.     endif
10.    k <-- k + 1;
11.  endwhile
12.  return MinSoFar, Location
13.end.

(a) Here, we can make effective use of the high-level primitive defined in T4-Q3 Find-Min(X,n). Instead of giving the whole algorithm, I will discuss the ideas behind several different methods.

One idea is to first find the smallest, then "eliminate" it from consideration.
But, how to "algorithmically" "eliminate" the smallest from consideration?

• Method 1: When finding the smallest, remember its location (like in the algorithm Find-Min given above). Then, set A[location] to be "infinity" or a very, very big number (so it cannot possibly be the new smallest).
• Method 2: Swap A[location] with A[n]. Then 2nd-smallest is smallest in A[1], A[2],..., A[n-1]! We can then use Find-Min(A,n-1) to find it.

Another idea is to find smallest and 2nd-smallest simultaneously. (Most of you did this!)
Be careful how you initialize Min-sf and Min2-sf.
Also, think about how you update them: (2 comparisons for each element)

• If Min-sf=4 and Min2-sf=6 and a new number 3 arrives, then you want to make Min-sf=3 and Min2-sf=4.
• If Min-sf=4 and Max2-sf=6 and a new number 5 arrives, then you want to make Min-sf=4 and Min2-sf=5.