热门代写
- 代做DEN401/DENM004 Computational...
- 代写ECON33001 MACROECONOMICS OF...
- 代做Quantitative Skills for...
- 代做MTH020 INTRODUCTORY...
- 代写BMGT3006S Supply Chain...
- 代写COM60704/ COM62004 MEDIA...
- 代做EEE8087 4W Real Time Embedded ...
- 代写Assignment – Spatial Data and...
- 代写PHYS4035 MACHINE LEARNING IN...
- 代做APH402 Homework 2代做留学...
代做compX123 Tutorial 2: Lists s2 2024代写C/C++语言

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.