Randomized Algorithms

### Analysis of Randomized QuickSort

The Randomized QuickSort sorting algorithm is a foundational randomized algorithm whose randomized analysis is always imperative to absorb and internalize. In this post, we explore the very simplified approach to its analysis with the use of probabilistic techniques rather than a brute-force expected run-time analysis. The procedure and intuition behind

Probability Theory

### Key Probabilistic Concentration Bounds

Especially in the analysis of randomized algorithms, probabilistic bounds play a pivotal role in the proving of probabilistic theorems. This blog aims to be a reference for such key results that will be used in the randomized analyses conducted in upcoming blogs. Foremost, we cover the all-important Markov and Chebyshev

Randomized Algorithms

### Randomized QuickSort

The most prominent randomized algorithm that almost everyone who has taken an algorithms course knows to their heart is the very famous Randomized QuickSort sorting algorithm. Since there are countless resources for this algorithm, I provide this blog to be a foundation for an upcoming post on the detailed analysis

### Measure Theoretic Probability Theory

Recently, I just completed my undergraduate Real Analysis course at UC Santa Cruz, and for the course, we were required to write a paper. I chose to write on this fantastic and pleasantly rigorous intersection of Measure Theory and Probability Theory — in particular, continuous sample spaces. The traditional method

Graph Theory

### Graph Theory Fundamentals

In my previous post (can be found here), we discussed the importance of Graph Theory and how we find it everywhere in the world. In this post, we will explore the fundamental definitions along with examples to cement a foundational understanding of Graph Theory to aid in future posts going

Graph Theory

### Introduction to Graph Theory

My favorite subject in Theoretical Computer Science: Graph Theory. Maybe you think this is a graph: And if you do, then you’d be right, but if you are a student of Mathematics or Computer Science, the term graph probably means something like this: And for this site, we distinguish these

### Reservoir Sampling: Uniform Sampling of Streaming Data

Consider a stream of data that we receive, call them where is the element in the stream. Note that we receive every at the time step and that is then no more in our access once we move on to the next time step. Furthermore, we don’t even know the

Probability Theory

### Introduction to Probability Distributions

There are many methods of introducing structure to random variables in Probability Theory, and traditionally we call this structure a property, and one such property is its distribution. Phrases like “coming from this distribution” or “they distribute as such” or “these variables make this distribution” all refer to this property.

### GraphSort Paper

A few months ago, I constructed this sorting algorithm based on graph data structure and the topological sort feature. In the future, I plan to write some more about the topological sort in an upcoming post, but for those who are interested in the paper, it can be found here

Miscellaneous

### Welcome!

Hi! I am Balaram. Currently, I am a third-year undergraduate student at the University of California, Santa Cruz (UCSC) where I am studying Computer Science and Mathematics. Passionate of many topics in Theoretical Computer Science, I decided to create this blog where I can post things I learn. Hopefully, you