← Back to mit.katmh.com

Algorithmic Thinking

· Read 02/18/2021


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

Tn=Tn1+1=Tn2+1+1=...=1+1+...+1=n1T_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.

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=1n=1, person is a celebrity
    • Recursive step: Arbitrarily pick A,BA, B from SS, a group of nn people
    • If AA knows BB, then AA cannot be a celebrity, and BB might be a celebrity, so perform the algorithm on S{A}S-\{A\}, a set of n1n-1 people.
    • If AA doesn't know BB, then BB cannot be a celebrity, and AA might be a celebrity, so perform the algorithm on S{B}S-\{B\}
    • We can express this as the following recurrence: Tn=Tn1+1T_n = T_{n-1} + 1 for n2n \geq 2, T1=0T_1 = 0
    • Rolling out the recurrence, we get Tn=Tn1+1=Tn2+1+1=1+1+...+1=n1T_n = T_{n-1} + 1 = T_{n-2} + 1 + 1 = 1 + 1 + ... + 1 = n - 1
    • Therefore, Tn=n1T_n = n - 1 and this is an O(n)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: AA and BB, who both know each other. Neither of them are celebrities. Yet the algorithm will return either AA or BB, when it should return None.
    • Also fails for AA and BB, who both don't know each other
  • Solution

    • Same base case
    • If A knows B, then make recursive call on S{A}S - \{A\}. This could return BB, some arbitrary person CC that's not BB, or None. If BB, we ask if BB knows AA — if yes, then None; if no, then BB is the celebrity. If we get CC, we recurse again, asking if CC and AA know each other.
    • Recurrence: Tn=Tn1+3T_n = T_{n-1} + 3 for n3n \geq 3, T2=2T_2 = 2, T1=0T_1 = 0
    • Tn=3n4T_n = 3n - 4 for n2n \geq 2, so we (still) have an O(n)O(n) algorithm
  • Alternative solution: O(n)O(n)

    • Run the algorithm that assumes a celebrity exists, which always returns some person CC. Worst case: n1n-1 questions
    • Check if the other n1n-1 people know CC and check that CC doesn't know those n1n-1 people
    • If all checks pass, return CC 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 Tn=Tn2+1=n/2T_n = T_{n-2} + 1 = n/2, where 11 comes from comparing positions
    • Analysis (swaps + search): Searching for leftmost white, rightmost red pegs each takes O(n)O(n) in worst case. Tn=Tn2+O(n)+O(n)+1=Tn2+O(n)=O(n2)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)O(n) across all searches and swaps
    • Comparisons are O(n)O(n) total and swaps are O(n)O(n) total, so O(n)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)O(n) distance and at most O(n)O(n) swaps occur, so the algorithm is O(n)O(n)