The word stack is used to describe a memory that can be written by adding a new
ID: 665846 • 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
The classic DFS is a completely different algorithm with significantly different core structure. True DFS is a genuinely recursive algorithm that uses stack for backtracking purposes, not for storing the vertex discovery "front" (as is the case in BFS). The most immediate consequence of that is that in DFS algorithm the maximum stack depth is equal to the maximum distance from the origin vertex in the DFS traversal. In BFS algorithm (as in the aforementioned pseudo-DFS) 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.