Question
STACK, QUEUE, DECK STRUCTURES, TIME COMPLEXITY, BIG O NOTATION Part A: Create a function for calculation of a transpose of any variable sized matrix(MxN where
STACK, QUEUE, DECK STRUCTURES, TIME COMPLEXITY, BIG O NOTATION
Part A:
- 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]]
- 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
- 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)
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started