Blogs

General Introduction to Algorithms and Theory of Computation — This website presumes you have an undergraduate or high-school level understanding of computers and data structures. Data structures These are just ways to structure data. There are primitive data types in every language, but they too are built off on other data structures. Something as bare-metal as a system reading a CD depends on data structures as. (Source expertsmind.com) As we go up the stack, we meet data structures at every level.
The many kind of Sorts, oh and Loop Invariants — Ref. CLRS book, 5.3 Randomized algorithms, Chapter 7 Quicksort, 8.4 Bucket sort 1. Randomized Algorithms Randomized algorithms are algorithms that incorporate randomness into their logic. The randomness allows the algorithm to make random choices during execution, rather than relying solely on the deterministic input. This provides several advantages: Randomized algorithms can have good expected performance across all inputs, rather than relying on assumptions about the input distribution. They can be useful when little is known about the properties or distribution of the input data.
Asymptotic Notations — Big O Notation [$ O $]: This notation describes an upper bound on the growth rate of a function. It gives a worst-case scenario for the growth rate of an algorithm. Mathematically, we say that [$ f(x) = O(g(x)) $] if there exist constants [$ c > 0 $] and [$ x_0 > 0 $] such that [$ f(x) \leq c \cdot g(x) $] for all [$ x > x_0 $].
Gale Shapely Algorithm — Gale-Shapley Algorithm Input Two sets of agents: Men and Women Preference lists for each agent Men’s preferences: men_preferences Women’s preferences: women_preferences Output Stable matching: matching Initialize Initialize an empty matching matching Create an empty list men_proposals to keep track of men’s proposals While there are unengaged men Select an unengaged man m from Men Find the first woman w in m’s preference list whom m has not proposed to Mark m as having proposed to w If w is unengaged Engage m and w in a couple and add them to matching Else, if w is already engaged to m' If w prefers m to m' Break the engagement between m' and w Engage m and w in a couple and add them to matching Mark m' as unengaged Else, w rejects m End Return the stable matching matching Complexity Analysis To prove that the Gale-Shapley algorithm has a time complexity of O(n^2), where ’n’ is the number of elements in each of the two sets being matched, we will analyze the worst-case scenario for both the proposal and acceptance phases.
Priority Queues — A priority queue is a data structure that maintains a collection of elements, each associated with a priority or key, and provides efficient access to the element with the highest (or lowest) priority. It allows for the insertion and removal of elements based on their priorities, making it a fundamental tool for tasks where items need to be processed in order of importance, such as scheduling tasks, graph algorithms, and simulation.
Shannon Entropy: Intuition, Proof and Applications — Ref: A mathematical theory of communication Claude Shannon formulated the mathematical expression for entropy, which is now known as Shannon entropy, through a systematic development based on key principles from probability theory and information theory. Here’s a step-by-step explanation of how he arrived at the formula: Basic Concepts: Shannon started with the idea of information and uncertainty. He wanted a measure of the amount of information in a message or a random variable.