---

UIT2201: CS & the IT Revolution
Tutorial Set 3 (Spring 2008)

(D-Problems discussed on Thursday, 31-Jan-2008)
(Q-Problems due on Tuesday, 05-Feb-2008)

---

T3-PP1: Probs 16, 17 on p76 (Ch2) of [SG].

T3-PP2: Probs 5, 11 on page 121 (Ch3) of [SG].

T3-PP3: Perform the selection sort algorithm on the following problem instances. Show the list are each iteration of the algorithm.

1. n=9, A = [ 3, 2, 5, 6, 1, 4, 9, 8, 7 ]
2. n=9, A = [ 8, 6, 4, 2, 9, 7, 5, 3, 1 ]
3. n=9, A = [ 1, 2, 3, 4, 5, 6, 7, 9, 8 ]

T3-D1: (Simple Cyclic Shift Algorithm)
In class, we discussed the swap algorithm that performs the exchange:   x <--> y
where the arrows indicate that x is to assume the value of y, and y to assume the value of x.
Now, design an algorithm that makes the following exchanges:   a --> b --> c -->(back to a)
where the arrows indicate that b is to assume the value of a, c to assume the value of b, and c to assume the value of a. Namely, perform a "cyclic" shift of a, b, and c.

T3-D2: (Printing out tables)
Using iterative (while) operations, write pseudocode for an algorithm that prints out the following:

(a)
  1  2  3  4  5  6  7
  1  2  3  4  5  6  7
  1  2  3  4  5  6  7
  1  2  3  4  5  6  7
  1  2  3  4  5  6  7
  1  2  3  4  5  6  7
  1  2  3  4  5  6  7

(b)
  1
  1  2
  1  2  3
  1  2  3  4
  1  2  3  4  5
  1  2  3  4  5  6
  1  2  3  4  5  6  7

T3-D3: (Exponentiation-by-Repeated-Multiplication)
One way to do exponentiation is by repeated multiplication. For example, 8⁵ = 8 * 8 * 8 * 8 * 8. Give the pseudo-code for this algorithm for computing a^b, for two positive numbers a and b using this technique.

T3-D4: (Reversing an Array)
Design an algorithm that will reverse the elements in an array A[1..n] = (A[1], A[2], A[3], ... , A[n]).
Namely, your algorithm will transform [1 2 3 4 5 6 7 8] --> [8 7 6 5 4 3 2 1].
[Hint: Make systematic use of the "swap" operation.]

T3-D5: (Problem Decomposition) [CountX, MajorityX]
Given a list of n numbers (elements) D₁, D₂, ... , D_n, a number X is called the majority element if X appears more than n/2 times in the list. For example, in the list (2, 3, 7, 2, 2, 4, 2, 2) the element 2 is the majority. The list (2, 3, 7, 4, 2, 3, 7, 3) does not have any majority element.
(a) First, design an algorithm CountX(D,n,X) to count the number of times X appears in the list D.
(b) Now, using CountX(D,n,X) as a high-level primitive, design an algorithm MajorityX(D,n,X) to determine if a given number X is the majority element of the list D.
(c) Give the time complexity of your algorithms CountX and MajorityX (as a function of n).

T3-Q1: (5 points) [Exercising the Find-Max algorithm]
Consider the "Find-Max" algorithm given in the lectures (or the FindLargest algorithm in Figure 2.10, p.63 of [SG]). Run the Find-Max algorithm for each of the following problem instances and for each, print out all the different values of the variable Max-sf during the execution of the algorithm. (Print only when the value of Max-sf changes.)

1. n=9, A = [ 4, 3, 1, 5, 6, 8, 2, 9, 7 ]
2. n=9, A = [ 7, 6, 8, 2, 4, 9, 5, 3, 1 ]
3. n=9, A = [ 1, 1, 2, 3, 3, 4, 4, 5, 5 ]
4. n=9, A = [ 8, 1, 2, 3, 4, 5, 6, 7, 8 ]
5. n=9, A = [ 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

T3-Q2: (5 points) [Multiplication-by-Repeated-Addition] Problem 9 on page 34 of [SG3].
One way to do multiplication is by repeated addition. For example, 47 x 5 = 47 + 47 + 47 + 47 + 47. Give the pseudo-code for this algorithm for multiplying two positive numbers a and b using this technique.

T3-Q3: (10 points) [Printing a Simple Monthly Calendar]
Write an algorithm that will print out a simple monthly calendar for June 2008 shown below.

   June 2008
 S  M Tu  W Th  F  S
 1  2  3  4  5  6  7
 8  9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30

T3-Q4: (10 points) [Algorithm for Minima]
Write an algorithm that finds the minimum (smallest) of n given numbers (all greater than 0).
Assume that the numbers are denoted by X₁, X₂, ... , X_n.
(Hint: Please first read Section 2.3.2 and the Find-Max algorithm.]

A2: (Long Subtraction [Challenge Problem 1 of Ch.1 in [SG3]])
Assume we have a "computing agent" that knows how to do one-digit subtraction where the first digit is at least as large as the second (i.e. we do not end up with a negative number). Thus, our computing agent can do such operations as 7−3=4, 9−1=8, and 5−5=0. It can also subtract a one-digit value from a two-digit value in the range 10−18 as long as the final result has only a single digit. This capability enables it to do such operations as 13−7=6, 10−2=8, and 18−9=9.
Using these primitive capabilities, design an algorithm to do decimal subtrraction of two m-digit numbers where m > 0. You will be given two positive who numbers A = (a_m-1 a_m-2 ... a₁ a₀) and B = (b_m-1 b_m-2 ... b₁ b₀), where A > B. Your algorithm must compute the value C = (c_m c_m-1 ... c₁ c₀), where C = A − B.
[See the text [SG3] for a more detailed description and some hints.]

A3: (Optional -- for those who are interested only)
Consider the Find-Max algorithm covered in class and also used in T3-Q1. Given a random permutation of {1,2,3,...,n}, determine how many times (on average) the variable Max-sf is updated.
[Notes:
1. You need some probability theory to do this, but only elementary prob. theory is needed,
2. You can also assume that all n! permutations of {1,2,...,n} are equally likely, and
3. The answer is *not* n/2.]