The Tales of Class Preparations and Classroom Teaching. Series title: "What it means to prepare for a 45 minute lecture and then say " Any questions? Does it make sense? ..."

 It was 12th April 2021, and revising the contents for the undergraduate class scheduled at 2:25 PM for the course Advanced Data Structures and Algorithms. The topic to be explained is "Amortized Analyzed". 

I was contended with my preparations as well as not, both -- yes I was in a polarized state. 

    Contended with the preparations because I had taken almost three to four weeks time (though not in continuum mode) just to understand what is Amortized Analysis, how is this different from traditional analysis -- asymptotic analysis that I have learnt so far? The process involved reading various website contents, watching dozens of YouTube videos, including MIT's, IIT's, reading the bible -- Introduction to Algorithms, 3rd edition by Thomas Cormen et al. etc. 

    I was not contended because I was unable to digest the fact that worst-case time complexity of a MultiPop() function is O(n^2), when analyzed using traditional approach. Finally, after reiterating all the study resources for a couple of times, I was bit convinced and said my self, "...yes I have nailed it!" 

The class commended sharp at 2:25 PM and I started explaining the learners what they learned in the earlier classes and what they shall learn in today's. Being passionate about pedagogical teaching approach, I started the class with the questions "what's the time complexity of PUSH and POP operations"? I got the response immediately. 

Then I introduced the new function named MultiPop() and briefed its working principle.  Now it was time to explain the running time complexity using asymptotic analysis approach. The conversation between the learners and myself goes this way...

Me: What is the worst case time-complexity on popping an element from a stack having n elements using MultiPop() function?

Learners: A couple of respondents responded saying it is of O(n). 

Me: I was contended with this answer and said "yes, you are right".

Me: If popping a single element from a stack having n elements takes worst-case time complexity of O(n), then what will the time complexity of popping n elements from a stack having n elements using this MultiPop() function?

Learners: Only one of them answered it is of O(n^2).

Me: In a polarized mode and  with a not so satisfying tone replied "yes, you are right". Then followed by this statement, I proceeded with the student's favorite statement -- that they would like to hear from their students',  "... Any question? Does it make sense? Have you understood?"

Learners: No response.

Me: I understood they are now in a confusion state as I was while preparing for this lecture session. So, my next statement was "... please don't get deceived by looking at the time complexity of  the MultiPop() function that we have arrived at using this asymptotic approach". Don't think the it is very expensive (cost) compared to PUSH and POP operations. I will show you this could be of lesser value when we use Amortized Analysis approach.

Now, it was time to explain them what Amortized Analysis is and what nuances can be captured using this approach compared to traditional Asymptotic Analysis.

After explaining these definitions and differences, I arrived at and showed that the worst case-time complexity for MultiPop() function is just O(n) and not O(n^2). 

... and then repeated the word "don't get deceived ..." and explained them why that sentences was in the lecture slide.

The class ended, I wasn't contended even after the session. 

This dissatisfaction remained until next day morning till 6:00 AM (roughly) when I came across a video lecture of Prof. Erik Demaine and Prof. Charles Leiserson available, on table doubling concept (not the MultiPop funiton), @ https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-13-amortized-algorithms-table-doubling-potential-method/ 

The feeling of contentedness commenced @ 00:9:29, when the prof. said "... So, let's do a quick analysis of this..." The worst analysis shows it is of O(n^2). The same complexity that I derived for the topic MultiPop() functions.  

The analysis ends at 00:10:34 and the prof. then says "Any questions?" @ 00:10:43. 

Another question is shoot @  00:10:53: @ "...Does it make sense?"

That was the most contended and happiest moment to me as it reflected my state when I ask similar question to my student during the class the pervious day. 

@ 00:11:08, one of the student replies to the Prof. saying "... not all of them can be worst case".

I just stopped at this point only to take pride of the moment and feel highly contended for what was thought to my learners during the previous day's online session.

Yes, at times, it takes hours of perpetration, days of perpetrations for certain topics and sometime it become better only when you teach for second time the same topic, maybe in the same week (for another set of students) or the semester coming next.

Conclusion:

Conclusions drawn could be many but here is mine ...

Choosing the right example to explain a scientific or an engineering concept/theory is what it matters.

What matters even more is hitting this target (I call it a luck) in right time for your classroom teaching, to make it more effective.

Dedicated to the following students:

(Shall be updated once the list is ready...)