Thema der Dissertation:
Weak Unit Disk Contact Representations and Colored Nearest Neighbor Graphs Thema der Disputation:
Simulating a stack using queues
Weak Unit Disk Contact Representations and Colored Nearest Neighbor Graphs Thema der Disputation:
Simulating a stack using queues
Abstract: Simulating a queue using two stacks is a common exercise in a data structure course. It is well-known that it can be done using only a constant number of stack operations per queue operation, both amortized and in the worst case. The reverse problem of simulating a stack using queues, however, has gotten barely any attention in the past. In their 2022 work Kaplan, Tarjan, Zamir, and Zwick present solutions for several variants of this problem. For the offline case they show a tight worst-case bound of Θ((1/k + k/log n) n^(1+1/k) + n log_k n) for a sequence of n stack operations. The online case is more diverse and we look at k queues to simulate a stack, which at any time contains at most n elements. For constant k (independent of n) the number of queue operations per stack operations is shown to be a tight Θ(n^(1/k)) both amortized and in the worst case. If k is not constant but grows with n, there are gaps and differences between the amortized and worst-case results. In the amortized case it is O(n^(1/k) + log_k n) versus Ω((1/k + k/log n) n^(1/k) + log_k n) while the worst-case results in O(kn^(1/k)) versus Ω(n^(1/k) + log_k n).In this talk we will look at some of the results for the online case.
Zeit & Ort
08.11.2024 | 14:15
Seminarraum 049
(Fachbereich Mathematik und Informatik, Takustr. 9, 14195 Berlin)