ÿþ<html><head> <meta http-equiv="content-type" content="text/html; charset=ISO-8859-1"> <title>UIT2201 (Spring 2012), NUS</title> </head><body><h3><hr><center> UIT2201: CS &amp; the IT Revolution<br> Tutorial Set 4 (Spring 2012) <p>(D-Problems discussed on Friday, 10-Feb-2012) <br>(Q-Problems due on Monday, 13-Feb-2012) </p></center><hr></h3> <body bgcolor=beige> <! body bgcolor=honeydew> <!-- -----------------------------------------------------------> <!-- The PP-Problems --- practice problems; --> <!-- -----------------------------------------------------------> <p> <font size="+1"><b> Practice Problems: (not graded) </b></font><br> These are practice problems for you to try out. <i>(If you have difficulties with these practice problems, please <b>quickly</b> see your classmates or the instructor for help.)</i> <P> <B>T4-PP1: </b> Problems 2, 3 on page 66 (Chapter 2) of [SG3]. <P> <B>T4-PP2:</b> Problems 16, 17 on p76 (Ch2) of [SG3]. <br>(Read Chapter 2.3.1--2.3.3 first.) <!-- -----------------------------------------------------------> <!-- The D-Problems --- Problems to be discussed --> <!-- -----------------------------------------------------------> </p><p><br> <font size="+1"><b> <hr>Discussion Problems: -- Prepare (individually) for tutorial discussion. </b></font> <P> <b>T4-D1: (Reversing an Array) </b><br> Design an algorithm that will reverse the elements in an array <tt>A[1..<i>n</i>] = (A[1], A[2], A[3], ... , A[<i>n</i>]</tt>). <br>Namely, your algorithm will transform <tt>[1 2 3 4 5 6 7 8] --> [8 7 6 5 4 3 2 1]</tt>. <br>[<b>Hint:</b> Make systematic use of the "swap" primitive.] <P> <!-- Modified from Dave's Pascal book --> <b>T4-D2: (Price Rise) [Average, PriceRise] </b><br> A consumer watchdog group, the USP-CWG, has been alarmed about the recent rapid rise in price of certain grocery item. The group sample grocery store prices of that item on a monthly basis for year 2011 and observed that the price varied from 84 to 110 as shown in the following table: <pre> Month (in year 2011) | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |------|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----| | Price| 87 | 89 | 89 | 91 | 87 | 84 | 88 | 95 | 98 | 100 | 105 | 110 |</pre> Since you are taking UIT2201, you are tasked to develop an algorithm to read in the data and carry out the following analyses, and to print out the results, appropriately formatted. <br>(Hint: Read in the values into a list called <tt>Price</tt> of size 12, in which <tt>Price[k]</tt> represents the price of the item for month <tt>k</tt> of 2011 (k=1,2,...,12]. Use whatever additional variables and lists you need. Remember to give <i>good</i> variable names for them.) <br> <b>(a)</b> Compute the average price for the item for the year 2011. <br> <b>(b)</b> Compute the percentage increase in monthly prices for each month of 2010. <br> &nbsp &nbsp &nbsp; Note: The formula for this is: <br> &nbsp &nbsp &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; percent-increase-for-month-k = 100 * (Price[k] - Price[k-1]) / Price[k-1] <P> <b>T4-D3: (Two Important Processes in CS)</b><br> <b>(a) [Repeated-halving]</b> Start with a number <i>n</i>. Repeatedly "divide by two (and throw away the remainder)" until we reach 0. How many steps will you take? [Do this for <i>n</i> = 1, 2, 3, 4, 5, 7, 8, 9, 10, 15, 16, 17, 31, 32, 33, 10<sup>3</sup>, 1023, 1024, 1025, 10<sup>6</sup>, 10<sup>9</sup>.] <br> <b>(b) [Repeated-doubling]</b> Start with the number 1. Repeatedly multiply by two until we get a number greater than or equal to <i>n</i>. How many steps will you take? [Do this for <i>n</i> = 1, 2, 3, 4, 5, 7, 8, 9, 10, 15, 16, 17, 31, 32, 33, 10<sup>3</sup>, 1023, 1024, 1025, 10<sup>6</sup>, 10<sup>9</sup>.] <br> <b>(c)</b> Express the processes described in <b>(a)</b> and <b>(b)</b> as algorithms given in pseudo-code. <br> <b>(d)</b> Do you see any relationship between process <b>(a)</b> and <b>(b)</b> [for the same <i>n</i>]? <P> <b>T4-D4: (Tennis Tournaments and Finding Maxima)</b><br> The Australian tennis tournament is just over (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. <br> <b>(a)</b> 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? <br> <b>(b)</b> Can this process be used to find the maximum of n numbers where n is 13 or 21 (in general, n is NOT a power of 2). <br> <b>(c)</b> Can you think of some advantages of this algorithm, compared to the <tt>Find-Max</tt> algorithm given in class. <br><br> <!-- -----------------------------------------------------------> <!-- Q-Problems --- to be handed in for graded --> <!-- -----------------------------------------------------------> <p><b><font size="+1"><hr> Problems to be Handed in for Grading by the Deadline: </font></b><br> (<b>Note:</b> Please submit <i>hard copy</i> to me. Not just soft copy via email.) </p> <P> <B>T4-Q1: (5 points) [Exercising the Find-Max algorithm]</b><br> Consider the <tt>Find-Max</tt> algorithm given in the lectures (or the FindLargest algorithm in Figure 2.10, p.63 of [SG]). Run the <tt>Find-Max</tt> algorithm for each of the following <i>problem instances</i> and for each, print out all the different values of the variable <tt>Max-sf</tt> during the execution of the algorithm. (Print only when the value of <tt>Max-sf</tt> <i>changes</i>.) <ol type=a> <li> n=8, A = [ 3, 2, 4, 1, 5, 7, 8, 6 ] <li> n=8, A = [ 6, 3, 1, 2, 8, 5, 7, 4 ] <li> n=8, A = [ 1, 2, 2, 3, 4, 5, 6, 6 ] <li> n=8, A = [ 8, 7, 1, 2, 3, 4, 5, 6 ] <li> n=8, A = [ 1, 2, 4, 5, 6, 7, 8, 9 ] </ol> (See T4-A4 for an interesting <i>advanced problem</i> related to this.) <P> <B>T4-Q2: (10 points) [Algorithm for Smallest and 2nd Smallest] </b> <br><b>(a)</b> Write an algorithm to find the Smallest <i>and</i> the Second Smallest in a list of <i>n</i> numbers, <tt>A[1..n]</tt>. <br><b>(b)</b> How many item-comparisons are made by your algorithm? <br><b>(c)</b> Write a simple Scratch program that implements your algorithm for (a). <P> <B>T4-Q3: (5 points) [Algorithm for Counting] </b><br> <b>(a)</b> Design an algorithm <b><tt>Count-List(D, n, X)</tt></b> to count the number of times that the number <tt>X</tt> appears in a list of numbers stored in a list <tt>D[1..n]</tt> of n numbers. (Note: <tt>D</tt> is an array (or list) with n numbers.) For example, if <tt>D = (2, 3, 7, 3, 2, 3, 8, 3)</tt> and <tt>X=3</tt>, then <tt>X</tt> appears 4 times. <br> (Note: You can modify the algoritm <tt>Array-Sum</tt> given in class.) <br><b>(b)</b> Modify the Scratch program <tt>sum-of-list.sb</tt> to implement this algorithm. Call your new program <tt>Count-List.sb</tt>. </p><p> <br> <!-- ----------------------------------------------------------- --> <!-- The A-Problems --- advanced problems --> <!-- ----------------------------------------------------------- --> </p><p></p><hr><b>A-Problems: OPTIONAL Challenging Problems for Further Exploration</b><br> A-problems are usually <i>advanced</i> 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. <P><b>A4: [More on <tt>Find-Max</tt> Updates] </b><br> Consider the <tt>Find-Max</tt> algorithm covered in class and also used in T4-Q1. Given a <i>random</i> permutation of <tt>{1,2,3,& ,<i>n</i>}</tt>, determine how many times (<i>on average</i>) the variable <i>Max-sf</i> is updated. <br> <b>[Some notes:</b> (1) You need some probability theory to do this, but only <i>elementary</i> prob. theory is needed, (2) You can also assume that all <i>n</i>! permutations of {1,2,...,<i>n</i>} are equally likely, and (3) The answer is *not* <i>n</i>/2.] </p><p> </p><hr> <address> UIT2201: CS & IT Revolution; (Spring 2012); A/P Leong HW <!-- <P> <B>T3-Q2: (10 points) [Getting the Grade]</b><br> (a) Give an algorithm that will read in a mark (an integer between 0 and 100) that a student gets for UIT2201, and computes the corresponding letter grades (A+, A, A-, B+, ...) according to the NUS "standard" grade scheme. <br>(b) Write a simple Scratch program that implements your algorithm. <P> <B>T2-D1: (Exercising an Algorithm) </b><br> For this problem, please first read the addition algorithm (C=A+B) for adding two <i>m</i>-digit number in the lecture notes (see Figure 1.2, page 7 & 8 of [SG3]) for more details). Trace through the execution of the <b>"addition algorithm" in the lecture notes</b> using the following input values: <br> &nbsp; &nbsp; m=4,<br> &nbsp; &nbsp; a<sub>3</sub> = 3, &nbsp; &nbsp; a<sub>2</sub> = 5, &nbsp; &nbsp; a<sub>1</sub> = 2, &nbsp; &nbsp; a<sub>0</sub> = 8, <br> &nbsp; &nbsp; b<sub>3</sub> = 9, &nbsp; &nbsp; b<sub>2</sub> = 6, &nbsp; &nbsp; b<sub>1</sub> = 4, &nbsp; &nbsp; b<sub>0</sub> = 7, <br> Show the <b>"state of the algorithm"</b> after Step 5 (of each iteration) and the output obtained in Step 8. To show the "state of the algorithm", show (in a table format) the value for <i>i, x, carry, c<sub>4</sub>, c<sub>3</sub>, c<sub>2</sub>, c<sub>1</sub>, c<sub>0</sub></i>. <br> (<b>Note:</b> If you have problem, See the example in the lecture notes.) --> </address></body></html>