Algorithms and Data Structures (INF1, Autumn'05)
Exercise Set 2
Exercise 1:
Exercise 1.1 from Algorithms and Data Structures: Design, Correctness and Analysis by Jeffrey H. Kingston.
Exercise 2:
State appropriate pre- and post-conditions for the following algorithm
and prove that it is correct with respect to that specification (find
appropriate assertions).
procedure XY (x,y:INTEGER)
x := x+y
y := x-y
x := x-y
end
Exercise 3:
Let us consider the following algorithm for computing factorial.
factorial(n)=
if n=0 then return 1
else return n*factorial(n-1)
endif
Let us consider the following pre- and post-condition.
-- pre: n is an integer
x:=factorial(n)
-- post: x=n!
- Is this algorithm totally correct with respect to these pre- and
post-conditions? Why?
- Is this algorithm partially correct with respect to these pre- and
post-conditions? Why?
Exercise 4:
Exercise 1.2 from Algorithms and Data Structures: Design, Correctness and Analys
is by Jeffrey H. Kingston.