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