There are some code files as well, once I think the quote is good, I can upload them as...

Question

There are some code files as well, once I think the quote is good, I can upload them as well.

Assignment 1 Note: Submitting wrong files or in the wrong format or corrupted files or missing files will not give you permission to re-submit. It is your responsibility to submit all the correct files on time. 1. Time complexity: Write a written report where you analyze the time and space complexity (best and worst case scenario) for each of the following functions in the dlinkedlist code. The analysis must explain the complexity for each block of code, show the exact calculations, and give the final time complexity and rate of growth. a) is_unique b) add_last c) get_list d) complete 2. Transaction Manager: a) Implement a manager class which imports and uses dlinkedlist (code is provided in week 2 course materials) to manage a list of transactions. You may not change any of the dlinkedlist code or files. You must use the functionality that is provided in your code and not write all functionality from scratch. You will be graded on using the existing code efficiently and on your functionality working correctly. b) The manager class must have the following functionality (each a separate function):  Add one or more transaction objects to the manager’s dlinkedlist attribute  Find a stored transaction using tid and return that transaction instance  Complete specific transaction  Display all currently stored transactions  Delete all transactions c) Write test code to demonstrate correct functionality of transaction manager. All input must be hardcoded and output should be written to the console. d) Analyze in writing the time and space complexity of each function, showing all calculations and then giving the final grow rate for the best and worst case scenarios. 3. Queue/Stack usage: a) Implement a program which imports and uses provided dlinkedlist, queue and stack ADTs (code is provided in week 2 course materials) and implements the below functionality. You cannot modify any of the provided code.  Function called reversel which takes as a parameter an instance of dlinkedlist (populated with transaction objects) and returns a new instance with copies of the items in reverse order. Make sure to validate that the parameter is dlinkedlist and not None  Function called completeq which takes as a parameter an instance of queue (populated with transaction objects) and a tid value. The method then completes the transaction with the given tid. At the end of the function, the queue must have all the elements in the same order as given. You must only use queue/stack operations for the functionality, you cannot access queue’s underlying storage directly, and you cannot use Python lists. Make sure to make your code time and space efficient.  Function called copyqts which takes as parameter an instance of queue (populated with transaction objects) and returns a stack instance with copied items in the same remove order as the queue. At the end of the function, the queue must have all the elements in the same order as given. You must only use queue/stack operations for the functionality, you cannot access queue’s underlying storage directly, and you cannot use Python lists. Make sure to make your code time and space efficient. b) Write test code to demonstrate that the above methods work correctly c) Analyze in writing, explaining all calculations and then giving the final grow rate, time and space complexity of the methods to include best and worst case 4. Submission instructions: Submit one zip file with all the programs and separate pdf or word file with written analysis of time/space complexities for all exercises Grading Rubric Points Criteria 30 Time complexities: Includes correct written analysis of space/time complexity that shows all calculations to include best and worst case and final growth rate for each indicated function 40 Transaction Manager using dlinkedlist code: Correctly implemented functions Correctly implemented test code that demonstrates correctness Includes correct written analysis of space/time complexity that shows all calculations to include best and worst case and final growth rate 30 Stack/Queue usage: Correctly implemented functions Correctly implemented test code that demonstrates correctness Includes correct written analysis of space/time complexity that shows all calculations to include best and worst case and final growth rate

assignment1-4anz1yr0.pdf python-36-assignment1-code-1-12bxqi2d-ykskc5j0.zip

Aniket · Accepted Answer

dlinkedlist.py
import datetime
class dlinkedlist:
    class transaction:
        def __init__(self, tid):
            if not isinstance(tid, int):
                raise TypeError('tid must be integer')
            self.tid = tid
            self.completed = False
        @property
        def key(self):
            return self.tid
        def clone(self):
            t = dlinkedlist.transaction(self.tid)
            t.completed = self.completed
            return t
        def complete(self):
            self.completed = True
        def __str__(self):
            return 'tid={} completed={} '.format(self.tid, self.completed)
    class node:
        def __init__(self, value):
            if not isinstance(value, dlinkedlist.transaction):
                raise TypeError('item must be instance of dlinkedlist.transaction')
            self.item = value
            self.next = None
            self.prev = None
        @property
        def key(self):
            return self.item.key
    def __init__(self):
        self.front = None
        self.rear = None
        self.length = 0
    def is_unique(self, key):
        n = self.front
        while n is not None:
            if n.key == key:
                return False
            n = n.next
        return True
    def add_last(self, item):
        if not self.is_unique(item.key):
            raise AttributeError('Duplicate key is not allowed')
        n = self.node(item.clone())
        if self.front is None:
            self.front = self.rear = n
        else:
            self.rear.next = n
            n.prev = self.rear
            self.rear = n
        self.length = self.length + 1
    def delete_first(self):
        n = self.front
        if self.front == self.rear:
            self.front = self.rear = None
        else:
            self.front = self.front.

Assignment 1 Note: Submitting wrong files or in the wrong format or corrupted files or missing files will not give you permission to re-submit. It is your responsibility to submit all the correct...

Answer To: Assignment 1 Note: Submitting wrong files or in the wrong format or corrupted files or missing files...

Answer To This Question Is Available To Download

Related Questions & Answers

Submit New Assignment