Assignment 3 Implementation of Stack

Assignment 3

Note: For all programming questions, you must use Python 3.2.3 or higher.
Consider using the design recipe and Python style guide available from the course
website. Approximately 80% of the marks of each question will be allocated to
correctness, with the remaining 20% to style, including aspects of the design
recipe. Examples and tests are optional.
Programming Component
In programming component, you can use the provided data structure file
(dataStructures.py), which includes implementation of Stack, Queue, Priority
Queue from course slides.
Consider the Stack ADT defined in our lectures as follows:
Stack() Creates a new empty stack.
isEmpty() Returns a Boolean value indicating if the stack is empty.
length() Returns the number of items in the stack.
pop() Removes and returns the top item of the stack, if the stack is not
empty. Item cannot be popped from an empty stack. The next item
on the stack becomes the new top item.
peek() Returns a reference to the item on top of a non-empty stack without
removing it. Peeking, which cannot be done on an empty stack, does
not modify the stack contents.
push(item) Adds the given item to the top of the stack.
1. (9 marks) Use a single Queue to implement the Stack ADT.
2. (9 marks) Use a Priority Queue to implement the Stack ADT.
3. (10 marks) Given a text compression algorithm, it compresses files with only lowercase
alphabets (a – z) by representing a repeated pattern. The pattern is: k{text_string},
where the text_string inside the curly brackets is being repeated exactly k times.
Note:
1) k is guaranteed to be a positive integer.
2) You may assume that the input compressed file string is always valid.
3) No extra white spaces.
4) Curly brackets are well-formed and balanced.
5) You may assume that there are not any digits in the original file text. Digits are
only used for representing repeat numbers k. For example, there won’t be
strings such as 3a or 2{4}.
Please write a Python function decompressFile(txt), where txt is a string type
which represents the compressed file. The function returns a string of the original file
text.
For example:
txt = “2{a}3{bc}”, decompressFile(txt) - “aabcbcbc”
txt = “2{a3{c}}”, decompressFile(txt) - ”acccaccc”
txt = “3{abc}2{cd}ef”, decompressFile(txt) -
“abcabcabccdcdef”
4. (10 marks) Given a binary tree, return the inorder traversal of its nodes’ values using
Stack.
class BinTreeNode:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
You may assume that data in each node of the binary tree is a positive integer. Please
write a Python function inorderTraversal(root), where root is a root node
(BinTreeNode type). It returns a list of integers of the tree nodes’ values.
Written Component
5. (6 marks) What is the running time of the operations on Stack implementation of
Question 1. Justify your answers.
6. (6 marks) What is the running time of the operations on Stack implementation of
Question 2. Justify your answers.
7. (10 marks) Given a hash table of size 16, with hash function h(x) = x mod 16, we
want to insert prime numbers in sequence starting at 11 (i.e. 11, 13, 17, 19, 23, 29, … )
until two collisions occur – that is, include the number that causes the second collision.
Show the above procedure (insertion by insertion, showing the contents of the array
after each insertion) with collisions handled by:
1) Linear probing.
2) Double hashing, with the hash function for the jump size being
h_j(x) = (x mod 10) OR 1 (that is, we take the number modulo 10, and if it
is even, we add 1, so that we can only obtain values 1, 3, 5, 7, or 9).
Submission: Please use the provided files for the programming
component: a3q1.py, a3q2.py, a3q3.py, a3q4.py. Please submit pdf files
for Question 5, Question 6 and Question 7.