STACK, QUEUE, DECK STRUCTURES, TIME COMPLEXITY, BIG O NOTATION

Part A:

1. Create a function for calculation of a transpose of any variable sized matrix(MxN where M and N are variables) by using stack structure.

def transpose_stack(inp_mat):

out_mat=[]

return out_mat

For example:If inp_mat=[[0, 1, 2], [3, 4, 5]], then return value=[[0, 3], [1, 4], [2,5]]

1. Create a function for calculation of at transpose of any variable sized matrix(MxN where M and N are variables) by using queue structure.

def transpose_queue(inp_mat):

out_mat=[]

return out_mat

2. Create a function for calculation of at transpose of any variable sized matrix(MxN where M and N are variables) by using deck structure.

def transpose_deck(inp_mat):

out_mat=[]

return out_mat

Note: The necessary structures stack, deck and queue are given in the second page.

Part B:

Show the computational complexity of each function by using Time or Timer module.

Part C:

Compute Big-O notation of each algorithm by hand. Show your calculations in detail.

####

####

class Stack: def __init__(self): self.items = [] def pop(self): if self.isEmpty(): raise RuntimeError("Attempt to pop an empty stack") topIdx = len(self.items)-1 item = self.items[topIdx] del self.items[topIdx] return item def push(self,item): self.items.append(item) def top(self): if self.isEmpty(): raise RuntimeError("Attempt to get top of empty stack") topIdx = len(self.items)-1 return self.items[topIdx] def isEmpty(self): return len(self.items) == 0 class Queue: def __init__(self): self.items = [] self.frontIdx = 0 def __compress(self): newlst = [] for i in range(self.frontIdx,len(self.items)): newlst.append(self.items[i]) self.items = newlst self.frontIdx = 0 def dequeue(self): if self.isEmpty(): raise RuntimeError("Attempt to dequeue an empty queue") if self.frontIdx * 2 > len(self.items): self.__compress() item = self.items[self.frontIdx] self.frontIdx += 1 return item def enqueue(self,item): self.items.append(item) def front(self): if self.isEmpty(): raise RuntimeError("Attempt to access front of empty queue") return self.items[self.frontIdx] def isEmpty(self): return self.frontIdx == len(self.items) class Deque: def __init__(self): self.items = [] def is_empty(self): return self.items == [] def add_front(self, item): self.items.append(item) def add_rear(self, item): self.items.insert(0,item) def remove_front(self): return self.items.pop() def remove_rear(self): return self.items.pop(0) def size(self): return len(self.items)