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

(D-Problems discussed on Thursday, 24-Jan-2008)
(Q-Problems due on Tuesday, 29-Jan-2008)

Practice Problems: (not graded)

For the benefit of those who are completely new to Computer Science (and to algorithms, in particular), 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 see your classmates or the instructor for help.)

T2-PP1: Problems 4,6 on page 34 (Chapter 1) of [SG3].
T2-PP2: Practice Problems 1,2 on page 45 (Chapter 2) of [SG3].
T2-PP3: Practice Problem 2,3 on page 66 (Chapter 2) of [SG3].

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

T2-D1: (Exercising an Algorithm)
For this problem, please first read the addition algorithm (C=A+B) for adding two m-digit number in the lecture notes (see Figure 1.2 (page 7 & 8 of [SG3]) for more details). Trace through the execution of the "addition algorithm" in the lecture notes using the following input values:
    m=4,
    a3 = 3,     a2 = 5,     a1 = 2,     a0 = 8,
    b3 = 8,     b2 = 0,     b1 = 8,     b0 = 9,
Show the "state of the algorithm" after Step 5 (of each iteration) and the output obtained in Step 8.
(Note: To represent the "state of the algorithm" show the value for i, x, carry, c4, c3, c2, c1, c0. (See an example of this in the lecture notes.))

T2-D2: [All kinds of algorithms]
(First, read Chapter 1 (or at least Section 1.3) of the textbook [SG3].)
In Chapter 1 of [SG3] and lectures, we have seen some examples of "algorithms in everyday life":
      (a) programming a VCR,
      (b) shampooing your hair,
      (c) making a chocolate mousse.
For this exercise, please look for other examples of "algorithms in everyday life" (not from computing). For each example, please (i) photocopy the algorithm, (ii) "execute the algorithm" (or imagine yourself doing so), and (iii) discuss whether or not it qualifies as an algorithm, as defined by Section 1.3 of [SG3].
(What is the set of "primitives operations" for your chosen "algorithm" example.)

T2-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 (not 1). How many steps will you take? [Do this for n = 8, 9, 15, 16, 17, 32, 33, 64, 103, 1,024, 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 = 8, 9, 15, 16, 17, 32, 33, 64, 103, 1,024, 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]?

T2-D4: [Finding the Tallest Woman in the World]
Think of some of the issues involved when giving a precise algorithm for this problem.

Problems to be Handed In by the Deadline:

(Note: Please submit hard copy to me. Not just soft copy via email.)

T2-Q1: (5 points) [modified on 22-01-2008)]
Similar to T2-D2 (above), but using the following input values:
    m=5,
    a4 = 9,     a3 = 7,     a2 = 8,     a1 = 1,     a0 = 4,
    b4 = 1,     b3 = 8,     b2 = 8,     b1 = 3,     b0 = 6,
Show the "state of the algorithm" after Step 5 (of each iteration) and the output obtained in Step 8.

T2-Q2: (Algorithm Odd-Sum)
In the lecture notes, algorithm Sum-1-to-100 finds the sum of all the integers from 1 to 100, namely, 1 + 2 + 3 + ... + 100. Modify this algorithm very slightly to get Algorithm Odd-Sum-1-to-101 that finds the sum of all the odd numbers from 1 to 101, namely, 1 + 3 + 5 + ... + 101.
(Note: Please make only small changes to the original algorithm.)

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 attempt them if you are interested and turn in your attempts.

A1: (Optional -- for those who are interested only)
Actually, this would normally not be an A-problem, but we'll start A-problems gently.
Can you think out of the box (like Gauss) did and find a formula for the Odd-Sum-1-to-101 in T2-Q2.
(Actually, there are more than one ways to do it. Try to find as many as you can.)

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