Homework 5



Homework 5 due 05/03/02

Hand in typed or handwritten C++ code containing your solutions of problems 1-7 (you do not need to run the code).

1. How many function calls are performed during computing

• Fibonacci(6) by the algorithm

int Fibonacci(int n)

{

if(n==0 || n==1)

return 1;

else

return Fibonacci(n-1)+Fibonacci(n-2);

}

• C(6,2) by the algorithm

int C(int n,int k)

{

if(k==0 || k==n)

return 1;

else

return C(n-1,k-1)+C(n-1,k);

}

2. Write a recursive C++ function which computes powers of 2 in the following manner

[pic]

How many function calls are performed during computing P(1025)?

3. Draw the decision tree for the binary search algorithm acting on a sorted list consisting of 12 elements (if there is no middle take the middle right element).

Example: For a 6 element list the tree is the following.

[pic]

x>L[.] –go to the right, x0)

{

r=n%2;

m=n/2;

Dec_to_Bin(m);

cout link);

cout data;

}

}

X-tra credit:

Write a program, which takes logical formulas as input and checks whether they are logical tautologies. Input formulas may contain any number of variables.

Logical operators are defined by their truth tables:

not

| p | ( p |

| 0 | 1 |

| 1 | 0 |

and

| p | q | p(q |

| 0 | 0 | 0 |

| 0 | 1 | 0 |

| 1 | 0 | 0 |

| 1 | 1 | 1 |

or

| p | q | p(q |

| 0 | 0 | 0 |

| 0 | 1 | 1 |

| 1 | 0 | 1 |

| 1 | 1 | 1 |

if and only if

| p | q | p( q |

| 0 | 0 | 1 |

| 0 | 1 | 0 |

| 1 | 0 | 0 |

| 1 | 1 | 1 |

if then

| p | q | p(q |

| 0 | 0 | 1 |

| 0 | 1 | 1 |

| 1 | 0 | 0 |

| 1 | 1 | 1 |

0 means false and 1 means true. A logical tautology is a logical formula, which is true for all possible logical values of variables involved in it. For example

( (p(q)(( ( p((q)

is a logical tautology. For all possible logical values of p and q the resulting logical value of the above expression is 1. Make sure that your program accepts any logical formula without limiting the number of variables. You may assume for simplicity that a pair of parentheses accompanies any logical operator.

Hint: Modify the algorithm for evaluating arithmetic expressions.

Your solution should consist of a tested C++ program submitted in UNIX environment or as a Visual C++ workspace. To get the credit for your solution you will need to make an appointment with me before or on 05/08/02 to demonstrate your solution (you will need to run your programs with various input data as well as discuss your implementation).

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download