The word stack is used to describe a memory that can be written by adding a new
ID: 665802 • Letter: T
Question
The word stack is used to describe a memory that can be written by adding a new item to the "top" and read by reading the item at the top. Reads are destructive, removing the top item. If the stack is the only memory, data read are lost after reading. The progress of a computation using a stack often manifests in a changing height of the stack. A queue, by contrast, is a list of items to be remembered. New items are added at one end, and reads occur at the other end.
(a) What is the maximum occupied height of the stack during depth first search?
(b) What is the maximum occupied size of the queue during breadth first search?
(c) Note that it is possible to create equivalence classes over computations according to the occupied size of the stack or queue. Suppose computations were to be classified into two equivalence classes based upon their consumption of memory (stack or queue). Propose two such classes, and explain why they form a partition over computations.
Explanation / Answer
Multiple sub-parts post one more problem. Thanks
a)
In DFS algorithm the maximum stack depth is equal to the maximum distance from the origin vertex in the DFS traversal
b)
In BFS algorithm the maximum queue size is equal to the width of the largest vertex discovery front.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.