This lecture was a little bit of a shitshow. I followed along in the beginning, started only getting the gist of things when the lecturer introduced the harder celebrity problem, and didn't closely listen to the rest.
I decided I would listen to it like a podcast and be okay with reviewing the slides later, watching YouTube videos explaining the concepts, and going to recitation. But it turns out it's hard to make it through 20 more minutes when you have minimal grounding in what they're talking about now.
Also, I was watching in bed, which is perhaps unsuitable for lectures where I actually have to think a lot.
I've gathered that I should get gud at coming up with recurrence relations and unrolling them into closed expressions. I noticed from the chat that some students were able to do this quickly.
For example, for the first version of the celebrity problem, one of the instructors said in the chat: "We unrolled the recursion:"
$T_n = T_{n-1} + 1 = T_{n-2} + 1 + 1 = ... = 1 + 1 + ... + 1 = n-1$For harder celebrity problem, why -4? TA: "We overestimated by 4. We said 3 checks per layer, but in layer 1 we used 0 and layer 2 we used only 2."
A student also asked whether celebrities can be found as sinks in a digraph, or something. A TA replied: "A celebrity does have to be a sink - but also needs an incoming edge from all other nodes." I think it would be good to explore more of these concepts and applications/implementations:
I slowly went through the slides the day after the lecture.
Solution
The previous algorithm fails. Why?
None
.Solution
None
. If $B$, we ask if $B$ knows $A$ — if yes, then None
; if no, then $B$ is the celebrity. If we get $C$, we recurse again, asking if $C$ and $A$ know each other.Alternative solution: $O(n)$
None
Initial algorithm
Better algorithm
Examine mid pointer, then make a swap and advance the pointers accordingly