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!
There are n+1 people at a party. They might or might not know each other names. There is one celebrity in the group, and the celebrity does not know anyone by their name. However, all the n people know that celebrity by name. You are given the list of people present at the party. And we can ask only one question from each one of them. “Do you know this name”? How many maximum numbers of questions do you need to ask to identify the actual celebrity?
You have given n-bulbs connected in a circle with a switch for each bulb. The connection is such that if you change the state of anyone bulb may be on or off, it will toggle the state of its adjacent bulbs. All the bulbs are initially switched off. You have to find the number of steps such that all the bulbs are switched on.
You’ve got someone working for you for seven days and a gold bar to pay him. The gold bar is segmented into seven connected pieces. You must give them a piece of gold at the end of every day. What is the fewest number of cuts to the bar of gold that will allow you to pay him 1/7th each day?
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.