(D-Problems discussed on Friday, 26-Aug-2016)
(Q-Problems due on Tuesday, 30-Aug-2016, 5pm)
Practice Problems: (not graded) PP-problems are self-help type problems. They 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 meet instructor for help during consultation hours.)
T3-PP1: [Algorithms, Pseudo-code, Scratch] (Modified PP1, p45 (Ch.2) of [SG3])
(a) Give an algorithm (in pseudo-code) that gets three data values x, y, and z,
as input and outputs the average of those three values.
(b) Write a simple Scratch program that implements this algorithm. (Do the same for PP2, PP3.)
T3-PP2: [Algorithms, Pseudo-code, Scratch] (Modified PP2, p45 (Ch.2) of [SG3])
(a) Give an algorithm (in pseudo-code) 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.
T3-PP3: [Algorithms, Pseudo-code, Scratch] (Modified PP3, p45 (Ch.2) of [SG3])
(a) Give an algorithm (in pseudo-code) 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.
T3-PP4: [Exercising the Array-Sum Algorithms]
Simulate the algorithm Array-Sum on the array
B[1..6] = [20, -2, 14, 0, -36, 10], n=6. (This is what
happens when a program "calls" the primitive Array-Sum (B, 6).)
Discussion Problems: -- Prepare (individually)
for tutorial discussion.
T3-D0: [Read Algorithm Array-Sum] Read Lecture Notes 3a-alg, 3b-alg, 3c-alg for the algorithm Array-Sum, and the accompanying algorithm-animation and Scratch program(s).
T3-D1: [Array-Sum]
(First read and understand the algorithm Array-Sum
for lecture notes. (See T3-D0)).
(a) Will algorithm Array-Sum work if some of the items in 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 to make it sum ONLY the odd numbers in the array A.
(d) Make small changes to the algorithm to make it count the number of zeroes in the array A.
T3-D2: [Sum-of-Squares]
Make small changes to the algorithm Array-Sum to make it compute the "sum of squares";
namely, the algorithm will add up the square of each number in the given array.
For example, given the array B in T3-PP4, your algorithm will compute
(20)2 + (-2)2 + (14)2 + (0)2 + (-36)2 + (10)2.
T3-D3: [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-D4: (10 points) [Exponentiation-by-Repeated-Multiply]
Modified from Prob 9, p.34 of [SG3].
Problem: Given any two positive numbers a and b,
compute the exponentiation (ab ).
Algorithm: One method (algorithm) is exponentiation is by repeated multiplication.
Example: 57 = 5 * 5 * 5 * 5 * 5.
(a) Write the algorithm exponentiation is by repeated multiplication in pseudo-code
(similar to that used in algorithms Sum-1-to-100 and Array-Sum (of Lecture 2&3).
Namely, given any two positive numbers a and b,
your algorithm will compute the answer, ab.
(b) Write a Scratch program (call it T3-D4-YourName.sb) that implements your algorithm.
(c) After writing your Scratch program, you should test it out
by "running" your program many times with different values of a and b.
Try to think up values that might "break" your algorithm/program, namely make your program "bomb".
Software developers call this process Software Testing with the
aim of catching bugs in the program.
Give a table of k (k > 5) values of | a | b | (ab) || Answer |. (Answer is value computed by program).
Problems to be Handed in for Grading by the Deadline:
(Note: Please submit hard copy to me at COM1-03-17 DropBox.
Not just soft copy via email.)
T3-Q1: (10 points) [Multiplt-by-Repeated-Addition]
Modified from Prob. 9 on p.34 of [SG3].
Problem: Given any two positive numbers a and b, compute the product (a x b).
Algorithm: One method (algorithm) is multiplication by repeated addition.
Example: 5 x 43 = 43 + 43 + 43 + 43 + 43.
(a) Write the algorithm multiplication by repeated addition in pseudo-code.
Namely, given any two positive numbers a and b,
your algorithm will compute the product (a x b).
(b) Write a Scratch program (call it T3-Q1-YourName.sb) that implements your algorithm.
(c) After writing your Scratch program, you should test it out
by "running" your program many times with different values of a and b.
Try to think up values that might "break" your algorithm/program, namely make your program "bomb".
Software developers call this process Software Testing with the
aim of catching bugs in the program.
Give a table of k (k > 5) values of | a | b | (a x b) || P |. (Here, P is value computed by program).
T3-Q2: (10 points) [Getting the Grade]
Problem: We are given a integer (between 0 and 100) called mark
that represents what a student gets for UIT2201 MidTerm. We want to compute the grade,
and outputs both the mark and the grade.
[Assume, for simplicity only,
that the letter grades are A, B, C, D, and that the
cutoffs for are 80, 60, 40.
Namely, A is 80-100, B is 60-79, C is 40-59, and D is 0-39.]
Algorithms: There are two slightly different algorithms for doing this:
(i) using 4 separate (independent) if-statements (if-blocks in Scratch), and
(ii) using nested if-statements (in Scratch, if-blocks nested inside other if-blocks).
(a) Write a Scratch program (T3-Q2a-YourName.sb) that implements algorithm (i).
(b) Write a Scratch program (T3-Q2b-YourName.sb) that implements algorithm (ii).
(c) Which algorithm do you consider to be more efficient? Give a short reason. (Keep it short!)
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 non intersecting spiral path.
To track the cat's motion, turn "on" the pen (with the "Pen Down" command block) --
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 some real-life examples
of "algorithms" (and how they are expressed in English and in other forms):
recipe, origami, dog obedience training.
(a) Find a different interesting example of "algorithms" in real-life.
(b) For your example, briefly state the basic "primitive operations", and give sample algorithm(s),
(c) Comment on the existence (or not) of multiples levels of abstraction.
(You do not need to be exhaustive in your description --
just sufficient to illustrate the point.)
A4: [Fibonacci Spiral]
Look up the definition of a Fibonacci numbers and 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.)
