Description

ALGORITHMS AND DATA STRUCTURES (CH08-320201)
Prof. Dr. Michael Sedlmair
Computer Science & Electrical Engineering
Problem 1: Stacks & Queues (7+3=10 points)
(a) Implement in Python or C++ the data structure of a stack backed up by a linked list, that can workfor whatever type, and analyze the running time of each specific operation. In order to achieve this in C++, make use of template < classT >, on which you can find more information at Templates.
Implement the stack such that you have the possibility of setting a fixed size but not necessarily have to (size is -1 when unset). Check for the correctness of your functions and throw exceptions with suggestive messages in cases of underflow or overflow(C++,Python). You can assume that if the size is passed, it always has a valid value.
class Stack [A ] ( ) :
private :
s t r u c t StackNode ( ) { / / linked l i s t
A data ;
StackNode ∗next ;
};
StackNode ∗top ; / / top of stack i n t size ; / /−1 i f not set , value otherwise
i n t current size ; / / unused i f size = −1 public :
fun push ( x :A) : void / / i f size set , check f o r overflow fun pop ( ) :A / / return element i f not in underflow
fun isEmpty ( ) : bool / / 1 i s empty , 0 otherwise fun Stack ( i n t new size ) fun Stack ( )
5
10
15
Checking will be done by case-tests alone. The tests will cover overflow and underflow cases, as well as tests for different types of variables.
(b) Show how a queue can be implemented with two stacks.
Problem 2: Linked Lists & Rooted Trees (4+5+3=12 points)
(a) Program an in-situ algorithm that reverses a linked list of n elements in Θ(n). Add an explanation to why it is an in-situ algorithm in the code.
(b) Program an algorithm to convert a binary search tree to a sorted linked list and derive its asymptotictime complexity.
(c) Program an algorithm to convert a sorted linked list to a binary search tree and derive its asymptotictime complexity.
Remarks
• Exercises marked with a * are bonus problems. These count towards your number of points for this homework. The maximum number of official points can not be exceeded.
2