UIT2201: CS & the IT Revolution
Tutorial Set 4 (Spring 2013)

(D-Problems discussed on Wednesday, 06-Feb-2013)
(Q-Problems due on Friday, 08-Feb-2013)

(IMPORTANT NOTE for all Scratch Programs: What is given in the homework writeup is merely the minimum requirement. You are encouraged to use your creativity and imagination to make your Scratch program do MORE than the minimum requirement and, more importantly, to make it FUN.)

Practice Problems: (not graded)
I have included a number of practice problems for you to try out. These problems will help you to "ease into" the materials covered in the course. (If you have difficulties with these practice problems, please quickly see your classmates or the instructor for help.)

T4-PP1: Problems 2,3 on page 66 (Chapter 2) of [SG3].

T4-PP2: Probs 16, 17 on p76 (Ch2) of [SG].
(Read Chapter 2.3.1--2.3.3 first.)

Discussion Problems: -- Prepare (individually) for tutorial discussion.

T4-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 <== d <== a
where the <== arrows indicate that a is to assume the old value of b, b to assume the old value of c, c to assume the old value of d, and d to assume the old value of a. Namely, perform a "cyclic" left-shift of a, b, c, and d.

T4-D2: (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 [3 5 1 4 8 7 2 6] --> [6 2 7 8 4 1 5 3].
[Hint: Make systematic use of the "swap" operation.]

T4-D3: (Two Important Processes in CS)
(a) [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? [Do this for n = 1, 2, 3, 4, 5, 7, 8, 9, 15, 16, 17, 31, 32, 33, 103, 1023, 1024, 1025, 106, 109.]
(b) [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? [Do this for n = 1, 2, 3, 4, 5, 7, 8, 9, 15, 16, 17, 31, 32, 33, 103, 1023, 1024, 1025, 106, 109.]
(c) Express the processes described in (a) and (b) as algorithms given in pseudo-code.
(d) Do you see any relationship between process (a) and (b) [for the same n]?

T4-D4: (Tennis Tournaments and Finding Maxima)
The Australian tennis tournament is over not too long ago (who won?). The tournament is a knock-out tournament in which pairs of players play against each other (in rounds). The winner continues to the next round, while the loser is "knocked out". This continues until the final in which the last two remaining players plays to decide the final winner.
(a) Explain how this process be used to find the maximum of n numbers in the list (for say, n=8, 16, 32)? If so, how? and how many matches are needed?
(b) Can this process be used to find the maximum of n numbers where n is 11 or 23 (in general, n is NOT a power of 2).
(c) Can you think of some advantages of this algorithm, compared to the Find-Max algorithm given in class.

Problems to be Handed in for Grading by the Deadline:
(Note: Please submit hard copy to me. Not just soft copy via email.)

T4-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=8, A = [ 4, 1, 5, 2, 6, 7, 3, 8 ]
  2. n=8, A = [ 6, 3, 7, 2, 4, 8, 5, 1 ]
  3. n=8, A = [ 1, 2, 2, 2, 3, 3, 4, 5 ]
  4. n=8, A = [ 8, 1, 2, 3, 4, 5, 6, 7 ]
  5. n=8, A = [ 1, 2, 3, 4, 6, 7, 8, 9 ]

T4-Q2: (5 points) [Algorithm for Counting]
Design an algorithm Count-List(D, n, X) to count the number of times that the number X appears in a list of numbers stored in a list D[1..n] of n numbers. (Note: D is an array (or list) with n numbers.) For example, if D = (2, 3, 7, 3, 2, 3, 8, 3) and X=3, then X appears 4 times.
(Note: You can modify the algoritm Array-Sum given in class.)

T4-Q3: (10 points) [Algorithm for Minima]
(a) Write an algorithm that finds the minimum (smallest) of n given numbers.
Assume that the numbers are denoted by X1, X2, ... , Xn.
(Hint: Please first read Section 2.3.2 and the Find-Max algorithm in lecture notes.)
(b) Will your algorithm work correctly when there is only 1 number (namely, n=1)?
(c) What about when n=0? What happens?

T4-Q4: (10 points) [Algorithm for Smallest and 2nd Smallest]
(a) Write a Scratch program that find the Smallest and the Second Smallest in a list of n numbers, A[1..n].
(Note: It may happen that Second Smallest is equal to the Smallest; that is OK.)
(b) Give the pseudo-code of your algorithm for (a).
(c) How many item-comparisons are made by your algorithm? (written in terms of n)

A-Problems: OPTIONAL Challenging Problems for Further Exploration
A-problems are usually advanced problems for students who like a challenge; they are optional. There is no deadline for A-problems -- you can try them if you are interested and turn in your attempts.

A4: (Optional -- for those who are interested only)
Consider the Find-Max algorithm covered in class and also used in T4-Q1. Given a random permutation of {1,2,3,...,n}, determine how many times (on average) the variable Max-sf is updated.

    Some notes for those who like to try this:
  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.

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