Important Math Topics for Data Structures and Algorithms
Just like programming, math is one of the core parts of learning data structures and algorithms. We mainly use math to analyse efficiency of various algorithms. But sometimes, the problem itself contains mathematical property or requires some mathematical insight to find a solution.
So learning math is crucial for mastering algorithms and data structures. The critical question is: What type of math or mathematical thinking is essential for DSA? Here is a comprehensive list of topics:
Summation formula and properties of various series: Arithmetic series, Geometric series, Infinite geometric series, Harmonic series, Sum of squares and cubes, Telescopic series, Finding nth terms of different series, etc.
The idea of various proofs: Proof by contradiction, Proof by mathematical induction, Proof by logical deduction, Proof by contraposition, etc.
Properties and operations of matrices: Matrices addition, Matrices subtraction, Matrices multiplication, Transpose, Inverse, Types of matrices, Determinant of a matrix, Solving systems of linear equations using matrices, etc.
Analysis of recursion: Recurrence relation of various recursive functions, Substitution method, Recursion tree method, Master theorem
Analysis of various loop patterns: Single loop patterns, Two nested loop patterns, Three nested loop patterns, etc.
Combinatorics: Basic principle of counting, Permutations of sets, Combinations of sets, Permutations of multisets, Combinations of multisets, Decision problem, Exhaustive search problem, Optimization problem, The rule of product, The rule of sum, Permutations with repetition, Combinations with repetition, Pascal Triangle, Principle of inclusion-exclusion, Piegon hole principle, Catalan number, etc.
Properties of numbers and numbers theory: Various representations of numbers (Binary, decimal, hexadecimal, etc.), properties of natural and prime numbers, LCM, GCD, Square root, Factorial, Prime factorization, Primality test, Rule of divisibility, Properties of Fibonacci numbers, Modular arithmetic, Chinese remainder theorem, Fermat's theorem, etc.
Basic probability theory: Random Variables, Bayes’ Rule, Analysis of randomized algorithms, Conditional probability, Independence, Conditional independence, etc.
Bit manipulation, Operators and their various use cases: Bitwise AND, Bitwise OR, Bitwise NOT, Bitwise XOR, Left shift, Right shift, Bit Masking, etc.
Mathematical properties of various graph types: Directed graph, undirected graph, sparse graph, dense graph, bipartite graph, Directed acyclic graph, cycle, Connectivity, degree, path, subpath, Connected components, Properties of BFS and DFS, Graph colouring, etc.
Mathematical properties of various trees: Full binary tree, Complete binary tree, Perfect binary tree, Height balanced tree, BST property, Heap property, Segment tree, Trie, Decision tree, Fenwick tree, etc.
Other important concepts: Asymptotic notations, properties of big-O, Logarithm and exponential fundamentals, Basic set theory, etc.
We are planning to write a separate blog on each topic later. In the meantime, we are looking forward to your suggestions and critical feedback. Enjoy mathematics!
More blogs to explore
The summation formulas are used to calculate the sum of the sequence. In this blog, we have discussed the visual proofs: the sum of numbers from 1 to n (arithmetic series), the sum of infinite geometric series, the sum of squares of numbers from 1 to n, etc.
A group of four people, who have one torch, need to cross a bridge at night. A maximum of two people can cross the bridge at one time, and any party that crosses (either one or two people) must have the torch with them. The torch must be walked back and forth and cannot be thrown. Person A takes 1 minute to cross the bridge, person B takes 2 minutes, person C takes 5 minutes, and person D takes 10 minutes. A pair must walk together at the rate of the slower person’s pace. Find the fastest way they can accomplish this task.