A&DS S01E06. Stacks. Queues. Amortized cost

Algorithms and data structures. Semester 1. Lecture 6.
In the sixth lecture, we discussed stacks and queues, and also talked about what amortized time cost is, why it is needed and how to measure it.
Home task and discussion: codeforces.com...
ITMO University, 2020

[@chuka231d8]

Content of this lecture:
1.Stack
2.Queue
3.Deque
4.Amortized Analysis (Potential Function, Accounting Method, Making queue with 2 stacks)

[@parthsharma7129]

Potential Technique for finding Amortized cost
TimeStamp : 53:28

[@A57278]

how the array cycle would help if i keep push-ing with no pop-ing? 21:15

[@madhukiranattivilli2321]

1:32:54 -- build Q from 2 stacks
Hi Pavel,
Shouldn't we have the 1st statement for Q.remove() as :
if !S1.empty() return S1.pop()
???

[@pavelmavrin]

Yes, sure. It's hard to code without bugs on a whiteboard :)

[@madhukiranattivilli2321]

@@pavelmavrin That's ok. I understand. Just wanted to clarify
Thanks for regular responses. Please continue this gr8 habit. I huuuuugely appreciate. I too will control my urges to not ask trivial Qs. May be this 1 is trivial :)
I guess there is only 1 from U that I'm waiting on. Will ping on that msg. Cud u pls write there? It's a continuation, not fresh msg (on "counting sort, etc" lecture)

[@Mit_Bambhroliya]

Hi pavel sir, I have a query at 47:23 how m is >= 2^(k) I didn't get it please help me to understand this.

[@raunak1147]

It's the 'definition' of k here, k is essentially floor(log_2(m)), that's what we've taken it to be to simplify the analysis.
(It is kind of like taking a relaxation on m, by constraining m to be a perfect square, however by taking such a k we drop the need for such a relaxation)

[@udayanjoshi2691]

No home tasks this time around? Find them here codeforces.com/blog/entry/83756

[@LongNguyen-gz4yq]

❤