ECE 209 Spring 2010 Homework 1 1 Homework 1 Due: January 25, 2010, 1:59pm NAME: __________________________________________________________ Edit this file and submit your answers electronically using the course webpage. ECE 209 Spring 2010 Homework 1 2 1. Write an algorithm in pseudocode that finds the greatest common divisor of two integers, X and Y. You may use any algorithm to compute the GCD, but be sure that your pseudocode mets the three requirements of an algorithm: definitenes, efectively computable, and finitenes. Subroutine gcd(X, Y): X = Absolute value of X Y = Absolute value of Y Min = Minimum of X and Y Max = Maximum of X and Y ; Handle special case that Min is 0 ; If Min is 0, GCD is Max, no matter what it?s value ; including 0 If Min is 0: GCD is Max Exit subroutine ; Look at all possible divisors less than or equal ; to smaller number. The greatest one must be the ; the GCD. This loop must terminate because it will ; only loop from 2 to Min, and Min can?t be negative ; If Min is less than 2, GCD will be 1 GCD = 1 For I from 2 to Min: If I divides both Max and Min evenly: GCD = I The GCD variable has the final value Exit subroutine ECE 209 Spring 2010 Homework 1 3 2. The table on the right lists a set of C variables and their values. What is the value of each expresion given below? (Make sure to write the value as the correct type. For example, write ?2.0? instead of ?2? if the expresion results in a floating-point value.) Use the table of operators in the textbook, or on the C reference sheet, to determine the precedence and asociativity of operators. Evaluate each expresion independently using the value in the table without propagating changes. Expresion Value a + bravo * 3 ______16____ a / 3 + eNum _______7____ eNum * cost _____8.4____ eNum + bravo << 2 ______12____ f *= 1000.0 + cost __4.209e-1__ cost / 3 * 2 ____1.4_____ d & (a=0x20) _____0______ a | 0xf _____0xf____ a & 1 + bravo & 3 ______2_____ a / eNum / 3 ______0_____ cost > 3.0 ______0_____ (a | 0x3) && (eNum >> 3) ______0_____ d = bravo = eNum ______4_____ bravo << eNum ? 2 ______8_____ a++ + --bravo % 8 _____11_____ (a && eNum) == !0 ______1_____ Variable Value a 10 bravo 2 cost 2.1 d ?W? eNum 4 f 4.2e-4 The last one is 1 because C99 converts Boolean values into 0 and 1. a&enum becomes 1 and !0 becomes 1. ECE 209 Spring 2010 Homework 1 4 3. Sheldon?s friendship flowchart shown in Lecture 1 has at least two flaws that result in non- terminating behavior. Fix Sheldon?s algorithm to guarante that the flowchart wil terminate in one of the following states: (1) in the beginning of a new friendship or (2) the failure to start one. Hint: one of the problems with the algorithm was debugged on the fly in an episode of The Big Bang Theory. Modified parts of the flow chart are shown in grey. There are stil some other problems not fixed here. Place Phone Call Home? Would you like to share a meal? Dine Together What is response? Leave Message Wait for Callback for 2 Days Do You Enjoy a Hot Beverage? What is response? Case: Tea Coffee Cocoa Action: Have Tea Have Coffee Have Cocoa Begin Friendship Recreational Activities! Tell me one of your interests? Do I share that interest? Why don't we do that together? Partake in interest Sheldon's Friendship Flowchart Yes No Yes No Yes No Yes No Have we discussed 3 options? No Choose Least Objectionable Activity Yes Received Callback? Yes Called only once? No Give up on friendship for now. Yes No James Tuck hw1-sol