7CCSMASE
Tutorial 4
1. Show the data dependence and control flow graphs for the following program:
public int kcl(int x, int y){ int a;
int b;
while(𝑦 ≤ 10){
a = x*y; b = y-x; y++;
}
return a; }
• Annotate the nodes to indicate the definitions/uses of variables a, x and y.
• Draw the control-dependence graph for the program.
2. Consider the following simple program (in no particular language) to find the smallest prime factor of a number:
smallest(int p) /* precondition p > 1 */ {
int q = 2;
while(p mod q > 0 AND q < sqrt(p) )
q := q+1
;
if (p mod q = 0)
then
print(q,''is the smallest factor'') else
print(p, ``is prime'')
;
}
• Draw the control flow graph for this program and annotate the nodes to indicate the definitions/uses of variables p and q.
• Label the nodes and give All DU Paths for p and q. (A du-path from node x to node y for a variable v is a simple path from x to y which is definition clear for v and which assigns to v at x and uses v at y)
3. Draw a finite state machine for the design of the vending machine for one type of chocolate
bar:
• Release item after receiving 15 cents
o Singlecoinslotfordimes(10¢)andnickels(5¢)–assumingsensorspecifies coin type
o Machinedoesnotgivechange
• Draw state diagram by considering the below input sequences: o 3nickels
o 2nickels,dime o Nickel,dime
o Dime,nickel
o Twodimes
*Inputs: N, D, reset *Output: Open
*What would change if, for example, the machine had had the option to dispense two types of chocolate bar? There would be two buttons to choose a bar (say, one for Mars and one for Snickers) and the machine would give change.