I took the course Randomized algorithms in Fall 2020, offered by Professor Kent Quanrud. This blog post contains an overview of topics I learnt in the course.

Randomized Algorithms(CS590-RA) is touted to be one of the toughest courses(in terms of content) offered in Purdue’s CS department. The course needs Algorithms:Design and Analysis (CS58000) as a prerequisite and also needs expertise with mathematical machinery such as Probability and Linear Algebra. This course was the most influential course I took in a long time. The concepts I learnt in this course changed the way I think about problem solving and designing algorithms for the same. The course is divided into 2 parts: The first half is about using randomization to design Approximation algorithms for solving standard conceptual problems like Graph Min. Cuts with higher efficiency and practicality. The second half of the course was based on understanding random walks and applying them to design solutions for various problems.

Learnings from the course

Approximation is not that bad

The beauty of the concept of absolute zero is the fact that it is impossible to achieve. Zero is a concept that exists only in theory. For example, think about drawing 2 line segments of EQUAL length. Can we do this? The maximum precision we can achieve when measuring things is in the order of femto meters (10^(-15)), which is still infinity times greater than zero. However, the mathematical construct of zero allows us to derive many proofs and concepts in mathematics. Considering that zero is practically unachievable, don’t we undergo a lot of stress designing algorithms that solve a given problem EXACTLY?

Consider 2 algorithms A1 and A2 which solve a fundamental Computer Science problem - say Min. Cut of a graph G. A1 solves the problem with 100% accuracy while taking time X and occupying space Y. A2 solves the problem with 99.9999% accuracy while taking time X/100 and occupying space Y/100. What approach is preferrable in terms of practicality? Is it worth spending 100 times more memory and time for the 0.0001% accuracy? The course presents us techniques which make use of randomization to make such gains.

Approximation through Randomization

Randomization techniques such as random sampling and probabilistic sampling are highly effective in achieving polynomial probabilistic bounds. Certain beautiful concepts like Universal Hash functions, HyperLogLog and Gaussian sampling based approximations were taught in the course. We moved on to a concept called LP Duality, which I think is one of the most intuitive mathematical concepts, yet extremely hard to prove. According to me, the approximation techniques based on LP Duals is one of the most challenging lectures in the course.

Moving on to Random Walks

The second half of the course was about random walks and their applications. Given a map and the deterministic explorative tendencies of a human, the idea of walking randomly around a graph itself sounds very absurd. However, the mathematics supporting the concept completely blew my mind away. I learnt about stationary distributions, the analog with respect to electrical networks, expander graphs and deterministic connectivity. There is a lecture which talks about the Zig-Zag product, following which I wondered about the limits of human imagination. I mean, we all do have these moments right? When we think how the hell can someone get that idea? The course has many more such joyful moments where I just said to myself that I am grateful to possess the consciousness which can perceive and understand these concepts.

Conclusion

The course demands a lot of effort with 2 homeworks every week and a lot of brainstorming and head-banging, but I say that every minute of my time I spent on the course was worth it. I will probably reap the benefits of this knowledge for an indefinite amount of time. A huge shoutout to Professor Kent Quanrud for teaching such an amazing course!