Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
compX123
Tutorial 2: Lists
s2 2024
Warm-up
Problem 1. Suppose we implement a stack using a singly linked list. What would be the complexity of the push and pop
operations? Try to be as efficient as possible.
Problem 2. Suppose we implement a queue using a singly linked list. What would be the complexity of the enqueue and
dequeue operations? Try to be as efficient as possible.
Problem solving
Problem 3. We want to extend the queue that we saw during the lectures with an operation
getAverage() that returns the average value of all elements stored in the queue.
This operation should run in O(1) time and the running time of the other queue operations should remain the same
as those of a regular queue.
a) Design the getAverage() operation. Also describe any changes you make to the other operations, if any.
b) Briefly argue the correctness of your operation(s).
c) Analyse the running time of your operation(s).
Problem 4. Given a singly linked list, we would like to traverse the elements of the list in reverse order.
a) Design an algorithm that uses O(1) extra space. What is the best time complexity you can get?
b) Design an algorithm that uses O(√n) extra space. What is the best time complexity you can get?
You are not allowed to modify the list, but you are allowed to use position/cursors to move around the list.
Problem 5. Using only two stacks, provide an implementation of a queue. Analyze the time complexity of enqueue
and dequeue operations.
Problem 6. Consider the problem of given an integer n, generating all possible permuta- tions of the numbers {1, 2, . .
. , n}. Provide a recursive algorithm for this problem.
Problem 7. Consider the problem of given an integer n, generating all possible permu- tations of the numbers {1, 2, . . . , n}.
Provide a non-recursive algorithm for this problem using a stack.