Writing Challenge Day 8: Divide and Conquer

I've been writing every day for the last week, and am quite anxious at the thought that I haven’t even completed 25% of my 30-day writing challenge. I’m struggling to think about future posts and get a gigantic brain freeze attempting to do so, like eating all of Antarctica. I remember the wise words of my long-distance running coach: a marathon is a succession of 5-mile runs, and the last one is surprisingly shorter. Plot twist: I have never run a marathon, but did get injured trying. I followed a preparation schedule tailored to achieving a sub-3-hour finishing time, without the fitness to go with it. Hopefully, writing will be a less risky activity, but who knows? Brain overheating and finger fatigue: There are a lot of frightening outcomes to this challenge, and it's too early to list them out now. The only way to keep going is to take it day by day. Divide and conquer. The concept exists in politics and sociology to empower the sovereign to control subjects, populations, or factions of different interests who collectively might be able to oppose its rule. Sadly, I'm more in a position to talk about its application in algorithms from basic array ordering to fancy Fast Fourier Transformation (FFT) implementation. "You must be fun at parties".

I might know how to write a single blog post (or not - I’ll let the readers be the judge of that), but I have absolutely no clue how to go about writing 30. Conversely, all programming languages have elementary operators to compare numbers < > , but can't natively sort an array. Of course, you could use a sorted -like function in any high-level language, but it would be calling a sorting algorithm under the hood. The merge sort divides the array into its most atomic form: an array of one element. Then, it conquers (i.e., solves the problem for each array). In that case, it's easy because an array of one element is a sorted array by definition. Finally, it combines all sorted arrays to obtain the final result. I will not spend more time on the topic because there are gigabytes of great resources online, and chat-GPT4o would be a far greater teacher than me.

All divide-and-conquer algorithms can be generalized under the following form:

procedure p(input x of size n):
    if n < some constant k:
        Solve x directly without recursion
    else:
        Create a subproblems of x, each having size n/b
        Call procedure p recursively on each subproblem
        Combine the results from the subproblems

The Master Theorem classifies the algorithms following this design paradigm based on how complicated it is to create/recombine subproblems compared to solving them and provides an asymptotic analysis for each category.

I'm currently reading all Vitalik’s articles on Zero-Knowledge proofs (ZKPs). He is a fount of knowledge, and I believe Vitalik's work on education equals his contribution to Ethereum in terms of usefulness to humankind. As I mentioned in Day 1 of this series, my background is in computer science more than advanced mathematics. One would argue that computer “science” isn’t a real science and neither is anything else that needs the word “science” appended to it. Cleaving tweet. Still, Vitalik makes it possible to grasp complex concepts with relatively little mathematical background. He always starts from the beginning or points the reader to the appropriate resource. It's the best place on the internet to learn advanced crypto. Right, but why am I talking about ZKPs now? Because I have an intense fear of missing out (FOMO) that I can't shake off. It's been THE big thing in crypto for a few years and will likely enable privacy-preserving KYC applications and solve Ethereum scaling, amongst other problems. Easy. The math behind them is fascinating, and their domain of applicability is unbound. Fast Fourier Transform (FFTs) algorithms play a big role in proof generation, allowing the implementation of optimized polynomial multiplication required to transform the "prover's statement" (i.e., computational problem) into a Quadratic Arithmetic Program (QAP). I will surely not do better than Vitalik (again) in explaining them, but I love that most common implementations of FFTs are part of the divide-and-conquer big family.
And they belong to the same Master Theorem category as the Merge Sort.

Is the world running on a handful of fundamental meta-concepts? We'll answer that question in the following post (just kidding!)