1. Below are three computational tasks. For each one, choose the data structure
ID: 3588022 • Letter: 1
Question
1. Below are three computational tasks. For each one, choose the data structure or abstract data type you feel best suited to the task from the following list: Stack, Queue, Hashtable, AVL Tree, Priority Queue, Union-Find. In addition, list the basic operations for the data structure or ADT that you chose and give asymptotic worst-case running times for those operations. No additional explanation is required.
e) Store the activation records (i.e. objects containing the return address and local variable associated with a function call) for nested function calls.
f) What is log2(1; 000; 000; 000) to the nearest whole number?
g) Your friend says she does not like implementing algorithms that have amortized run-time guarantees because amortization makes it harder to debug her code. Why does this argument
make no sense? (A one sentence answer is probably enough.)
Explanation / Answer
e) We can use stack for nested function
Operations available: push, pop
Worst case running time:O(1) for both as we dont need to loop through anyting.
f) log2(1 billion) can be calculated using avl trees.
Nearest whole number is 29.
Operations available are insert, delete, find.
Worst case run time is O(n) when all the elements are on same side of tree like in a list.
f) Data structure: Hash table
Operations available are: insert, find, delete
Worst case run time: O(n) when all the elements are to be inserted at same key or when hash table has passed its load balance.
Reason that statement in your question makes no sense: Ammortisation involves probability and it is highly unlikely that worst case scenario would occur. Upon random analysis of algorithm, faster runtime is expected than the worst case running time.
If you face any issue, you can leave a comment, thanks.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.