CS501

Project #1

Fall 2006

1) Use simple mathematical induction to prove that statement S(n) is true for every positive number n.

S(n): 1³+2³+…+n³ = n²(n+1)²/4

2) Use strong or complete mathematical induction to prove that statement P(n) is true for every positive integer n.

P(n): If T is strictly binary tree, then the number of its external nodes is one more than the number of its internal nodes.

 
 
 
CS 501  
Project #2
Evaluate Truth Value of Propositional Expression
 
Propositional expression with binary operators has following recursive definition.
· Propositional variables (that have values true or false only) and boolean constants true and false are propositional expressions.
· If A and B are propositional expressions then A operator B is also a propositional expression.
Operator can be any of the following binary logical operators coded with a single symbol (to simplify syntax analysis) as follows: 
& ( AND operator, conjunction), 
v ( OR operator, disjunction), 
> ( implication), 
= ( equivalence).
 
Truth values for logical operators are defined with the following truth table.
 

A	B	A & B	A v B	A > B	A = B
T	T	T	T	T	T
T	F	F	T	F	F
F	T	F	T	T	F
F	F	F	F	T	T

 
The priorities of logical operators are defined as follows: All & are applied first, next all v are applied, next all > are applied, and finally all = are applied last. In case of two operators of the same priority the left one is applied first.
 Code operands as T (true) and F (false).
 
Write an application to evaluate the truth value of a propositional expression entered by user in postfix notation.
Assume that you have no more than twenty tokens (operands and operators). Assume that input is a propositional expression 
in postfix notation that has correct syntax. Enter expression with no spaces within it. 
 
Class that contains main method should be called Evaluator. 
Execution (when input is entered from the command line) should look like this
>java Evaluator TT&F>
Program should report 
The truth value of the postfix propositional expression "True True & False =>" is False.
 
Submit design of your program (class diagram hierarchy with uses and extends relationships between classes done in UML). For each method in a class specify preconditions, and postcoditions). Describe what data structures were used in your application and explain why. Also submit floppy disk or CD, printout of your code, and example runs.
 
 

Project#3

Write

· recursive method whose worst case running time is cubic.

· recursive method whose worst case running time is exponential.

· non-recursive method whose worst case running time is cubic.

For recursive methods provide recurrence relations that measure the number of times the basic operation is performed in terms of input size.

For non-recursive method provide informal analysis of the running time performance.

Methods that were analyzed in the class cannot be used for the project.