Algorithms and Data Structures (INF1, Autumn'05)
Exercise Set 7
Exercise 1 :
Write appropriate pre- and post-conditions for the stack operations
push, top and pop.
Exercise 2:
Implement the stack operations push, top and pop in the
singly-linked list implementation from the lecture (in a stack s
the last entry in the singly-linked list is accessed by last).
Exercise 3:
Write a procedure reverse(l:LIST) such that it is totally
correct with regard to the following pre- and post-conditions.
--pre: l=< a1, a2 ..., an >
reverse(l)
--post: l'= < an, ..., a2, a1 >
Write an iterative algorithm using stack. What is the worst-case time
complexity of your algorithm?
Exercise 4 (hand-in):
Write appropriate pre- and post-conditions for the queue operations
enqueue, front and dequeue.
Exercise 5 (hand-in):
Implement the queue operations enqueue, front and dequeue
in the circular singly-linked list implementation from the lecture
(in a queue q the last entry at the back of the queue
is accessed by last
and the first entry is accessed by last.next_entry).
Exercise 6:
Write a function member(x:ENTRY_TYPE; q:QUEUE):boolean which uses
only the queue operations enqueue, front and dequeue and no
extra temporary data structures (except for variables).
The function should return true if and only if the entry x is
present in the queue q. The queue q should not be changed after
executing the function member.
Analyze the worst-case time complexity of your algorithm.
Exercise 7 (voluntary, I will correct your solution if you give me any):
Highly recommended: try to solve this exercise individually, the exam
will be also individual!
Write an algorithm for a list operation
merge(l1:LIST; l2:LIST): LIST
which satisfies the following pre- and post-conditions.
--pre: l1=< a1, ..., an > and
l2=< b1, ..., bm > are
non-decreasing lists, i.e., a1.value <=
a2.value <= ... <= an.value and
b1.value <=
b2.value <= ... <= bm.value
l3 := merge(l1,l2)
--post: l3 is a non-decreasing list, it is a permutation
of the entries a1, ..., an,
b1, ..., bm and l'1=<>
and l'2=<>
What is the worst-case time complexity of your algorithm (use big-O notation)?