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

(D-Problems discussed on Wednesday, 30-Jan-2013)
(Q-Problems due on Friday, 01-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.)

T3-PP1: [Very Simple Algorithms in Pseudo-code and Scratch]
(a) Practice Problems 1-3 on page 45 (Chapter 2) of [SG3].
(b)Then, write a simple Scratch program for each problem.

Note: Since many of you don't have the textbook yet, I am typing them out for you (this once).

  1. An algorithm that gets three data values x, y, and z as input and outputs the average of those three values.
  2. An algorithm that gets the radius r of a circle as input. Its output is both the circumference and the area of a circle of radius r.
  3. An algorithm that gets the amount of electricity used (in kilowatt-hours) and the cost of electricity per kilowatt-hour as input. Its output is the total amount of the electric bill, including a 7% GST.

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

T3-D0: [Read Algorithm Array-Sum] Read Lecture Notes 3b-Alg for the algorithm Array-Sum, and the accompanying algorithm-animation and Scratch program.

T3-D1: [Array-Sum]
(First read and understand the algorithm Array-Sum for lecture notes. (See T3-D0)).
(a) Will the algorithm Array-Sum work if some of the numbers in the array A are positive and some are negative?
(b) Will the algorithm Array-Sum work if n is negative?
(c) Make small changes to the algorithm in order to make the algorithm sum up ONLY the odd numbers in the array A.
(d) Make small changes to the algorithm in order to make the algorithm count the number of negative numbers in the array A.
(e) Make small changes to the algorithm in order to make the algorithm compute the "sum of squares". (Namely, add up the square of each number in the array A.)

T3-D2: [Finding the Tallest Woman in the World]
Think of some of the issues involved when giving a precise algorithm for this problem.
Your algorithm should give a precise result -- namely, the tallest woman in the world as of a particular day, for example.

T3-D3: [Multiplication-by-Repeated-Addition] Problem 9 on page 34 of [SG3].
(a) 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 any two positive numbers a and b using this technique.
(b) Then, write a simple Scratch program that implements your algorithm.

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

Remember: Name your Scratch program YourNickName-T3-Qx.sb, as appropriate.
(Note: Remember the remark above about minimum requirements. Do enhance your Scratch program with creativity and imagination!.)

T3-Q1: (10 points) [Exponentiation-by-Repeated-Multiplication]
(a) One way to do exponentiation is by repeated multiplication. For example, 85 = 8 * 8 * 8 * 8 * 8.
Write a simple Scratch program that reads in two positive numbers a and b and computes ab using this technique.
(b) Now, give the pseudo-code for your algorithm for computing ab, for two positive numbers a and b using this technique.

T3-Q2: (10 points) [Getting the Grade]
(a) Write a Scratch program that will read in a mark (an integer) that a student gets for UIT2201, and outputs both the mark and the grade.
Assume, for simplicity only, that the letter grades are A, B, C, D, F and that the cutoffs for are 80, 70, 60, 50. Namely, A is 80-100, B is 70-79, C is 60-69, D is 50-59 and F is 0-49.
(b) Now, extend your Scratch program to process a list of marks entered by the user, instead of just one mark. The user will enter a "-1" to indicate that there are no more marks left.

T3-Q3: (10 points) [Cat going in a spiral]
Write a Scratch program that will make the cat go around in an approximate spiral. The cat starts in the middle, the make a series of moves, tracing out a spiral path. To track its motion, turn on the pen (with a "Pen Down" command) -- it will draw the path taken by the cat so that we can see the spiral it made. (Use "Pen Up" to stop drawing.)
(Note: Think hard about what the cat should do in each move -- it has to turn a little bit, and its distance has to increase each time.)

T3-Q4: (10 points) [Other algorithmic frameworks]
In the lectures, we covered different real-life example of communicating different forms of "algorithms" to others: recipe, origami, dog obedience training.
Find another similar real-life example -- and for your example briefly state the framework, the basic primitives, or some sample algorithms, and the role of abstraction.
You do not need to be exhaustive in your description -- just sufficient to illustrate the point.

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.

A3: [Fibonacci Spiral]
Look up the definition of a Fibonacci spiral. Then, using the "pen down/up" feature of Scratch, write a Scratch program that draws a Fibonacci spiral.
(Click here to see a Fibonacci spiral.)

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