Data Structures and Algorithms Exercises

Part A

Consider the "circular" array implementation of a queue, similar to ArrayQueue that we studied in class, where the only difference is that the initial capacity is set to 4 (INITIAL_CAPACITY=4):

class ArrayQueue:
INITIAL_CAPACITY = 4
def __init__(self):
self.data_arr = make_array(ArrayQueue.INITIAL_CAPACITY)
self.num_of_elems = 0
self.front_ind = None
def __len__(self): …
def is_empty(self): …
def enqueue(self, elem): …
def dequeue(self): …
def first(self): …
def resize(self, new_cap): …

Show the values of the data members: front_ind, num_of_elems, and the contents of each data_arr[i] after each of the following operations.

If you need to increase the capacity of data_arr, add extra slots as described in class.

Part B

i) Draw the expression tree that corresponds to the following postfix expression:

2 3 4 * 5 6 + / - 7 +

ii) Find the prefix expressions that is equivalent to the following postfix expression:

4 6 2 5 + * 7 - / 1 +

Question 2

Many programming languages represent integers in a fixed number of bytes (a common size for an integer is 4 bytes). This, on one hand, bounds the range of integers that can be represented as an int data (in 4 bytes, only 232 different values could be represented), but, on the other hand, it allows fast execution for basic arithmetic expressions (such as +, -, * and /) typically done in hardware.

Python and some other programming languages do not follow that kind of representation for integers and allows for arbitrarily large integers to be stored as int variables. However, as a result, the performance of basic arithmetic is slower.

In this question, we will suggest a data structure for positive integer numbers, that can be arbitrary large (not the representation Python uses though). We will represent a positive integer value, as a doubly linked list of its digits. That is, each element in the doubly linked list would be an integer in the range 0-9. For example, the number 375 will be represented by a 3-length list, with 3, 7 and 5 as its elements.

Figure: see image.

Complete the definition of the following Integer class:

class Integer:
def __init__(self, num_str):
''' Initializes an Integer object representing
the value given in the string num_str '''
def __lt__(self, other):
''' returns True if”f the number represented in self is
less than the number represented in other, also of type
Integer '''

For example, after implementing the Integer class, you should expect the following behavior:

>>> n1 = Integer('336876451094675')
>>> n2 = Integer('978234')
>>> n3 = Integer('336876451987675')
>>> n1 < n2
False
>>> n1 < n3
True

Implementation requirements:

1. EACH Integer method has to run in worst case linear time.

2. When comparing Integer objects, DO NOT convert the Integer objects to ints, and then use the Python's built-in < operator. This approach misses the point of this question. However, You are allowed to use Pythons built-in < operator to compare single digits.

3. Since construction of this kind of objects was already given in the homework assignment, most of the points in this question would be given to the __lt__() method.

A Parity-Stack is an abstract data type that stores a collection of integer numbers. It behaves like a regular stack, but in addition to allowing to access (retrieve or remove) the number that entered last, it also allows to access (retrieve or remove) the even number that was entered last and the odd number that was entered last.

A Parity-Stack has the following operations:

• ps = ParityStack(): creates a new ParityStack object, with no numbers in it.
• ps.is_empty(): returns true if there are no numbers in ps, or false otherwise.
• ps.push(num): inserts num to ps.
• ps.pop(): removes and returns the number that was last to enter into ps, or raises an Exception if ps is empty.
• ps.pop_even(): removes and returns the even number that was last to enter into ps, or raises an Exception if there are no even numbers in ps.
• ps.pop_odd(): removes and returns the odd number that was last to enter into ps, or raises an Exception if there are no odd numbers in ps.
• ps.top(): returns (without removing) the number that was last to enter into ps, or raises an Exception if ps is empty.
• ps.top_even(): returns (without removing) the even number that was last to enter into ps, or raises an Exception if there are no even numbers in ps.
• ps.top_odd(): returns (without removing) the odd number that was last to enter into ps, or raises an Exception if there are no odd numbers in ps.

For example, you should expect the following interaction:

>>> ps = ParityStack()
>>> ps.push(1)
>>> ps.push(3)
>>> ps.push(2)
>>> ps.push(4)
>>> ps.push(5)
>>> ps.push(6)
>>> ps.push(7)
>>> ps.pop()
7
>>> ps.pop()
6
>>> ps.pop_even()
4
>>> ps.pop_odd()
5
>>> ps.pop_odd()
3
>>> ps.pop()
2
>>> ps.pop()
1
>>> ps.is_empty()
True

Write a ParityStack class, implementing the Parity-Stack ADT defined above.

Runtime requirement: Each ParityStack operation should run in (1) worst-case.

Notes:

1. Make sure to choose the most suitable data types for your data members, so you could satisfy the runtime requirement.

2. You may want to attach an additional information to each number the user enters to the parity-stack (store them as a tuple).

Consider the following binary tree: see image.

1. We can represent a path that starts at the root, as a doubly linked list of "left" and "right" strings, in an order that corresponds to the directions one should take when walking down the tree along this path.

For example, the path from the root, to the leaf with the value 6, is represented by the list: ["right" <--> "left" <--> "right" <--> "left"].

2. We define the "cost of a leaf L, as the sum of all the values in the nodes along the path from the root to L.

For example, the cost of the leaf with the value 6, is 24 (since, 4+5+1+8+6=24).

Give a recursive implementation of the following function:

def path_to_leaf_with_cost(root, target_cost)

When given root, a reference to a (non-empty) LinkedBinaryTree.Node, and a number target_cost, it will return a doubly linked list that represents the path to a leaf, in the tree rooted by root, with a cost equal to target_cost.

For example, if root is a reference the root of the tree above, the call path_to_leaf_with_cost(root, 13) should return: ["right" <--> "left" <--> "left"].

Notes:

1. If there is more than one leaf with cost equal to target_cost, the function would return the path to any one of them.

2. If there is no leaf with cost equal to target_cost, the function should return None.

Implementation requirements:

1. Your function has to run in worst case linear time. That is, if there are n nodes in the tree, your function should run in O(n) worst-case.

2. You must give a recursive implementation.

3. You are not allowed to:

• Define a helper function.
• Add parameters to the function's header line
• Set default values to any parameter.
• Use global variables

Consider the following definitions:

1. A nested list of integers is a list that stores integers in some hierarchy. That is, its elements are integers and/or other nested lists of integers.

For example nested_lst=[[1, 2], 3, [4, [5, 6, [7]], 8], 9] is a nested list of integers.

2. The nesting depth of an integer num in a nested list, is the number of "[" that are actively open when reading the string representation of the list from left to right until reaching the point where num appears. For example:

• The nesting depth of 3 and 9 is 1.
• The nesting depth of 1, 2, 4 and 8 is 2.
• The nesting depth of 5 and 6 is 3.
• The nesting depth of 7 is 4.

Implement the following function:

def flatten_by_nesting_depth(nested_lst)

The function is given a nested list of integers nested_list.

When called, it should create and return a flat list of integers containing all the numbers in nested_list.

The numbers should show in the returned list by their nesting depth. That is, first will come all the numbers with nesting depth 1, then would come all the numbers with nesting depth 2, followed by the numbers with nesting depth 3, etc.

Note: The order of the numbers with the same nested depth does not matter.

For example, if nested_list is the nested list demonstrated above, the call flatten_by_nesting_depth(nested_lst) could return:

[3, 9, 1, 2, 4, 8, 5, 6, 7]

Implementation requirements: You may use one ArrayQueue object. Besides the queue and the list that is created and returned, you may use only constant additional space. That is, besides the queue and the returned list, you may use variables to store an integer, a double, etc. However, you may not use an additional data structure (such as a list, stack, queue, etc.) to store non-constant number of elements.