^CSE2304^
Tutorial 2, CSE2304, CSSE, Monash, Semester 1, 2005
Weeks 5-6, 4 to 15 April
Class:
Prepare your answers to the questions before the tutorial!
It will probably not be possible to cover all questions unless
the class has prepared them all in advance.
(The online versions of the tutorials may contain extra
information and links.)
Tutors:
(i) The purpose of the tutorials is not to solve
the practical exercises!
(ii) The purpose is to check answers, and
to discuss particular sticking points,
not to simply make answers available.
Objectives:
The tutorials give practice in
problem solving,
analysis of algorithms and data-structures, and
mathematics and logic useful in the above.
-
- Here are definitions of a list type for the linked-list data structure
and of two algorithms, append and length, on lists:
- List e = Nil | Cons e (List e)
-
- append Nil ys = ys
- append (Cons x xs) ys = Cons x (append xs ys)
-
- length Nil = 0
- length (Cons x xs) = 1 + (length xs)
-
- (i) Prove formally that
length(append a b) = (length a) + (length b),
for all lists a and b.
- (ii) Which expression is faster to evaluate,
the left or right hand side of the equality in (i)? Why?
- (iii) How could a compiler use such equalities?
-
- A problem to solve:
x, y and z are floating point variables.
Give a short piece of C-code to find
the median value of x, y, and z.
-
- Given the following algorithm:
for i from Lo1 to Hi1 do
for j from Lo2 to Hi2 do
body
end_for
end_for
- How many times is body executed if
-
- Lo1=1, Hi1=10, Lo2=i, Hi2=10,
- Lo1=0, Hi1= 9, Lo2=0, Hi2= 9,
- Lo1=1, Hi1=n, Lo2=i-2, Hi2=i+2,
- Lo1=0, Hi1=n, Lo2=i, Hi2=2*i ?
-
- A permutation of n things is a sequence of the n things in some order.
E.g., [1,2,3] and [3,1,2] are both permutations of the set of things {1,2,3}.
- Permutations of {1..n} can be ordered lexicographically,
e.g., [1,2,3] < [1,3,2] < [2,1,3] < [2,3,1] < [3,1,2] < [3,2,1].
- (i) If n=7, what is the next permutation after [4,7,5,2,6,3,1]?
- (ii) Give C-code for an algorithm,
next(int n, int p[]),
which is given a permutation of {1..n} in p[] and
which changes p[] so that it holds
the next permutation in lexicographical order (assuming there is one).
- (iii) Give a formal, logical argument
(as in [e.g.] & other examples)
that your routine
(a) terminates and
(b) is correct.
© L. Allison 2005,
School of Computer Science and Software Engineering,
Monash University, Australia 3800.
Created with "vi (Linux & Solaris)", charset=iso-8859-1