Commentary

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:"

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:

• https://mathworld.wolfram.com/DigraphSink.html
• https://www.geeksforgeeks.org/number-sink-nodes-graph/

Content

I slowly went through the slides the day after the lecture.

Celebrity Problem (1 exists)

• Celebrity: everyone knows them, they don't know anyone
• By definition, there can be at most one celebrity in a set of people
• All we can ask a person is, "Do you know this person?"

• Solution

  • Base case: $n=1$, person is a celebrity
  • Recursive step: Arbitrarily pick $A, B$ from $S$, a group of $n$ people
  • If $A$ knows $B$, then $A$ cannot be a celebrity, and $B$ might be a celebrity, so perform the algorithm on $S-\{A\}$, a set of $n-1$ people.
  • If $A$ doesn't know $B$, then $B$ cannot be a celebrity, and $A$ might be a celebrity, so perform the algorithm on $S-\{B\}$
  • We can express this as the following recurrence: $T_n = T_{n-1} + 1$ for $n \geq 2$, $T_1 = 0$
  • Rolling out the recurrence, we get $T_n = T_{n-1} + 1 = T_{n-2} + 1 + 1 = 1 + 1 + ... + 1 = n - 1$
  • Therefore, $T_n = n - 1$ and this is an $O(n)$ algorithm.

Celebrity Problem (0 or 1 exists)

• Now we must identify a celebrity or determine that a group has no celebrity

• The previous algorithm fails. Why?

  • Consider a set of people: $A$ and $B$, who both know each other. Neither of them are celebrities. Yet the algorithm will return either $A$ or $B$, when it should return None.
  • Also fails for $A$ and $B$, who both don't know each other

• Solution

  • Same base case
  • If A knows B, then make recursive call on $S - \{A\}$. This could return $B$, some arbitrary person $C$ that's not $B$, or 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.
  • Recurrence: $T_n = T_{n-1} + 3$ for $n \geq 3$, $T_2 = 2$, $T_1 = 0$
  • $T_n = 3n - 4$ for $n \geq 2$, so we (still) have an $O(n)$ algorithm

• Alternative solution: $O(n)$

  • Run the algorithm that assumes a celebrity exists, which always returns some person $C$. Worst case: $n-1$ questions
  • Check if the other $n-1$ people know $C$ and check that $C$ doesn't know those $n-1$ people
  • If all checks pass, return $C$ as celebrity, else return None

Polish National Flag Problem

• Use minimum number of swaps to move all red pegs to left of all the white pegs

• Initial algorithm

  • Search for leftmost white, rightmost red peg. If white to left of red, swap pegs and repeat; else done
  • Analysis (swaps only): In worst case, once we swap we can ignore the two ends, so $T_n = T_{n-2} + 1 = n/2$, where $1$ comes from comparing positions
  • Analysis (swaps + search): Searching for leftmost white, rightmost red pegs each takes $O(n)$ in worst case. $T_n = T_{n-2} + O(n) + O(n) + 1 = T_{n-2} + O(n) = O(n^2)$

• Better algorithm

  • No need to search over and over for leftmost, rightmost pegs
  • Instead, use a left pointer and right pointer, each of which moves $O(n)$ across all searches and swaps
  • Comparisons are $O(n)$ total and swaps are $O(n)$ total, so $O(n)$ algorithm

Dutch National Flag Problem

• Want red, white, blue from left to right
• Left pointer on 1st white, mid pointer, right pointer before 1st blue

• Examine mid pointer, then make a swap and advance the pointers accordingly

  • Mid pointer begins with red: swap items at left and mid pointers, then move left and mid pointers forward
  • White: no swap; advance mid pointer
  • Blue: swap items at mid and right pointers; advance right pointer (but not mid because it's pointing to unknown now)
• Start state: left and mid pointers at start, right pointer at end
• End state: left pointer at first white, mid and right pointers cross at last white
• All pointers move $O(n)$ distance and at most $O(n)$ swaps occur, so the algorithm is $O(n)$

Videos

• The Celebrity Problem | GeeksforGeeks (only the simple version)
• FACEBOOK - FIND THE CELEBRITY (LeetCode)
• The Dutch National Flag Problem (The Quicksort "Band-Aid")