Getting Started

INTRODUCTION TO PROGRAMMING LANGUAGES:

A program is a set of instructions that tells a computer what to do in order to come up with a solution to a particular problem. Programs are written using a programming language.A programming language is a formal language designed to communicate instructions to a computer. There are two major types of programming languages: low-level languages and high-level languages.

TYPES OF LANGUAGES:

Low-Level Languages : Low-level languages are referred to as 'low' because they are very close to how different hardware elements of a computer actually communicate with each other. Low-level languages are machine oriented and require extensive knowledge of computer hardware and its configuration. There are two categories of low-level languages: machine language and assembly language.

Machine language : or machine code, is the only language that is directly understood by the computer, and it does not need to be translated. All instructions use binary notation and are written as a string of 1s and 0s. A program instruction in machine language may look something like this:

However, binary notation is very difficult for humans to understand. This is where assembly languages come in.

An assembly language : is the first step to improve programming structure and make machine language more readable by humans. An assembly language consists of a set of symbols and letters. A translator is required to translate the assembly language to machine language called the 'assembler.' While easier than machine code, assembly languages are still pretty difficult to understand. This is why high-level languages have been developed.

High-Level Languages : A high-level language is a programming language that uses English and mathematical symbols, like +, -, % and many others, in its instructions. When using the term 'programming languages,' most people are actually referring to high-level languages. High-level languages are the languages most often used by programmers to write programs. Examples of high-level languages are C++, Fortran, Java and Python. Learning a high-level language is not unlike learning another human language - you need to learn vocabulary and grammar so you can make sentences. To learn a programming language, you need to learn commands, syntax and logic, which correspond closely to vocabulary and grammar. The code of most high-level languages is portable and the same code can run on different hardware without modification. Both machine code and assembly languages are hardware specific which means that the machine code used to run a program on one specific computer needs to be modified to run on another computer. A high-level language cannot be understood directly by a computer, and it needs to be translated into machine code. There are two ways to do this, and they are related to how the program is executed: a high-level language can be compiled or interpreted.

COMPILER VS INTERPRETER

A compiler is a computer program that translates a program written in a high-level language to the machine language of a computer.
The high-level program is referred to as 'the source code.' The compiler is used to translate source code into machine code or compiled code. This does not yet use any of the input data. When the compiled code is executed, referred to as 'running the program,' the program processes the input data to produce the desired output.
An interpreter is a computer program that directly executes instructions written in a programming language, without requiring them previously to have been compiled into a machine language program.

HOW TO START WRITING PROGRAMS?

Algorithm:
Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language.
Qualities of a good algorithm
1. Input and output should be defined precisely.
2. Each step in the algorithm should be clear and unambiguous.
3. An algorithm shouldn’t include computer codes. Instead it should be written in such a way that it can be used in different programming languages. Good, logical programming is developed through good pre-code planning and organization. This is assisted by the use of pseudocode and program flowcharts.

Flowcharts:
Flowcharts are written with program flow from the top of a page to the bottom. Each command is placed in a box of the appropriate shape, and arrows are used to direct program flow.

4.This is what we use when our program has to make a decision. This is the only block that has more than one exit arrow. The rhombus symbol has one(or several) entrance points and exactly two outputs.

5.Junction flow chart symbol : You can connect two arrows with a junction

Here are examples of a short algorithm, using each flowcharts

VARIABLES

A variable is a container (storage area) used to hold data.
Each variable should be given a unique name (identifier).
int a=2;

Here a is the variable name that holds the integer value 2.
The value of a can be changed, hence the name variable.
There are certain rules for naming a variable in C++
1. Can only have alphabets, numbers and underscore.
2. Cannot begin with a number.
3. Cannot begin with an uppercase character.
4. Cannot be a keyword defined in C++ language (like int is a keyword).

FUNDAMENTAL DATATYPES IN C++ :

Data types are declarations for variables. This determines the type and size of
data associated with variables which is essential to know since different data
types occupy different size of memory.

2. float and double:
● Used to store floating-point numbers (decimals and exponentials)
● Size of float is 4 bytes and size of double is 8 bytes.
● Float is used to store upto 7 decimal digits whereas double is used to store upto 15 decimal digits.
Eg. float pi = 3.14
double distance = 24E8 // 24 x 108

3. char:
● This data type is used to store characters.
● It occupies 1 byte in memory.
● Characters in C++ are enclosed inside single quotes ͚ ͚.
● ASCII code is used to store characters in memory.
Eg͘ char ch с ͚a͖͛

4. bool
● This data type has only 2 values ʹ true and false.
● It occupies 1 byte in memory.
● True is represented as 1 and false as 0.

Eg. bool flag = false

C++ TYPE MODIFIERS

Type modifiers are used to modify the fundamental data types.

DERIVED DATATYPES:

These are the data types that are derived from fundamental (or built-in) data
types. For example, arrays, pointers, function, reference.

USER-DEFINED DATATYPES:
These are the data types that are defined by user itself.For example, class, structure, union, enumeration, etc.

1. Comments
The two slash(//) signs are used to add comments in a program. It does not have any effect on the behavior or outcome of the program. It is used to give a description of the program you’re writing.

2. #include<iostream>
#include is the pre-processor directive that is used to include files in our program. Here we are including the iostream standard file which is necessary for the declarations of basic standard input/output library in C++.

3. Using namespace std
All elements of the standard C++ library are declared within namespace. Here we are using std namespace.

4. int main()
The execution of any C++ program starts with the main function, hence it is necessary to have a main function in your program. ‘int’ is the return value of this function. (We will be studying about functions in more detail later).

5. {}
The curly brackets are used to indicate the starting and ending point of any function. Every opening bracket should have a corresponding closing Bracket.

6. Cout<< ”Hello World!\n”;
This is a C++ statement. cout represents the standard output stream in C++. It is declared in the iostream standard file within the std namespace. The text between quotations will be printed on the screen. \n will not be printed, it is used to add line break. Each statement in C++ ends with a semicolon (;)

7. return 0;
return signifies the end of a function. Here the function is main, so when we hit return 0, it exits the program. We are returning 0 because we mentioned the return type of main function as integer (int main). A zero indicates that everything went fine and a one indicates that something has gone wrong.

                                                        
// Hello world program in C++
#include<iostream>
using namespace std;
int main()
{
      cout << "Hello World!\n";
      return 0;
}
                                                    

Operator Operation Example

+ Adds two operands A+B = 15
- Subtracts right operand from left operand B-A = 5
* Multiplies two operands A*B = 50
/ Divides left operand by right operand B/A = 2
% Finds the remainder after integer division B%A = 0

Pre-incrementer : It increments the value of the operand instantly.

Post-incrementer : It stores the current value of the operand temporarily and only after that statement is completed, the value of the operand is incremented.

Pre-decrementer : It decrements the value of the operand instantly.

Post-decrementer : It stores the current value of the operand temporarily and only after that statement is completed, the value of the operand is decremented.

                                                        
int a=10;
int b;
b = a++;
cout<<a<<" "<<b<<endl;
Output : 11 10
int a=10;
int b;
b = ++a;
cout<<a<<" "<<b<<endl;
Output : 11 11
                                                    

2. Relational Operators

Relational operators define the relation between 2 entities. They give a boolean value as result i.e true or false.

Suppose : A=5 and B=10

Operator Operation Example
== Gives true if two operands are equal A==B is not true
!= Gives true if two operands are not equal A!=B is true
> Gives true if left operand is more than right operand A>B is not true
< Gives true if left operand is less than right operand A<B is true
>= Gives true if left operand is more than right operand or equal to it A>=B is not true
<= Gives true if left operand is more than right operand or equal to it A<=B is true

3. Logical Operators

Logical operators are used to connect multiple expressions or conditions together.
We have 3 basic logical operators.

Suppose : A=0 and B=1

&& AND operator. Gives true if both operands are non-zero.(A && B) is false
|| OR operator. Gives true if atleast one of the two operands are non-zero.(A || B) is true
! NOT operator. Reverse the logical state of operand !A is true

Example -

If we need to check whether a number is divisible by both 2 and 3, we will use AND operator
(num%2==0) && num(num%3==0)
If this expression gives true value then that means that num is divisible by both 2 and 3.

(num%2==0) || (num%3==0)
If this expression gives true value then that means that num is divisible by 2 or 3 or both.

Suppose : A=5(0101) and B=6(0110)

& Binary AND. Copies a bit to the result if it exists in both operands.
0101 & 0110 => 0100

| Binary OR. Copies a bit if it exists in either operand.
0101 | 0110 => 0111

^ Binary XOR. Copies the bit if it is set in one operand but not both.
0101^ 0110 => 0011

~ Binary Ones Complement. Flips the bit.
~0101 =>1010

<< Binary Left Shift. Shifts left by the number of places specified by the right operand.
4 (0100)
4<<1=1000 = 8

>> Binary Right Shift. Shifts right by the number of places specified by the right operand.
4>>1=0010 = 2

If shift operator is applied on a number N then,
x N<<a will give a result N*2^a
x N>>a will give a result N/2^a

According to inclusion-exclusion principle, to count unique ways for doing a task, the number of ways to do it in one way (n1) and number of ways to do it in some other way (n2) should be added, and the number of ways that are common to both set should be subtracted.

For two finite sets A1 and A2
| A1 ∪ A2 |= |A1 |+ | A2| – |A1 ∩ A2|

Have a look at these examples:

Example 1 :

How many numbers between 10 and 100, including both, have the first digit as 3 and the last digit as 5?

Solution :

The numbers with 1st digit as 3 are from 30,31,32.…..39. So, the number of numbers with 1st digit as 3 is equal to 10. The numbers with last digit as 5 are 15,25,35…..95. Hence, the number of numbers with last digit as 5 is equal to 9.
So, is 10 + 9 = 19 the answer? No.
Because, we haven’t subtracted the common part between the two sets. We need to find the numbers who have both the first digit as 3 and the last digit as 5. Here, there’s only 1 such number, i.e. 35.
Therefore, the final answer = 10 + 9 - 1 = 18.

Example 2 :

How many numbers between 1 and 100, including both, are divisible by 3 and 7?

Solution :

Number of numbers divisible by 3 = 100 / 3 = 33.
Number of numbers divisible by 7 = 100 / 7 = 14.

Number of numbers divisible by 3 and 7 = 100 / (3 * 7) = 100 / 21 = 4.

Hence, number of numbers divisible by 3 or 7 = 33 + 14 - 4 = 43.

If there are more than two sets, the following general formula is applicable:

For a given set A of n sets A_1,A_2,....A_n, let S_nbe the number of ways to do the task :

Here, we can observe that odd number of terms are added while even number of terms are subtracted.
Actually, each subset of is considered exactly once in the formula, thus the formula for a set of n sets has 2^n components.

Problem :

Given two positive integers n and r . Count the number of integers in the interval [1,r] that are relatively prime to n (their GCD is 1).

Solution:

Let’s first find the number of integers between 1 and r that are not relatively prime with n ( i.e they share atleast one prime factor with n ).

So, the first step is to find the prime factors of n. Let the prime factors of n be p_i(i = 1...k )
How many numbers in the interval [1,r] are divisible by p_i? The answer is :

However, if we simply sum these numbers, some numbers will be summarized several times (those that share multiple pias their factors). Therefore, it is necessary to use the inclusion-exclusion principle.

We will iterate over all 2ksubsets of pis, calculate their product and add or subtract the number of multiples of their product.
Below is the C++ implementation of the above idea:

                                                        
// CPP program to count the
// number of integers in range
// 1-r that are relatively
// prime to n
#include <bits/stdc++.h>
using namespace std;
 
// function to count the
// number of integers in range
// 1-r that are relatively
// prime to n
int count (int n, int r) {

    vector<int> p; // vector to store prime factors of n

   
    // prime factorisation of n
    for (int i=2; i*i<=n; ++i)
        if (n % i == 0) {
            p.push_back (i);
            while (n % i == 0)
                n /= i;
        }
    if (n > 1)
        p.push_back (n);

    int sum = 0;
    for (int mask=1; mask<(1<<p.size()); ++mask) {
        int mult = 1,
            bits = 0;
        for (int i=0; i<(int)p.size(); ++i)
            // Check if ith bit is set in mask
            if (mask & (1<<i)) {
                ++bits;
                mult *= p[i];
            }

        int cur = r / mult;
        if (bits % 2 == 1)
            sum += cur; // if odd number of prime factors are selected
        else
            sum -= cur; // if even number of prime factors are selected

    }

    return r - sum;
}

// Driver Code
int main()
{
    int n=30;
    int r=30;
    cout << count(n, r);
    return 0;
}

//OUTPUT : 22
                                                    

As we all know by now, Probability is how likely something is about to happen.

Let’s denote an event by A, for which we need to find the probability of how likely the event is going to happen. We denote this by using P(A).
And mathematically, P(A) = Number of outcomes where A happens / Total outcomes.

Basic probability calculations

Complement of A : Complement of an event A means not A. Probability of complement event of A means the probability of all the outcomes in sample space other than the ones in A.

P(Ac) = 1 − P(A).

Union and Intersection : The probability of intersection of two events A and B is P(A∩B). When event A occurs in union with event B then the probability together is defined as P(A∪B) = P(A) + P(B) − P(A∩B) which is also known as the addition rule of probability.

Mutually exclusive : Any two events are mutually exclusive when they have non-overlapping outcomes i.e. if A and B are two mutually exclusive events then, P(A∩B) = 0. From the addition rule of probability

P(A∪B) = P(A) + P(B)

as A and B are disjoint or mutually exclusive events.

Independent : Any two events are independent of each other if one has zero effect on the other i.e. the occurrence of one event does not affect the occurrence of the other. If A and B are two independent events then, P(A∩B) = P(A) ∗ P(B).

Conditional Probability
The conditional probability of an event B is the probability that the event will occur given the knowledge that an event A has already occurred. This probability is written P(B|A), notation for the probability of B given A. In the case where events A and B are independent (where event A has no effect on the probability of event B), the conditional probability of event B given event A is simply the probability of event B, that is P(B).

If events A and B are not independent, then the probability of the intersection of A and B (the probability that both events occur) is defined by P(A and B) = P(A)P(B|A).

From this definition, the conditional probability P(B|A) is easily obtained by dividing by P(A):

Binomial Distribution

To get started first we need to learn about something called Bernoulli Trial. Bernoulli Trial is a random experiment with only two possible, mutually exclusive outcomes. And each Bernoulli Trial is independent of the other.

To better understand stuff, let’s see an example.
Suppose we toss a fair coin three times. And we need to find the probability of two heads in all the possible outcomes.

Now, we can see that the probability of getting heads is ½, and tails is also ½, for a fair coin. And here all the tosses of the coin are independent to each other. So, we may say that the single tossing of the coin is a Bernoulli Trial, with the two possible outcomes of heads and tails. Let p denote the probability of getting heads in a fair coin toss. And the other possibility of getting tails is denoted by q. We can see that, p = ½ and q = ½.

The coin is tossed three times, so we have to select two events out of three, where heads will occur. And the total events are three. So, the number of ways to select them is 3C2. And the so can denote the total probability as = 3C2 p2q

Now let’s generalise the approach to problems like these involving Bernoulli Trials.
We saw that the Bernoulli Trial involves two mutually exclusive outcomes. Now for convenience they are often labelled as, “success” and “failure”. The binomial distribution is used to obtain the probability of observing x successes in N trials, with the probability of success on a single trial denoted by p. The binomial distribution assumes that p is fixed for all trials.

GCD(Greatest Common Divisor) or HCF(Highest Common Factor) of 2 integers a and b refers to the greatest possible integer which divides both a and b.
GCD plays a very important part in solving several types of problems(both easy and difficult) which makes it a very important topic for Competitive Programming.

Algorithms to find GCD:

Brute Force Approach:
An approach is possible to start from the smaller number and iterate to 1. As soon as we find a number that divides both a and b, we can return it as the result.

Time complexity: O(min(a,b))
Space complexity: O(1)

Euclidean Algorithm:
The Euclidean Algorithm for calculating the GCD of two numbers builds on several facts:
If we subtract the smaller number from the larger number then the GCD is not changed.
i.e,gcd(a,b)=gcd(b,a-b)[considering a>=b]

If a is 0 and b is non-zero, the GCD is by definition b(or vice versa). If both are zero, then the GCD is undefined; but we can consider it to be zero, which gives us a very basic rule:
If one of the numbers is 0, then the GCD is the other number.

We can build upon these facts and further define GCD as(since the algorithm terminates as soon as one of the numbers become 0):
gcd(a,b)=gcd(b,a%b)

L.C.M:

LCM (Least Common Multiple) of 2 integers u and v refers to the smallest possible integer which is divisible by both u and v.

Important Properties:

1. gcd(a,b)=gcd(b,a)

2. gcd(a,b,c)=gcd(a,gcd(b,c))=gcd(gcd(a,b),c)=gcd(b,gcd(a,c))

3. Depending on the parity of a and b, the following cases may arise:

(a). If both the numbers are even, then we can say,

gcd(2*a,2*b)=2*gcd(a,b)

(b). If only one of the numbers is even, while the other is odd,

gcd(2*a,b)=gcd(a,b) [b is odd]

(c). If both numbers are odd,

gcd(a,b)=gcd(b,a−b) [provided a>=b]

Extended Euclidean Algorithm:

The Extended Euclidean Algorithm allows us to find a linear combination of a and b which results in the GCD to a and b.
i,e, a*x+b*y=gcd(a,b) [x,y are integer coefficients]

e.g, a=15, b=35

Therefore,
gcd(a,b)=5
x=-2
y=1

Since, 15*(-2)+35*1=5

Another important topic, Linear Diophantine Equations, will also build upon this algorithm.

Algorithm:

The key factor in understanding the algorithm is figuring out how the coefficients (x,y) change during the change from the function call of gcd(a,b) to gcd(b,a%b) [i.e, following the recursive implementation].

Let us assume we have the coefficients (x1,y1) for (b,a%b);

∴ b*x1+(a%b)*y1=gcd(b,a%b)........(i)

We finally want to find the pair (x,y) for (a,b);

∴ a*x+b*y=gcd(a,b)........(ii)

Again, we know from the rules of modulus:

a%b=a-floor(a/b)*b........(iii)

[floor() function represents the mathematical floor function]

Therefore from equations (i),(ii) and (iii), we can say:

x=y1

y=x1-y1*floor(a/b)

                                                        
//Recursive implementation
int extended_euclid_recursive(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int gcd = extended_euclid_recursive(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return gcd;
}

//Iterative implementation
int extended_euclid_iterative(int a, int b, int& x, int& y) {
    x = 1, y = 0;
    int x1 = 0, y1 = 1, a1 = a, b1 = b;
    while (b1) {
        int q = a1 / b1;
        tie(x, x1) = make_tuple(x1, x - q * x1);
        tie(y, y1) = make_tuple(y1, y - q * y1);
        tie(a1, b1) = make_tuple(b1, a1 - q * b1);
    }
    return a1;
}
                                                    

What is Sieve:

Sieve of Eratosthenes is an algorithm for finding all the prime numbers in a segment in range 1 to n in
0(n log(log n)) operations

Native approach:

USING SIEVE:

In the sieve algorithm, we create an integer array of length n+1(for numbers from 1 to n) and mark all of them as prime. Then we iterate from 2 till square root of n. We mark all proper multiples of 2 (since 2 is the smallest prime number) as composite. A proper multiple of a number num is a number greater than num and divisible by num. Then we find the next number that hasn't been marked as composite, in this case, it is 3. This means 3 is prime, and we mark all proper multiples of 3 as composite and we continue this procedure.

For n=50, this is the list of primes we are going to get

                                                        
#include <bits/stdc++.h> 
using namespace std; 
int main() 
{ 
	int n;
	cin>>n;
	vector<int> prime(n+1, 1);
	prime[0] = prime[1] = 0;
	for (int i = 2; i * i <= n; i++) {
    	if (prime[i]==1) {
        	for (int j = i * i; j <= n; j += i)
            	prime[j] = 0;
    	}
	}
	for(int i=1;i<=n;i++)if(prime[i]==1)cout<<i<<endl;
}
                                                    

The time complexity of the above code is 0(n*log(log n))

In the above code, we can reduce the number of operations performed by the algorithm by stopping checking for even numbers as all even numbers (except 2) are composite numbers for we can check for odd numbers only.

                                                        
#include <bits/stdc++.h> 
using namespace std; 
int main() 
{ 
	int n;
	cin>>n;
	vector<int> prime(n+1, 1);
	prime[0] = prime[1] = 0;
	for (int i = 3; i * i <= n; i+=2) {
    	if (prime[i]==1) {
        	for (int j = i * i; j <= n; j += i)
            	prime[j] = 0;
    	}
	}
	if(n>=2)
	cout<<2<<endl;//as 2 is a prime number
	for(int i=3;i<=n;i+=2)if(prime[i]==1)cout<<i<<endl;
}
                                                    

                                                        
#include<bits/stdc++.h>
using namespace std;
vector<int>ar(100000,0);
void sieve(int maxn)
{
	for(int i=0;i<=maxn;i++)ar[i]=i;
	for(int i=2;i*i<=maxn;i++)
	{
		if(ar[i]==i)
		{
			for(int j=i*i;j<=maxn;j+=i)
				ar[j]=i;}
	}
}
int main()
{	sieve(100000);
	int t;
	cin>>t;
	while(t--)
	{	int n;
		cin>>n;
		while(n>=1)
		{	cout<<ar[n]<<endl;
			if(n==1)break;
			n/=ar[n];
		}
	}
}
                                                    

SEGMENTED SIEVE

The idea of a segmented sieve is to divide the range [0..n-1] in different segments and compute primes in all segments one by one. This algorithm first uses Simple Sieve to find primes smaller than or equal to √(n). Below are steps used in Segmented Sieve.

1. Use Simple Sieve to find all primes up to the square root of ‘n’ and store these primes in an array “prime[]”. Store the found primes in an array ‘prime[]’.

2. we need to find all prime numbers in a range [L, R] of small size (e.g., R−L+1≈1e7), where R can be very large (e.g.10^12)

To solve such a problem, we can use the idea of the Segmented sieve. We pre-generate all prime numbers up to sqrt(R) and use those primes to mark all composite numbers in the segment [L, R].

                                                        
vector<bool> segmentedSieve(long long L, long long R) { // generate all primes up to sqrt(R) 
long long lim = sqrt(R); 
vector<bool> mark(lim + 1, false); 
vector<long long> primes; 
for (long long i = 2; i <= lim; ++i) { 
if (!mark[i]) { 
primes.emplace_back(i); 
for (long long j = i * i; j <= lim; j += i) 
mark[j] = true; 
} 
} 
vector<bool> isPrime(R - L + 1, true); 
for (long long i : primes) 
for (long long j = max(i * i, (L + i - 1) / i * i); j <= R; j += i) 
isPrime[j - L] = false; 
if (L == 1) 
isPrime[0] = false; 
return isPrime; 
}

//Time complexity of this approach is O((R-L+1)loglog(R)+sqrt(R)loglog(sqrt(R)))
                                                    

Linear Diophantine Equations

Introduction:

A General Diophantine equation is a polynomial equation, having two(or more) integral variables i.e. if a solution of the equation exists, it possesses integral values.
A linear Diophantine equation is a Diophantine equation of degree 1 i.e. each integral variable in the equation is either of degree 0 or degree 1.

General form:

A Linear Diophantine Equation(in two variables) is an equation of the general form:

ax + by = c

Where a,b,c are integral constants and x,y are integral variables.

Homogeneous Linear Diophantine equation:

A Homogeneous Linear Diophantine Equation(in two variables) is an equation of the general form:

ax + by = 0

Where a,b are integral constants and x,y are the integral variables.
By looking at the equation we can easily observe that x=0 and y=0 is a solution to the equation. This is called the Trivial solution.
Though more solutions can exist for the same.

Condition for the solution to exist:

For a linear diophantine equation, the integral solution exists if and only if:

c%gcd(a,b)=0

i.e. c must be divisible by the greatest common divisor of a and b. This is because

Let, a = gcd(a,b).A, where A is an integral divisor of a. Similarly, b = gcd(a,b).B.
Therefore the Linear Diophantine equation can be written as:

gcd(a,b).A + gcd(a,b).B = c
gcd(a,b).(A + B) = c

This means that c must be a multiple of gcd(a,b).
For the Homogeneous Linear Diophantine equation, a solution always exists i.e. the trivial solution.This is because c=0, and we know 0 is divisible by every integer.

Finding a solution:
A solution can easily be found using the Extended Euclidean algorithm.
.
ax1 + by1 = gcd(a,b)
a.x1.c + by1.c = gcd(a,b).c (multiplying both sides by c)
a.x1.{c/gcd(a,b)} + by1.{c/gcd(a,b)} = c
a.{x1.(c/gcd(a,b))} + b.{y1.(c/gcd(a,b))} = c ….. (1)

Now, by comparing the equation (1) with the general Linear Diophantine equation we get:

x0 = x1 . c/gcd(a,b)
y0 = y1 . c/gcd(a,b)

Where x0 and y0 is a solution of the Linear Diophantine equation.

Implementation:
Program to find a solution of a given Linear Diophantine equation.

                                                        
#include<bits/stdc++.h>
using namespace std;
// function to find the gcd of a,b and coefficient x,y
//using Extended Euclidean Algorithm
int extended_gcd(int a, int b, int &x, int &y)
{
	if(a == 0)// base case
	{
		x = 0;
		y = 1;
		return b;// here b will be the gcd.
	}
	int x1, y1;
	int g = extended_gcd(b%a, a, x1, y1);
	x = y1 - (b/a) * x1;
	y = x1;
	return g;
}
// function to find a solution of the Diophantine equation if any
int one_solution(int a, int b, int c, int &x, int &y)
{
   int g = extended_gcd(a, b, x, y);
   if(c%g == 0) // condition for a solution to exist
   {
   	  //solution to the Diophantine equation
   	  x = x * c/g; 
   	  y = y * c/g;
   	  return 1;  // Atleast 1 solution exist
   } 
   return 0;   // no solution exists
}

int main()
{
   int a,b,c,x,y;
   cin>>a>>b>>c;
   if(one_solution(a,b,c,x,y))// if solution exists
   {
   	 cout<< "Solution are: "
   	 cout<<x<< " "<<y;
   }
   else// if no solution exists
   {
   	cout<< "Solution does not Exist";
   }
}
                                                    

Time Complexity - O(log(max(a,b)))
Auxiliary Space - O(1)

Finding all solutions:

Let, C0 be any arbitrary integer.
Add and subtract {C0.a.b/gcd(a,b)} in the general Linear Diophantine equation we get,

a.x0 + b.y0 + C0.a.b/gcd(a,b) - C0.a.b/gcd(a,b) = c
(Where x0 and y0 is a solution of the Linear Diophantine)

a.x0 + C0.a.b/gcd(a,b)+ b.y0 - C0.a.b/gcd(a,b) = c
a.(x0 + C0.b/gcd(a,b)) + b.(y0 - C0.a/gcd(a,b)) = c ….. (2)

Comparing equation (2) with general equation of Linear Diophantine equation
we get,

x = x0 + C0.b/gcd(a,b)
y = y0 - C0.a/gcd(a,b)

Where x,y are the solutions of the Linear Diophantine equation.

Chinese Remainder Theorem

Introduction:
Given set of n equations:

x % q[1] = r[1] or x ≡ r[1] (mod q[1])

x % q[2] = r[2]

x % q[3] = r[3]
.
.
.
x % q[n] = r[n]

Where, q[1], q[2]... q[n] are pairwise coprime positive integers i.e, for any 2 numbers q[i] and q[j] (i≠j)

GCD(q[i] , q[j]) = 1

And r[1].. r[n] are remainders when x is divided by q[1]... q[n] respectively .So, according to the Chinese Remainder theorem, there always exists a solution of a given set of equations and the solution is always unique modulo N, where

N = q[1].q[2]...q[n]

Finding solution:

Assume, C0 be a solution to the set of equations i.e C0 satisfies each and every equation belonging to the set. Then Xi = C0 ± K is also a solution to the set of equations if

K = LCM(q[1],q[2],q[3]....q[n]

LCM denotes the least common multiple of q[1] ,q[2]... q[n].
But ,we know that q[1] ,q[2]...q[n] are pairwise coprime therefore,

LCM(q[1],q[2]...q[n]) = q[1].q[2].q[3]...q[n]

Therefore, positive solutions to the set of equations are

Xi = C0 + K

Where C0 is the minimum positive solution that exists. So to find the solutions of the given set of equations we just need to find the minimum positive solution that exists.

Finding minimum positive solution:

Brute Force Approach:

A simple solution to find the minimum positive solution is to iterate from 1 till we find first value C0 such that all n equations are satisfied.

Implementation: function to find minimum positive solution.

                                                        
int Find_x(int q[] ,int r[] ,int n)
{
    int x=1;// initializing minimum positive solution
    bool flag;
    while(1)// we iterate till we get a solution
    {
        flag=true; 
        for(int i=0;i<n;i++)
        {
           if(x % q[i] == r[i] )//check if x gives remainder r[i] when divided by q[i]
             continue;
           flag=false;// if remainder is not r[i], this x cannot be the answer 
           break; 
        }
        if(flag) // if x satisfies all n equations ,then we have found the answer.
          break;
        x++; // check for further values
    }
    return x;
}
                                                    

Efficient Approach:

The general solution of the set of equation looks like

Xi = r[1].y[1].inv[1] + r[2].y[2].inv[2] . . . . . r[n].y[n].inv[n] .... (1)

Where,
y[1] = q[2].q[3].q[4]....q[n] or y[1] = N/q[1]

y[2] = q[1].q[3].q[4]....q[n]
.
.
.
y[n] = q[1].q[2].q[3].....q[n-1]

and,

inv[1] = y[1]-1 mod q[1]

inv[2] = y[2]-1 mod q[2]
.
.
.
inv[n] = y[n]-1 mod q[n]

We, know that the Chinese Remainder theorem states that there always exists a solution and this solution is always unique modulo N.So, to find the minimum positive solution we take (Xi mod N) where N = q[1].q[2]....q[n]. Therefore

x = Xi %N or

x = (r[1].y[1].inv[1] + r[2].y[2].inv[2] . . . . . r[n].y[n].inv[n]) % N …. (2)

Implementation: function to find minimum positive solution.

                                                        
// function to find gcd and coefficients using Extended Euclidean Algorithm
int Extended_gcd(int a ,int b, int &x, int &y)
{
    if(a==0)
    {
        x = 0;
        y = 1;
        return b;
    }
    int x1 ,y1;
    int g = Extended_gcd(b % a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return g;
}
//function to find inverse of val w.r.t m
int inv(int val ,int m)
{
    int x ,y;
    int g = Extended_gcd(val ,m ,x ,y);
    if(x < 0)
        x = (x % m + m) % m;
    return x;
}
int Find_x(int q[] ,int r[] ,int n) //function to find minimum positive solution
{
    int x=0 ,N=1;
    for(int i=0;i<n;i++)
        N *= q[i]; // compute N = q[0].q[1]..q[n-1] 
    for(int i=0;i<n;i++)
    {
       int y = N / q[i];
       x = ( x + r[i] * y * inv(y ,q[i]) ) % N; //computing x according to equation 2
    }
    return x;
}
                                                    

FERMAT’S LITTLE THEOREM

Fermat’s little theorem states that if p is a prime number, then for any integer a, the number ap – a is an integer multiple of p.

ap ≡ a (mod p), where p is prime.

If a is not divisible by p, Fermat’s little theorem is equivalent to the statement that ap-1 -1 is an integer multiple of p.

ap - 1 ≡ 1 (mod p)

1. Applications of Fermat’s little theorem

Modular multiplicative Inverse

If we know p is prime, then we can also use Fermats’s little theorem to find the inverse.
ap-1 ≡ 1 (mod p)

If we multiply both sides with a-1, we get
a-1 ≡ a p-2 (mod p)

                                                        
// C++ program to find modular multiplicative inverse 
//using fermat's little theorem.
#include <bits/stdc++.h> 
using namespace std; 

// Modular Exponentiation to compute x^y under modulo p
int power(int x, unsigned int y, unsigned int p) 
{ 
    if (y == 0) 
        return 1; 
    int res = power(x, y / 2, p) % p; 
    res = (res * res) % p; 

    return (y % 2 == 0) ? res : (x * res) % p; 
} 

// Function to find modular inverse of a under modulo p 
void modInverse(int a, int p) 
{ 
    if (__gcd(a, p) != 1) 
        cout << "Inverse doesn't exist"; 
    else { 
        // If a and p are relatively prime, then 
        // modulo inverse is a^(p-2) mode p 
        cout << "Modular multiplicative inverse is "
            << power(a, p - 2, p); 
    } 
} 

// Driver Program 
int main() 
{ 
    int a = 3, p = 11; 
    modInverse(a, p); 
    return 0; 
}
                                                    

2. Primality Test

In Fermat Primality Testing, k random integers are selected as the value of a (where all k integers follow gcd(a,k) = 1). If the statement of Fermat's Little Theorem is accepted for all these k values of a for a given number N, then N is said as a probable prime.

                                                        
// C++ program to check if N is prime.
#include <bits/stdc++.h>
using namespace std;

/* Iterative Function to calculate (a^n)%p in O(logy) */
int power(int a, unsigned int n, int p)
{
    int res = 1; // Initialize result
    a = a % p; // Update 'a' if 'a' >= p

    while (n > 0)
    {
        // If n is odd, multiply 'a' with result
        if (n & 1)
            res = (res*a) % p;

        // n must be even now
        n = n>>1; // n = n/2
        a = (a*a) % p;
    }
    return res;
}

// If n is prime, then always returns true, If n is
// composite then returns false with high probability
// Higher value of k increases probability of correct
// result.
bool isPrime(unsigned int n, int k)
{
    // Corner cases
    if (n <= 1 || n == 4) return false;
    if (n <= 3) return true;

    // Try k times
    while (k>0)
    {
        // Pick a random number in [2..n-2]  
        // Above corner cases make sure that n > 4
        int a = 2 + rand()%(n-4); 

        // Checking if a and n are co-prime
        if (__gcd((int)n, a) != 1)
            return false;

        // Fermat's little theorem
        if (power(a, n-1, n) != 1)
            return false;

        k--;
    }

    return true;
}

// Driver Program to test above function
int main()
{
    int k = 3;
    isPrime(11, k)? cout << " true\n": cout << " false\n";
    isPrime(15, k)? cout << " true\n": cout << " false\n";
    return 0;
}
                                                    

Introduction to Bits

We usually work with data types such as int, char, float, etc., or even data structures( i.e generally on bytes level) but sometimes programmers need to work at bit level for various purposes such as encryption, data compression, etc.
Apart from that operations on bits are time efficient and are used for optimizing programs.

Bitwise Operators

There are different operators that work on bits and are used for optimizing programs in terms of time.

Unary Operators

1. NOT (!) : Bitwise NOT is an unary operator that flips the bits of the number i.e., if the bit is 0, it will change it to 1 and vice versa.It gives the one’s complement of a number.
Example: - N = 5 = (101)2
~N = ~5 = ~(101)2 = (010)2 = 2

Binary Operators

1. AND (&) : Bitwise AND operates on two equal-length bit patterns. If both bits at the ith position of the bit patterns are 1, the bit in the resulting bit pattern is 1, otherwise 0.
Example:-
00001100 = (12)10
& 00011001 = (25)10
_________
00001000 = (8)10

2. OR ( | ) : Bitwise OR also operates on two equal-length bit patterns. If both bits at the ith position of the bit patterns are 0, the bit in the resulting bit pattern is 0, otherwise 1.
Example:-
00001100 = (12)10
| 00011001 = (25)10
_________
00011101 = (29)10

3. XOR ( ^ ) : Bitwise XOR also operates on two equal-length bit patterns. If both bits in the ith position of the bit patterns are 0 or 1, the bit in the resulting bit pattern is 0, otherwise 1.
Example:-
00001100 = (12)10
^ 00011001 = (25)10
_________
00010101 = (21)10

Basics Operations on Bits

Tricks with Bits

1. x ^ ( x & (x-1)) : Returns the rightmost 1 in binary representation of x.

(x & (x - 1)) will have all the bits equal to the x except for the rightmost 1 in x. So if we do bitwise XOR of x and (x & (x-1)), it will simply return the rightmost 1. Let’s see an Example:-
x = 10 = (1010)2 `
x & (x-1) = (1010)2 & (1001)2 = (1000)2
x ^ (x & (x-1)) = (1010)2 ^ (1000)2 = (0010)2

2. x & (-x) : Returns the rightmost 1 in binary representation of x

(-x) is the two’s complement of x. (-x) will be equal to one’s complement of x plus 1.
Therefore (-x) will have all the bits flipped that are on the left of the rightmost 1 in x. So x & (-x) will return rightmost 1.

Example:-
x = 10 = (1010)2
(-x) = -10 = (0110)2
x & (-x) = (1010)2 & (0110)2 = (0010)2

3. x | (1 << n) : Returns the number x with the nth bit set.

(1 << n) will return a number with only nth bit set. So if we OR it with x it will set the nth bit of x.
x = 10 = (1010)2 n = 2
1 << n = (0100)2
x | (1 << n) = (1010)2 | (0100)2 = (1110)2

In the programming world, we often need to find out whether an element is present in the given data set or not.
Formally, we have an array and we are asked to find the index of an element ‘k’ in the array. And if it is not present, inform that.

The simplest way to answer this question is Linear Search.
In linear search, we traverse the entire array and check each element one by one.

Binary Search is the most useful search algorithm. It has many applications too, mainly due to its logarithmic time complexity. For example, if there are 109 numbers and you want to search for a particular element, using binary search you can do this task in just around 32 steps!
The only thing that one must keep in mind is that binary search works only on sorted set of elements.

The main idea of the algorithm can be explained as follows:
Let we have a sorted array of n elements, and we want to search for k.
Let's compare k with the middle element of the array.
If k is bigger, it must lie on the right side of the middle element.
Else if it is smaller, it must lie on the left side of the middle element.
This means, in one step, we reduced the “search space” by half. We can continue this halfing-process recursively until we find the required element. That's it.
Remember, we could do this because the elements were sorted.

Here, in each step we half the length of the interval. In the worst case, we continue the process till the length becomes 1. Hence, the time complexity of binary search is O(log2 N), where N is the initial length of interval.

Sometimes a situation arises where we can’t calculate the answer directly from given data due to too many possibilities, but we can have a way to know if a number is possible as a solution or not. i.e. we ask a number and get a feedback as “yes” or “no”. And using the feedback we shorten our “search space”, and continue the search for our answer.
This technique is known as Binary Search the Answer.

Lower Bound: Lower bound of a number in a sorted array is the first element in that array that is not smaller than the given number. STL has a useful inbuilt function
lower_bound(start_ptr, end_ptr, num) to carry out this task. It returns the pointer pointing to the required element. As this function uses binary search in its working, its time complexity is O(log n).
Upper Bound: Upper bound of a number in a sorted array is the number that is just higher than the given number. STL provides an inbuilt function for this too:
upper_bound(start_ptr, end_ptr, num). Similar to lower_bound(), this function also returns the pointer pointing to the required element, and its time complexity is O(log n).
Note: These functions return the end pointer if the required element is not present in the array.
Note: If there are multiple occurrences of the required element in the array, these functions return the pointer to the first occurrence of it.

Just like the Binary search algorithm, Ternary search is also a divide and conquer algorithm. And the array needs to be sorted to perform ternary search.The only difference is, instead of dividing the segment into two parts, here we divide it into three parts, and find in which part our key element lies.

                                                        
int ternary_search(int l,int r, int k)
{
    if(r>=l)
    {
        int mid1 = l + (r-l)/3;
        int mid2 = r -  (r-l)/3;
        if(ar[mid1] == k)
            return mid1;
        if(ar[mid2] == k)
            return mid2;
        if(k<ar[mid1])		 // First part
            return ternary_search(l,mid1-1,k);
        else if(k>ar[mid2])	// Third part
            return ternary_search(mid2+1,r,k);
        else  			// Second part
            return ternary_search(mid1+1,mid2-1,k);
    }
    return -1;
}
                                                    

The idea behind this algorithm is pretty simple. We divide the array into two parts: sorted and unsorted. The left part is a sorted subarray and the right part is an unsorted subarray. Initially, the sorted subarray is empty and the unsorted array is the complete given array.
We perform the steps given below until the unsorted subarray becomes empty:
(Assuming we want to sort it in non-decreasing order)
Pick the minimum element from the unsorted subarray.
Swap it with the leftmost element of the unsorted subarray.
Now the leftmost element of the unsorted subarray becomes a part (rightmost) of the sorted subarray and will not be a part of the unsorted subarray.

Bubble sort, sometimes referred to as sinking sort, is based on the idea of repeatedly comparing pairs of adjacent elements and then swapping their positions if they exist in the wrong order. In one iteration of the algorithm the smallest/largest element will result at its final place at end/beginning of an array. So in some sense movement of an element in an array during one iteration of bubble sort algorithm is similar to the movement of an air bubble that raises up in the water, hence the name.

Lets try to understand the algorithm with an example: Arr[ ] = {9,2,7,5}.
At first our array looks like this:
{9,2,7,5}
In the first step, we compare the first 2 elements, 2 and 9, As 9>2 , we swap them.
{2,9,7,5}
Next, we compare 9 and 7 and similarly swap them.
{2,7,9,5}
Again, we compare 9 and 5 and swap them.
{2,7,5,9}
Now as we have reached the end of the array, the second iteration starts.
In the first step, we compare 2 and 7. As 7>2, we need not swap them.
{2,7,5,9}
In the Next step, we compare 7 and 5 and swap them.
{2,5,7,9}

In this way, the process continues.
In this example, there will not be any more swaps as the array is sorted after the steps shown above.

Insertion sort is the sorting mechanism where the sorted array is built having one item at a time. The array elements are compared with each other sequentially and then arranged simultaneously in some particular order. The analogy can be understood from the style we arrange a deck of cards in our hand. This sort works on the principle of inserting an element at a particular position, hence the name Insertion Sort.

To sort an array of size n in ascending order:
1: Iterate from arr[1] to arr[n] over the array.
2: Compare the current element (key) to its predecessor.
3: If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.
Lets try to understand the algorithm with an example: Arr[ ] = {69, 55, 2, 22, 1}.

At first our array looks like this:
{69,55,2,22,1}
Let us loop from index 1 to index 4

For index=1, Since 55 is smaller than 69, move 69 and insert 55 before 69
{55,69,2,22,1}
For index=2, 2 is smaller than both 55 and 69. So shift 55 and 69 to right and insert 2 before them.
{2,55,69,22,1}
For index=3, 22 is smaller than both 55 and 69. So shift 55 and 69 to right and insert 22 before them.
{2,22,55,69,1}
For index=4, 22 is smaller than both 55 and 69. So shift 55 and 69 to right and insert 22 before them.
{1,2,22,55,69}

Merge sort algorithm works on the principle of Divide and Conquer.
It is one of the most efficient sorting algorithms. It is one of the most respected algorithms due to many reasons. Also, it is a classic example of divide and conquer technique.

The main idea behind the algorithm is to divide the given array into two parts recursively until it becomes a single element, trivial to sort. The most important part of the algorithm is to merge two sorted arrays into a single array.
Let us first understand how to merge two sorted arrays:
1.We will take two pointers which will point to the starting of the two arrays initially.
2.Then we will take a new, empty auxiliary array with length equal to the sum of lengths of the two sorted arrays.
3.Now, we will compare the elements pointed by our two pointers. And insert the smaller element into the new array and increment that pointer (Assuming we are sorting in non-decreasing order).
4.We continue this process till any of the pointers reach the end of the respective array. Then we insert the remaining elements of the other array in the new array one by one.
(Have a look at the merge function in the following implementation of merge sort)

Now let's understand the merge sort algorithm:
>First of all, we call the mergesort function on the first half and second half of the array.
>Now the two halves are sorted, the only thing to do is to merge them. So we call the merge function.
>We do this process recursively, with the base case that, when the array consists of just one element, it is already sorted and we can return the function call from there.
It's time for an example:
>Let's take an array, Arr[ ]={14,7,3,12,9,11,6,2}.
>Following figure shows each step of dividing and merging the array.
>In the figure, segment (p to q) is the first part and segment (q+1 to r) is the second part of the array at each step.

Competitive programmers love C++, STL is one of the reasons. STL i.e. Standard Template Library provides us many in-built useful functions, sort() is one of them. In other words, sort() is one of the most useful STL functions.
Basically, sort() sorts the elements in a range, with time complexity O(N log2N) where N is the length of that range.
It generally takes two parameters , the first one being the point of the array/vector from where the sorting needs to begin and the second parameter being the point up to which we want the array/vector to get sorted. The third parameter is optional and can be used when we want to sort according to some custom rule. By default it sorts in non-decreasing order.

The third parameter of sort() function, called as the comparator, acts as an operator to compare two elements.
If we did not provide it sort() uses “<” as an operator.

This “comparator” function returns a value; convertible to bool, which tells the sort() function whether the passed “first” argument should be placed before the passed “second” argument or not.

Hash Function:
Hash function is a function that takes a key as an input and converts it to another small practical integer value which is then used as an index in the hash table.
Key -> Hash Function -> Address in hash table

There are various methods to generate/make hash functions, but the trivial and most often used method is, Division Method (Take modulo of given key with another number and use this as index in hash table )

For a good hash function we should consider that it is efficiently computed and the various index positions in the table are equally likely for each key.

Similar to the direct access table, it is an array to store pointers/data corresponding to the index location generated for a key by hash function.
Hash table is different from a direct access table for the original range of key as the hash function reduces the range of the original key to a small practical range.

Why to use Hashing ?
In various real life situations we deal with very large values and their associated data for which we need to do insertion,deletion and searching operations.

To search for a given element we have two techniques:
1.Linear Search - Time complexity O(n)
2.Binary Search - Time complexity O(log n)

For storing data, we can use:

1.Array: If we use array and store information then insertion, deletion and searching will have time complexity of O(n).
2.Sorted Array: Searching can be done in O(log n) but we need to sort after each insertion or deletion which increases the time complexity of O(n) to O(n*log n) or more.
3.LinkedList: Insertion, deletion and searching can be done in O(n) time.
4.AVL Tree: Insertion, deletion and searching can be done in O(log2n) time.
5.Direct address table: We can create a list of the size of maximum value we will be dealing with and then use value as index to store data in the array or list, this will make insertion, deletion and searching in O(1) constant time. But it will cost us in terms of memory as to store x data pointers with highest value h (1<= h <= 1050) ,space complexity is of order O(x*h), which is not a feasible solution.

So from the above discussion it can be noticed for such cases, best case for searching is O(log n) and worst case is O(n).
We use Hashing to get the best and average case to be done in O(1) and in the worst case O(n).

Performance of Hash Function:
The performance of hashing can be evaluated under the assumption that each key is equally likely to be hashed to any slot of the table.
n = Number of keys to be inserted in the hash table
m = Number of slots in the hash table

Load factor α = n/m

Collision in Hashing:
Using a hash function we get a smaller number for a big key, so there might be a possibility that after processing different keys through a hash function we get the same value. This situation where a newly inserted key maps to an already occupied slot in the hash table is called collision.
Hash(key1) = value
Hash(key2) = value
To handle such situations we use some collision handling technique.
We can use following collision handling technique:
Linear probing
Quadratic probing
Chaining
Double hashing

1. Linear Probing:

We have a hash table of size, more than the number of values to be stored.
In linear probing if there is something stored already at the index v in the hash table, we then check for the (v + 1)%Table_Size th index and so on (increment index by 1) till we find an empty slot in the hash table.
For example, You have a hash function x % 8 and you need to insert values 80,86,88,93,91,102,105,121:

2. Quadratic Probing:

We have a hash table of size L, more than the number of values to be stored.
In quadratic probing if there is something stored already at the index v in the hash table, we then check for the (v + 1*1) %Table_Size index and so on till we find an empty slot in the hash table.
Pattern for finding empty slot:
(v + 1*1) %Table_Size → (v + 2*2) %Table_Size → …... → (v + i*i) %Table_Size

Performance of Linear and Quadratic Probing:
Load factor α = n/m ( < 1 )
Search, Insert and Delete take (1/(1 - α)) time

Problems faced during Linear and Quadratic Probing:
Can be used only when the number of frequencies and keys are known.
A slot can be used even if an input key doesn’t map to it using the hash function.
After some collision resolution it starts taking time to find a free slot or to search an element.

3. Chaining:

In the chaining method of Collision resolution we make each cell of the hash table point to a linked list of records that have the same hash function value. Chaining is simple, but requires additional memory outside the table.
Some points to remember:
This way the Hash table never fills up and we can remove the factor that we need to know the number of keys and frequencies as we have to know in linear and quadratic probing.
As some space in hash table are never used, there is wastage of space.
If the chain becomes long then search time can become O(n) in the worst case.

C++ program to use chaining as Collision resolution method
Performance of Chaining:
If, Load factor α = n/m
Expected time to search = O(1 + α)
Expected time to delete = O(1 + α)
Time complexity of search insert and delete is O(1) if α is O(1)

For example, You have a hash function x % 8 and you need to insert values 80,86,88,93,91,102,105,121:

4. Double Hashing:

Double hashing is another collision handling technique in which we apply another hash function to key when a collision occurs.
Let, hash1() and hash2() are the hashing functions.
If using first hashing function there is a collision, we do double hashing using (hash1(key) + i * hash2(key)) % Table_Size, we increment the value of i, till collision is resolved.
Choose such a hash2() function which never evaluates value to zero and also probe all maximum possible indexes in the hash table.

A linked list is a data structure in which the objects are arranged in a linear order. Unlike an array, though, in which the linear order is determined by the array indices, the order in a linked list is determined by a pointer in each object. Linked lists provide a simple, flexible representation for dynamic sets.

Linked list data set :

General Linked list :

Singly Linked List
Singly-linked lists contain nodes which have a data field as well as 'next' field, which points to the next node in line of nodes. Operations that can be performed on singly-linked lists include insertion, deletion and traversal.
A singly linked list whose nodes contain two fields: an integer value and a link to the next node

The following code demonstrates how to add a new node with data "value" to the end of a singly linked list:

                                                        
node addNode(node head, int value) {
    node temp, p;  // declare two nodes temp and p
    temp = createNode(); // assume createNode creates a new node with data = 0 and next
			       //  pointing to NULL
    temp->data = value;   // add element's value to data part of node
    if (head == NULL)
   {
        head = temp;     // when linked list is empty
    }
    else {
        p = head; // assign head to p 
        while (p->next != NULL) {
            p = p->next; // traverse the list until p is the last node. The last node always points
			// to NULL
        }
        p->next = temp; // Point the previous last node to the new node created.
    }
    return head;
}
                                                    

Stacks and Queues are dynamic sets in which the element can be added or removed by some predefined operations.

In a stack, it implements LAST IN, FIRST OUT (LIFO). It means whichever element is added at the last will be the one to be removed first.

In a queue, it implements FIRST IN, FIRST OUT (FIFO). It means whichever element is added first will be removed first.

There are several ways to implement stacks and queues on a computer.

Stacks
The insert operation on a stack is often called PUSH, and the delete operation is called POP. These names are allusions to physical stacks, such as the spring-loaded stacks of plates used in cafeterias. The order in which plates are popped from the stack is the reverse of the order in which they were pushed onto the stack since only the top plate is accessible. Below is a visual of how stack data structures work, by inserting and removing elements, which expresses the LIFO property. Let’s define a stack named S.

Stack Definition in c++ : stack < <data type> > <stack name>;

Here we are defining stack if Integer Data Type :

                                                        
stack< int > S
                                                    

Push Operations :

Pop Operations :

Other Basic operations of Stack :

1 . empty() : checks if the stack is empty.
2. size() : returns the count of elements present in the stack.
3. top() : return the topmost element present in the stack.

When the stack contains no elements, it is said to be empty. The stack can be tested for emptiness by the query operation empty(). If an empty stack is popped, we call it
stack underflows, which is normally an error. And if the count of elements exceeds the maximum limit, we call it stack overflow. We do not worry about stack overflow in the code implementations shown below.

Code Implementations with various operations :

Queues

We call the insert operation on a queue as enque, and we call the delete operation dequeue(It is the same as pop in the stack) . The FIFO property of a queue causes it to operate as a line of people in the registrar's office. The queue has a head and a tail. When an element is enqueued, it takes its place at the tail of the queue, just as a newly arriving student takes a place at the end of the line. The element dequeued is always the one at the head of the queue, like the student at the head of the line who has waited the longest.
Below is a visual of how queue data structure works, by inserting and removing elements, which expresses the FIFO property. Let’s define a queue named q.

Queue definition : queue < <data type> > <queue name>;

Here we are defining queue of Integer Data Type :

                                                        
queue< int > q
                                                    

Push and Pop Operation :

Other Basic Operations in Queue :

1. size() : returns the number of elements in the queue.
2. empty() : checks if the queue is empty.
3. front() : returns the element in front of the queue
4. back() : returns the element at the back of the queue.

Code implementation with various operations :

Binary Tree Representation
Each node contains three components :
1. Pointer to left child
2. Pointer to right child
3. Data element
Code :-

                                                        
struct node {
   int data;   
   struct node *left;
struct node *right;
};
                                                    

Types of Binary Trees

1.Full Binary Tree : A full binary tree is A binary tree in which all the nodes have either zero or two children.

2. Complete Binary tree : A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

3.Perfect Binary tree : A perfect binary tree is a binary tree in which every internal node has exactly two child nodes and all the leaf nodes are at the same level

Binary tree traversals:-
A binary Tree can be traversed in two ways:
1. Breadth First Traversal (Or Level Order Traversal)
2. Depth First Traversals
A.Inorder Traversal (Left-Root-Right)
B.Preorder Traversal (Root-Left-Right)
C.Postorder Traversal (Left-Right-Root)

Breadth First Traversal
In BFS, For each node, first the node is visited and then it’s child nodes are put in a queue.This process is repeated till the queue becomes empty.

Code :

                                                        
void LevelOrder(Node *root)
{
    // Base Case
    if (root == NULL)  return;
 
    // Create an empty queue for level order traversal
    queue<Node *> q;
 
    // Enqueue Root 
    q.push(root);
 
    while (q.empty() == false)
    {
        // Print front of queue and remove it from queue
        Node *node = q.front();
        cout << node->data << " ";
        q.pop();
 
        /* Enqueue left child */
        if (node->left != NULL)
            q.push(node->left);
 
        /*Enqueue right child */
        if (node->right != NULL)
            q.push(node->right);
    }
}
                                                    

Depth First Traversals

Inorder traversal
1.First, visit all the nodes in the left subtree
2.Then the root node
3.Visit all the nodes in the right subtree

Code:-

                                                        
void Inorder(struct Node* node)
{ 
    if (node == NULL) 
        return; 
  
    /* first recur on left child */
    Inorder(node->left); 
  
    /* then print the data of node */
    cout << node->data << " "; 
  
    /* now recur on right child */
    Inorder(node->right); 
}
                                                    

Preorder traversal
1.Visit root node
2.Visit all the nodes in the left subtree
3.Visit all the nodes in the right subtree
Code:-

                                                        
void Preorder(struct Node* node) 
{ 
    if (node == NULL) 
        return; 
  
    /* first print data of node */
    cout << node->data << " "; 
  
    /* then recur on left subtree */
    Preorder(node->left);  
  
    /* now recur on right subtree */
    Preorder(node->right); 
}
                                                    

Postorder traversal

1.Visit all the nodes in the left subtree
2.Visit all the nodes in the right subtree
3.Visit the root node

Code:-

                                                        
void Postorder(struct Node* node) 
{ 
    if (node == NULL) 
        return; 
  
    // first recur on left subtree 
    Postorder(node->left); 
  
    // then recur on right subtree 
    Postorder(node->right); 
  
    // now deal with the node 
    cout << node->data << " "; 
}
                                                    

Binary Search Tree(BST)

A binary search tree (BST)is a rooted binary tree whose internal nodes each store a key greater than all the keys in the node's left subtree and less than those in its right subtree.The left and right subtree each must also be a binary search tree.

The basic operations of BST are as follows:-

1. Search : For searching an element in the binary search tree.

The algorithm works on the property that in a binary search tree,all the values in the left subtree are less than the particular node and all the values in the right subtree are greater than the particular node.If the value we are searching is less than the root,then the right subtree is not considered and if the value is greater than the root,then the left subtree is not considered.This is done recursively.

Code for the search operation is given below:

                                                        
struct node* find(struct node* root, int key) 
{
    if (root == NULL ) //If the key is not present in the tree
      return NULL; 
     
    if( root->key == key) // key is present at the root
      return root;
    
    if (root->key < key) //root's key is less than the key
      return find(root->right, key); 
  
   //root's key is greater than the key
    return find(root->left, key); 
}
                                                    

2. Insert : Inserting an element into the binary search tree.

The new element is inserted in such a way that even after adding the element,the properties of the BST hold true. We Start searching from the root node, if the value to be inserted is less than the data, search for an empty location in the left subtree and insert the data. Otherwise, search for an empty location in the right subtree and insert the data.

Code for insert operation is given below:-

                                                        
struct node *insert(struct node *node, int key) {
 
  // Return a new node if the tree is empty
  if (node == NULL) return newNode(key);
 
  if (key < node->key)
    node->left = insert(node->left, key);
  else
    node->right = insert(node->right, key);
 
  return node;
}
                                                    

3.Delete : Deleting an element present in the BST.

When we have to delete a node in BST,three cases arise:-
i)the node to be deleted is the leaf node
ii)the node to be deleted lies has a single child node
iii)the node to be deleted has two children

Code for the delete operation is given below:-

                                                        
struct node *delete(struct node *root, int key) {
  // Return if the tree is empty
  if (root == NULL) return root;
 
  // Find the node to be deleted
  if (key < root->key)
    root->left = Node(root->left, key);
  else if (key > root->key)
    root->right = Node(root->right, key);
  else {
 
    // If the node is with only one child or no child
    if (root->left == NULL) {
      struct node *temp = root->right;
      free(root);
      return temp;
    } else if (root->right == NULL) {
      struct node *temp = root->left;
      free(root);
      return temp;
    }
 
    // If the node has two children
    struct node *temp = minValueNode(root->right);
 
    // Place the inorder successor in position of the node to be deleted
    root->key = temp->key;
 
    // Delete the inorder successor
    root->right = deleteNode(root->right, temp->key);
  }
  return root;
}
                                                    

Heap

A Heap is a tree-based data structure in which all the nodes of the tree are in a specific order.

There are two types of Heap :-

1.Max Heap:- In Max Heap, the key of the parent node will always be greater than or equal to the key of the child node across the tree.

2.Min Heap:- In Min Heap, the key of the parent node will always be less than or equal to the key of the child node across the tree.

Heap in C++ STL

The heap operations are as follows:-

1.make_heap() : This function converts a range in a container to a heap.
2.front() : This function returns the first element of the heap which is the largest number.
3.push_heap() : This function is used to insert an element into the heap. The size of the heap is increased by 1.
4.pop_heap() : this function is used to delete the largest element of the heap.After deleting an element, the heap elements are reorganized accordingly. The size of heap is decreased by 1.
5.sort_heap() : This function is used to sort the heap in ascending order.
6.is_heap() : This function is used to check whether the container is a heap or not.
7.is_heap_until() : This function returns the iterator to the position till the container is the heap.

Code implementation with various operations :

Priority queue

A priority queue is an extension of a queue in which each element has a priority associated with it and is served according to its priority. If elements with the same priority occur, they are served according to their order in the queue.

Priority Queue in C++ STL

Syntax for creating priority queue.

                                                        
priority_queue<int> pq;
                                                    

Default C++ creates a max heap for priority queue.

The heap operations are as follows :-

1.push() : This function inserts an element in the priority_queue.Its time complexity is O(logN) where N is the size of the priority queue.

2.pop() : This function removes the topmost element from the priority queue, i.e, greatest element.Its time complexity is O(logN) where N is the size of the priority queue.

3.top() : This function returns the element at the top of the priority queue which is the greatest element present in the queue.Its time complexity is O(1).

4.size() : this function returns the size of the priority queue.Its time complexity is O(1).

5.empty() : this function returns boolean true if the priority queue is empty and false, if it’s not empty.Its time complexity is O(1).

6.swap() : This function is used to swap the contents of one priority queue with another priority queue of the same type and size.

Code implementation with various operations :

The C++ STL (Standard Template Library) is a powerful set of C++ template classes to provide general-purpose classes and functions with templates that implement many popular and commonly used algorithms and data structures like vectors, lists, queues, and stacks.

C++ Standard Template Library is made up of following three well-structured components −

Containers : Containers are used to manage collections of objects of a certain kind. There are several different types of containers like deque, list, vector, map etc.

Algorithms : Algorithms are defined as collections of functions especially designed to be used on ranges of elements.They act mainly on containers and provide means for various operations for the contents of containers.

Iterators : Iterators are used for working upon a sequence of different elements.These sequences may be containers.They are major features that allow generality in STL.

Iterator:
An iterator is any object that, points to some element in a range of elements (such as an array or a container) and has the ability to iterate through those elements using a set of operators (with at least the increment (++) and dereference (*) operators).
A pointer is a form of an iterator. A pointer can point to elements in an array, and can iterate over them using the increment operator (++). There can be other types of iterators as well. For each container class, we can define an iterator which can be used to iterate through all the elements of that container.

Example:

                                                        
vector<int>::iterator it;       // creates iterator it for vector container
                                                    

Implementation:

Pair:
Pair is a container that can be used to bind together two values which may be of different types. Pair provides a way to store two heterogeneous objects as a single unit.
One must include a <utility> header file to use the pair.

Different ways to declare and initialize pair are:

                                                        
pair < char , int > p1;         //creates a default pair
pair < char , int >p2 (‘a’,1);      //initialisation of pair p2  
pair < char , int > p3(p2);      //creates a copy of p2
                                                    

Implementation:

String:
C++ provides a powerful alternative for the char*. It is not a built-in data type, but is a container class in the Standard Template Library. String class provides different string manipulation functions like concatenation, find, replace etc.
<string> is a header file that contains functions of string containers.

Different ways to declare strings are:

string s ;
Creates empty string s
string s1(“Hello World”);
Creates string s1 storing Hello World
string s1(s2) ;
Creates a copy s1 of another string s2
string s1( s2,1,3);
Creates a string s1 storing substring of s2 from index 1 to index 3
string s1(“Hello World”,5);
Creates a string s1 storing “Hello” that is only 5 characters of passed string
string s1(5,”*”);
Creates string s1 storing “*****”
string s2(s1.begin(),s1.end());
Creates a copy of s1 using iterators.

Some of the member functions of string:

•append(): Inserts additional characters at the end of the string (can also be done using ‘+’ or ‘+=’ operator). Its time complexity is O(N) where N is the size of the new string.
Syntax to add str2 at the end of str1:
str1.append(str2)
•assign(): Assigns new string by replacing the previous value (can also be done using ‘=’ operator).
Syntax to assign str2 to str1:
str1.assign(str2)
•at(): Returns the character at a particular position (can also be done using ‘[ ]’ operator). Its time complexity is O(1).
Syntax to print character at index idx of string str:
str.at(idx)
•begin(): Returns an iterator pointing to the first character. Its time complexity is O(1).
Syntax:
string_name.begin()
•clear(): Erases all the contents of the string and assign an empty string (“”) of length zero. Its time complexity is O(1).
Syntax:
string_name.clear()
•compare(): Compares the value of the string with the string passed in the parameter and returns an integer accordingly. If both the strings are equal then it returns 0,if string s2 is greater than that of s1 then it returns value greater than zero otherwise it returns value less than zero.Its time complexity is O(N + M) where N is the size of the first string and M is the size of the second string.
Syntax to compare two strings:
s1.compare(s2)
Syntax to compare string s1 with s2 from idx index of s2 for len characters:
s2.compare(idx,len,s1)
•copy(): Copies the substring of the string in the string passed as parameter and returns the number of characters copied. Its time complexity is O(N) where N is the size of the copied string.
Syntax to copy s2 to s1:
s1.copy(s2)
•c_str(): Convert the string into a C-style string (null terminated string) and return the pointer to the C-style string. Its time complexity is O(1).
•empty(): Returns a boolean value, true if the string is empty and false if the string is not empty. Its time complexity is O(1).
Syntax:
string_name.empty()
•end(): Returns an iterator pointing to a position which is next to the last character. Its time complexity is O(1).
Syntax:
string_name.end()
•erase(): Deletes a substring of the string. Its time complexity is O(N) where N is the size of the new string.
Syntax to delete a character at position pos from string:
string_name.erase(pos)
Syntax to delete characters from a given range [pos1,pos2):
string_name.erase(pos1,pos2)
Syntax to remove substring of length len from index idx:
string_name.erase(idx,len)
•find(): Searches the string and returns the first occurrence of the parameter in the string. Its time complexity is O(N) where N is the size of the string.
Syntax to find str2 from str1:
str1.find(str2)
•insert(): Inserts additional characters into the string at a particular position. Its time complexity is O(N) where N is the size of the new string.
•length(): Returns the length of the string. Its time complexity is O(1).
Syntax:
string_name.length()
•replace(): Replaces the particular portion of the string. Its time complexity is O(N) where N is the size of the new string.
Syntax to replace len characters from pos position of str1 with str2:
str1(pos,len,str2)
•resize(): Resize the string to the new length which can be less than or greater than the current length.If new size is greater than that of original one then character passed as parameter is added to string to make it of new size. Its time complexity is O(N) where N is the size of the new string.
Syntax :
string_name.resize(new_size,character)
•size(): Returns the length of the string. Its time complexity is O(1).
Syntax:
string_name.size()
•substr(): Returns a string which is the copy of the substring of range [pos,pos+len) where pos is position and len is length given as parameters.Its time complexity is O(N) where N is the size of the substring.
Syntax:
string_name.substr(pos,len)

Implementation:

Same as dynamic arrays,vectors are STL containers having the ability to resize itself automatically when an element is inserted or deleted, with their storage being handled automatically by the container. Vector elements are placed in contiguous storage so that its elements can be accessed and traversed using iterators just as efficiently as in arrays.
One must include a <vector> header file to use vectors.

Ways to create vectors:

vector<data_type> v;
Creates an empty vector v without any element.
vector<data_type> v1(v2) ;
Creates a copy of another vector of the same type.(all elements of v2 is copied to v1)
vector<data_type> v(n);
Creates a vector v with n elements that are created by the default constructor.
vector<data_type> v(n,element);
Creates a vector v initialised with n copies of element elem.
vector<data_type> v(beg,end);
Creates a vector v initialised with the elements of range [beg,end).

Some of the member functions of vectors are:
•at():It returns a reference to the element at specified position in the vector.Its time complexity is O(1).
Syntax:
vector_name.at(val)
where val is the position to be fetched.
•insert():Inserts new elements into the vector at a particular position. Its time complexity is O(N + M) where N is the number of elements inserted and M is the number of the elements moved .
Syntax to insert element val at position pos:
vector_name.insert(pos,val)
•push_back():Inserts a new element at the end of the vector. Its time complexity is O(1).
Syntax:
vector_name.push_back(val)
where val is the element to be inserted.
•pop_back():Removes the last element from the vector. Its time complexity is O(1).
Syntax:
vector_name.pop_back()
•begin():It is a function which returns an iterator pointing to the first element of the vector.Its time complexity is O(1).
Syntax:
vector_name.begin()
•end():It is a function which returns an iterator pointing to next to the last element of the vector.Its time complexity is O(1).
Syntax:
vector_name.end()
•back():It returns a reference to the last element in the vector.Its time complexity is O(1).
Syntax:
vector_name.back()
•front():It returns a reference to the element at specified position in the vector.Its time complexity is O(1).
Syntax:
vector_name.front()
•clear():Deletes all the elements from the vector and assigns an empty vector. Its time complexity is O(N) where N is the size of the vector.
Syntax:
vector_name.clear()
•size():It is a function which returns the number of elements present in the vector.Its time complexity is O(1).
Syntax:
vector_name.size()
•empty():It is a function which is used to check whether the vector is empty or not.It returns true if the vector is empty otherwise returns false.Its time complexity is O(1).
Syntax:
vector_name.empty()
•erase():It is a function used to remove elements from the specified position of the vector.
Its time complexity is O(N + M) where N is the number of the elements erased and M is the number of the elements moved.
Syntax to remove element at a specified position pos:
vector_name.erase(pos);
Syntax to remove elements from a given range [pos1,pos2):
vector_name.erase(pos1,pos2)
•resize():This function resizes the container so that its size becomes n.This function alters the container by removing or inserting values in the vector.Its time complexity is O(N) where N is the size of the resized vector.
Syntax:
vector_name.resize(n,val)
where n is the new container size and val is the value to be inserted if the new size exceeds current one.

Implementation:

Lists are sequence containers that allow non-contiguous memory allocation. As compared to vector, list has slow traversal, but once a position has been found, insertion and deletion are quick.It is implemented as Doubly linked list in STL.
One must include a <list> header file to use list.

Syntax to declare list:
list<data_type> list_name

Some of the member function of List:

•begin():It is a function which returns an iterator pointing to next to the last element of the list.Its time complexity is O(1).
Syntax:
list_name.end()

•end():It is a function which returns an iterator pointing to next to the last element of the list.Its time complexity is O(1).
Syntax:
list_name.end()

•push_back():It adds a new element at the end of the list, after its current last element. Its time complexity is O(1).
Syntax to insert val at the end of the list:
list_name.push_back(val)

•pop_back():It removes the last element of the list, thus reducing its size by 1. Its time complexity is O(1).
Syntax to remove the last element of the list
list_name.pop_back()

•push_front():It adds a new element at the front of the list, before its current first element. Its time complexity is O(1).
Syntax to insert val at the beginning of the list:
list_name.push_front(val)

•pop_front():It removes the first element of the list, thus reducing its size by 1. Its time complexity is O(1).
Syntax to remove first element of the list:
list_name.pop_front()

•front():It returns a reference to the element at specified position in the list.Its time complexity is O(1).
Syntax:
list_name.front()

•back():It returns a reference to the last element in the list.Its time complexity is O(1).
Syntax:
list_name.back()

•assign(): It assigns new elements to the list by replacing its current elements and changing its size accordingly.It time complexity is O(N).
Syntax to replace n number of elements from beginning with val
list_name.assign(n,val)

•insert():It inserts new elements in the list before the element on the specified position. Its time complexity is O(N).
Syntax for inserting n elements having value val before pos
list_name.insert(pos,n,val)

•erase():It removes all the elements from the list, which are equal to the given element. Its time complexity is O(N).
Syntax to remove element from a specified position:
list_name.erase(pos)
Syntax to remove element from given range [pos1,pos2):
list_name.erase(pos1,pos2)

•remove():It removes all the elements from the list, which are equal to the given element passed as parameter. Its time complexity is O(N).
Syntax:
list_name.remove(val)

•empty():It is a function which is used to check whether the list is empty or not.It returns 1 if the list is empty otherwise it returns 0.Its time complexity is O(1).
Syntax:
list_name.empty()

•size():It returns the number of elements in the list. Its time complexity is O(1).
Syntax :
list_name.size()

•reverse():It reverses the order of elements in the list. Its time complexity is O(N).
Syntax:
list_name.reverse()

Implementation:

Sets are associative containers which store unique values in sorted order. The value of the element cannot be modified once it is added to the set, though it is possible to remove and add the modified value of that element.
One must include a <set> header file to use set.

Ways to create set are:

set<data_type> set_name
Creates an empty set
set<data_type> s1(arr,arr+n)
Creates set s1 from a given array arr of size n
set<data_type> s2(s1)
Creates a copy s2 of set s1
set<data_type> s2(s1.begin(),s1.end())
Creates a copy s2 of set s1 using iterators

Some of the member functions of set are:

•begin():It is a function which returns an iterator pointing to the first element of the set.Its time complexity is O(1).
Syntax:
set_name.begin()

•end():It is a function which returns an iterator pointing to next to the last element of the set.Its time complexity is O(1).
Syntax:
set_name.end()

•insert():It inserts new elements in the set passed as parameter.Its time complexity is O(logN) where N is the size of the set.
Syntax:
set_name,insert(val)

•count():It returns 1 if the element passed as parameter is present otherwise 0.Its time complexity is O(logN) where N is the size of the set.
Syntax:
set_name.count(val)

•find():It returns the iterator pointing to the position where the value passed as parameter is present.If the value is not present in the set then it returns iterator pointing to s.end()
where s is the name of the set.Its time complexity is O(logN) where N is the size of the set.
Syntax:
set_name.find(val)

•erase():Deletes a particular element or a range of elements from the set. Its time complexity is O(N) where N is the number of elements deleted.
Syntax to remove element at position pos:
set_name.erase(pos)
Syntax to remove elements from a given range [pos1,pos2):
set_name.erase(pos1,pos2)

•empty():Returns true if the set is empty and false if the set has at least one element. Its time complexity is O(1).
Syntax:
set_name.empty()

•clear():Deletes all the elements in the set and the set will be empty. Its time complexity is O(N) where N is the size of the set.
Syntax:
set_name.clear()

•size():It returns the number of elements in the set. Its time complexity is O(1).
Syntax :
set_name.size()

Implementation:

Multiset is a set container which has all the functions same as that of set but with an exception that it can hold the same value multiple times.

Syntax for creating a multiset:
multiset<data_type> multiset_name

Some of the member functions of set are:

•begin():It is a function which returns an iterator pointing to the first element of the multiset.Its time complexity is O(1).
Syntax:
set_name.begin()

•end():It is a function which returns an iterator pointing to next to the last element of the multiset.Its time complexity is O(1).
Syntax:
set_name.end()

•insert():It inserts new elements in the multiset passed as parameter.Its time complexity is O(log N) where N is the size of the multiset.
Syntax:
set_name.insert(val)

•count():It returns the count of numbers of elements whose values are equal to the value passed as parameter.Its time complexity is O(log N) where N is the size of the multiset.
Syntax:
set_name.count(val)

•find():It returns the iterator pointing to the position where the value passed as parameter is present.If the value is not present in the set then it returns iterator pointing to s.end()
where s is the name of the multiset.Its time complexity is O(log N) where N is the size of the size of the multiset.
Syntax:
set_name.find(val)

•erase():Deletes a particular element or a range of elements from the set. Its time complexity is O(N) where N is the number of elements deleted.
Syntax to remove element at position pos:
set_name.erase(pos)
Syntax to remove elements from a given range [pos1,pos2):
set_name.erase(pos1,pos2)

•empty():Returns true if the set is empty and false if the set has at least one element. Its time complexity is O(1).
Syntax:
set_name.empty()

•clear():Deletes all the elements in the set and the set will be empty. Its time complexity is O(N) where N is the size of the set.
Syntax:
set_name.clear()

•size():It returns the number of elements in the set. Its time complexity is O(1).
Syntax :
set_name.size()

Implementation:

It is an associative container that contains an unordered set of data inserted randomly. Each element may occur only once, so duplicates are not allowed. A user can create an unordered set by inserting elements in any order and an unordered set will return data in any order i.e. unordered form.The main reasons when unordered set can be used are when no sorted data is required means the data is available in an unordered format,when only unique data is needed,when we want to use hash table instead of a binary search tree and when a faster search is required as it take O(1) in average case and O(n) in worst case.
One must include <unordered_set> header file to use unordered_set.

Syntax for creating unordered_set:

unordered_set<int> s; //creates an empty unordered set
unordered_set<int> s={1,2,3,4}; //creates an unordered set containing 1,2,3 and 4

Some of the member functions of set are:
begin():It is a function which returns an iterator pointing to the first element of the unordered set.Its time complexity is O(1).
Syntax:
unordered_set_name.begin()
end():It is a function which returns an iterator pointing to next to the last element of the unordered set.Its time complexity is O(1).
Syntax:
unordered_set_name.end()
insert():It inserts new elements in the unordered set passed as parameter.Its time complexity is O(1) in average case but O(N) in worst case where N is the size of the unordered set.
Syntax:
unordered_set_name,insert(val)
count():It returns 1 if the element passed as parameter is present otherwise 0.Its time complexity is O(1) in average case but O(N) in worst case where N is the size of the unordered set.
Syntax:
unordered_set_name.count(val)
find():It returns the iterator pointing to the position where the value passed as parameter is present.If the value is not present in the unordered set then it returns iterator pointing to s.end() where s is the name of the set.Its time complexity is O(1) in average case but O(N) in worst case where N is the size of the unordered set.
Syntax:
unordered_set_name.find(val)
erase():Deletes a particular element or a range of elements from the unordered set. Its time complexity is O(N) where N is the number of elements deleted.
Syntax to remove element at position pos:
unordered_set_name.erase(pos)
Syntax to remove elements from a given range [pos1,pos2):
unordered_set_name.erase(pos1,pos2)
empty():Returns true if the unordered set is empty and false if the unordered set has at least one element. Its time complexity is O(1).
Syntax:
unordered_set_name.empty()
clear():Deletes all the elements in the unordered set and the unordered set will be empty. Its time complexity is O(N) where N is the size of the unordered set.
Syntax:
unordered_set_name.clear()
size():It returns the number of elements in the unordered set. Its time complexity is O(1).
Syntax :
unordered_set_name.size()

Implementation:

Unordered Multiset:
Unordered multiset is an associative container that contains a set of possibly non-unique objects of type Key. Search, insertion, and removal have average constant-time complexity.
Internally, the elements are not sorted in any particular order, but organized into buckets. Which bucket an element is placed into depends entirely on the hash of its value.This allows fast access to individual elements, since once hash is computed, it refers to the exact bucket the element is placed into.
One must include <unordered_set> header file to use multiset.

Syntax for creating unordered_multiset:

                                                        
unordered_multiset<int> s;     //creates an empty unordered multiset
unordered_multiset<int> s={1,2,3,4};   //creates an unordered multiset containing 1,2,3 and 4
                                                    

Some of the member functions of set are:
begin():It is a function which returns an iterator pointing to the first element of the unordered multiset.Its time complexity is O(1).
Syntax:
unordered_multiset_name.begin()
end():It is a function which returns an iterator pointing to next to the last element of the unordered multiset.Its time complexity is O(1).
Syntax:
unordered_multiset_name.end()
insert():It inserts new elements in the unordered multiset passed as parameter.Its time complexity is O(1) in average case but O(N) in worst case where N is the size of the unordered multiset.
Syntax:
unordered_multiset_name,insert(val)
count():It returns the count of the element passed as parameter. Its time complexity is O(N) where N is the number of elements counted.
Syntax:
unordered_multiset_name.count(val)
find():It returns the iterator pointing to the position where the value passed as parameter is present.If the value is not present in the unordered multiset then it returns iterator pointing to s.end() where s is the name of the unordered multiset.Its time complexity is O(1) in average case but O(N) in worst case where N is the size of the unordered multiset.
Syntax:
unordered_multiset_name.find(val)
erase():Deletes a particular element or a range of elements from the unordered multiset. Its time complexity is O(N) where N is the number of elements deleted.
Syntax to remove element at position pos:
unordered_multiset_name.erase(pos)
Syntax to remove elements from a given range [pos1,pos2):
unordered_multiset_name.erase(pos1,pos2)
empty():Returns true if the unordered multiset is empty and false if the unordered multiset has at least one element. Its time complexity is O(1).
Syntax:
unordered_multiset_name.empty()
clear():Deletes all the elements in the unordered multiset and the unordered multiset will be empty. Its time complexity is O(N) where N is the size of the unordered multiset.
Syntax:
unordered_multiset_name.clear()
size():It returns the number of elements in the unordered multiset. Its time complexity is O(1).
Syntax :
unordered_multiset_name.size()

Implementation:

Maps are associative containers that store elements in a mapped fashion. Each element has a key value and a mapped value. Here key values are used to uniquely identify the elements mapped to it. The data type of key value and mapped value can be different. Elements in the map are always in sorted order by their corresponding key and can be accessed directly by their key using bracket operator ([ ]).
One must include <map> header file to use the map

Declaration of map:

                                                        
map<char,int> m;     //creates map m where key is char type and value is int type
m[‘a’]=2;                   //assign 2 to key a
                                                    

Some Member Functions of map:

begin( ): returns an iterator(explained above) referring to the first element of map.Its time complexity is O(1).
Syntax:
map_name.begin()
insert( ): insert a single element or the range of elements in the map.Its time complexity is O(logN)where N is the number of elements in the map, when only element is inserted and O(1) when position is also given.
Syntax:
map_name.insert({key,element})
end( ): It returns an iterator referring to the theoretical element(doesn’t point to an element) which follows the last element.Its time complexity is O(1).
Syntax:
map_name.end()
count( ):It searches the map for the elements mapped by the given key and returns the number of matches.As map stores each element with unique key, then it will return 1 if match if found otherwise return 0.Its time complexity is O(logN) where N is the number of elements in the map.
Syntax:
map_name.count(k) //k is the key
find( ): It searches the map for the element with the given key, and returns an iterator to it, if it is present in the map otherwise it returns an iterator to the theoretical element which follows the last element of map.Its time complexity is O(logN) where N is the number of elements in the map.
Syntax:
map_name.find(key)
clear( ): It clears the map, by removing all the elements from the map and leaving it with its size 0.Its time complexity is O(N) where N is the number of elements in the map.
Syntax:
map_name.clear()
empty( ): It checks whether the map is empty or not. It doesn’t modify the map.It returns 1 if the map is empty otherwise returns 0.Its time complexity is O(1).
Syntax:
map_name.empty()
erase( ): It removes a single element or the range of elements from the map.
Syntax for erasing a key:
map_name.erase(key)
Syntax for erasing the value from a particular position pos:
map_name.erase(pos)
Syntax for erasing values within a given range [pos1,pos2):
map_name.erase(pos1,pos2)

Implementation:

Multimap is an associative container that contains a sorted list of key-value pairs, while permitting multiple entries with the same key. Sorting is done according to the comparison function Compare, applied to the keys. Search, insertion, and removal operations have logarithmic complexity.
One must include <map> header file to use multimap.

Syntax to create multimap:

multimap<int,int> m1;
Creates empty multimap m1 that stores key and mapped value both of int data type.
multimap<int,int> m2={{1,20},{2,50}};
Creates initialised multimap m2
multimap<int,int> m3(m2.begin(),m2.end());
Creates a copy of multimap m2 using iterators.
multimap<int,int> m4=m2;
Creates a copy of multimap m2

Some Member Functions of map:

begin( ): It returns an iterator(explained above) referring to the first element of multimap.Its time complexity is O(1).
Syntax:
multmap_name.begin()
insert( ):It inserts a single element or the range of elements in the multmap.Its time complexity is O(logN)where N is the number of elements in the map, when only element is inserted and O(1) when position is also given.
Syntax:
multmap_name.insert({key,element})
end( ): It returns an iterator referring to the theoretical element(doesn’t point to an element) which follows the last element.Its time complexity is O(1).
Syntax:
multmap_name.end()
count( ):It searches the multmap for the elements mapped by the given key and returns the number of matches..Its time complexity is O(logN) where N is the number of elements in the map.
Syntax:
multmap_name.count(k) //k is the key
find( ): It searches the multmap for the element with the given key, and returns an iterator to it, if it is present in the multimap otherwise it returns an iterator to the theoretical element which follows the last element of the multmap.Its time complexity is O(logN) where N is the number of elements in the multimap.
Syntax:
multmap_name.find(key)
clear( ): It clears the multimap, by removing all the elements from the multmap and leaving it with its size 0.Its time complexity is O(N) where N is the number of elements in the multimap.
Syntax:
multmap_name.clear()
empty( ): It checks whether the multimap is empty or not. It doesn’t modify the multimap.It returns 1 if the multimap is empty otherwise it returns 0.Its time complexity is O(1).
Syntax:
multimap_name.empty()
erase( ): It removes a single element or the range of elements from the multimap.
Syntax for erasing a key:
multimap_name.erase(key)
Syntax for erasing the value from a particular position pos:
multimap_name.erase(pos)
Syntax for erasing values within a given range [pos1,pos2):
multimap_name.erase(pos1,pos2)

Implementation:

Unordered maps are associative containers that store elements formed by the combination of a key value and a mapped value, and which allows for fast retrieval of individual elements based on their keys.In an unordered map, the key value is generally used to uniquely identify the element, while the mapped value is an object with the content associated to this key.Internally unordered_map is implemented using hash table, the key provided to map are hashed into indices of hash table that is why performance of data structure depends on hash function a lot but on an average the cost of search, insert and delete from the hash table is O(1).
One must include <unordered_map> header file to use unordered map.

Syntax to create unordered map are:

                                                        
unordered_map<data_type,data_type> unordered_map_name;
                                                    

Some Member Functions of map:

begin( ): It returns an iterator referring to the first element of unordered map.Its time complexity is O(1).
Syntax:
map_name.begin()
insert( ): insert a single element or the range of elements in the unordered map.Its time complexity is O(1) ,when only element is inserted and O(N) when N numbers of elements are inserted.
Syntax:
map_name.insert({key,element})
end( ): It returns an iterator referring to the theoretical element(doesn’t point to an element) which follows the last element.Its time complexity is O(1).
Syntax:
map_name.end()
count( ):It searches the map for the elements mapped by the given key and returns the number of matches.As unordered map stores each element with unique key, then it will return 1 if match if found otherwise return 0.Its time complexity is O(N) where N is the number of elements counted.
Syntax:
map_name.count(k) //k is the key
find( ): It searches the unordered map for the element with the given key, and returns an iterator to it, if it is present in the unordered map otherwise it returns an iterator to the theoretical element which follows the last element of the unordered map.Its time complexity is O(1) in average case but in worst case it is O(N) where N is the number of elements in the unordered map.
Syntax:
map_name.find(key)
clear( ): It clears the unordered map, by removing all the elements from the unordered map and leaving it with its size 0.Its time complexity is O(N) where N is the number of elements in the unordered map.
Syntax:
map_name.clear()
empty( ): It checks whether the unordered map is empty or not. It doesn’t modify the unordered map.It returns 1 if the unordered map is empty otherwise it returns 0.Its time complexity is O(1).
Syntax:
map_name.empty()
erase( ): It removes a single element or the range of elements from the unordered map.
Syntax for erasing a key:
map_name.erase(key)
Syntax for erasing the value from a particular position pos:
map_name.erase(pos)
Syntax for erasing values within a given range [pos1,pos2):
map_name.erase(pos1,pos2)

Implementation:

Unordered multimaps are associative containers that store elements formed by the combination of a key value and a mapped value, much like unordered map containers, but allowing different elements to have equivalent keys.In an unordered_multimap, the key value is generally used to uniquely identify the element, while the mapped value is an object with the content associated to this key. Types of key and mapped value may differ.

Internally, the elements in the unordered_multimap are not sorted in any particular order with respect to either their key or mapped values,

Syntax to create unordered multimap:

                                                        
unordered_multimap<data_type,data_type> map_name;
                                                    

Some Member Functions of map:

begin( ): It returns an iterator(explained above) referring to the first element of unordered multimap.Its time complexity is O(1).
Syntax:
map_name.begin()
insert( ):It inserts a single element or the range of elements in the unordered multmap.Its time complexity is O(N) where N is the number of elements inserted.
Syntax:
map_name.insert({key,element})
end( ): It returns an iterator referring to the theoretical element(doesn’t point to an element) which follows the last element.Its time complexity is O(1).
Syntax:
map_name.end()
count( ):It searches the unordered multmap for the elements mapped by the given key and returns the number of matches..Its time complexity is O(N) where N is the number of elements counted.
Syntax:
map_name.count(k) //k is the key
find( ): It searches the unordered multmap for the element with the given key, and returns an iterator to it, if it is present in the unordered multimap otherwise it returns an iterator to the theoretical element which follows the last element of the unordered multmap.Its time complexity is O(1) in average case and O(N) in worst case where N number of elements in the unordered multimap.
Syntax:
map_name.find(key)
clear( ): It clears the unordered multimap, by removing all the elements from the unordered multmap and leaving it with its size 0.Its time complexity is O(N) where N is the number of elements in the unordered multimap.
Syntax:
map_name.clear()
empty( ): It checks whether the unordered multimap is empty or not. It doesn’t modify the unordered multimap.It returns 1 if the unordered multimap is empty otherwise it returns 0.Its time complexity is O(1).
Syntax:
map_name.empty()
erase( ): It removes a single element or the range of elements from the unordered multimap.
Syntax for erasing a key:
map_name.erase(key)
Syntax for erasing the value from a particular position pos:
map_name.erase(pos)
Syntax for erasing values within a given range [pos1,pos2):
map_name.erase(pos1,pos2)

Implementation:

Queues are a type of container adaptors which operate in a first in first out (FIFO) type of arrangement. Elements are inserted at the back (end) and are deleted from the front.

Link: https://www.recursionnitd.in/getting_started/getting_started/#subtopic47

Stacks are a type of container adaptors with LIFO(Last In First Out) type of working, where a new element is added at one end and (top) an element is removed from that end only.

Link: https://www.recursionnitd.in/getting_started/getting_started/#subtopic47

Priority queues are a type of container adapters, specifically designed such that the first element of the queue is the greatest of all elements in the queue and elements are in non increasing order (hence we can see that each element of the queue has a priority {fixed order}).

Link:

Deques are sequence containers with dynamic sizes that can be expanded or contracted on both ends (either its front or its back).It manages its elements with a dynamic array,provides random access,and has almost the same interface as a vector.The difference is that with deque
the dynamic array is open at both ends making it fast for insertions and deletions at both the end and the beginning.
To use deque one must include a <deque> header file .

Declaration of deque:

                                                        
deque<int> dq;        //creates empty deque d that can store int values.
                                                    

Some of the functions of deque are:

•begin():It returns an iterator pointing to the first element of the deque.Its time complexity is O(1).
Syntax:
deque_name.begin()

•end():It returns an iterator pointing to next to the last element of the deque.Its time complexity is O(1).
Syntax:
deque_name.end()

•insert():It inserts an element and returns to the first of the newly inserted element.It can be used in three different ways:
Syntax to insert new value val at position pos:
deque_name.insert(pos,val);
Syntax to insert n new elements of value val in the deque at position pos:
deque_name.insert(pos,n,val);
Syntax to insert new elements in the range [first, last) at position pos.
deque_name.insert ( pos, first, last)

•assign():It assigns new values to the deque destroying values of the previous deque and assigning new one to it.
Syntax to insert val n number of times:
deque_name.assign(n, val)

•push_front():This function is used to push the element to the deque at front.Its time complexity is O(1).
Syntax:
deque_name.push_front()

•pop_front():This function is used to pop the element from the deque front.Its time complexity is O(1).
Syntax:
deque_name.pop_front()

•pop_back():This function is used to pop the element from the deque back.Its time complexity is O(1).
Syntax:
deque_name.pop_front()
push_back():This function is used to push the element to the deque at front.Its time complexity is O(1).
Syntax:
deque_name.push_front()

•front():It returns the first element of the deque container.
Syntax:
deque_name.front()

•back():It returns the last element of the deque container.
Syntax:
deque_name.back()

•size():This returns the number of the elements present in the deque.Its time complexity is O(1).
Syntax:
deque_name.size()

•at():This function is used to reference the element present at the position given as the parameter to the function.Its time complexity is O(1).
Syntax to fetch element at position pos:
deque_name.at(pos)

•erase():It is used to remove elements from a container from the specified position or range passed as parameters.Its time complexity is O(N) where N is the number of elements deleted.
Syntax:
deque_name.erase(pos)

•clear():It clears all the elements of the deque container and destroys them.Its time complexity is O(N) where N is the number of elements in the deque.
Syntax:
deque_name.clear()

•empty():It is a function used to check whether the deque is empty or not.It returns 1 if the deque is empty otherwise returns 0.Its time complexity is O(1).
Syntax:
deque_name.empty()

•resize():This function alters the size of the deque container and resize it to n.If the value of n is greater than that of the current size of the container then new elements are inserted at the end of the deque.If the value of the n is less than the current size of the deque then the extra elements are destroyed.Its time complexity is O(N) where N is the number of elements inserted or removed.
Syntax:
deque_name.resize(n)

•operator[]:This operator is used to reference the element present at position given inside the operator.Its time complexity is O(1).
Syntax:
Deque_name[pos]

Implementation:

What is a Graph:

In theoretical Computer Science and Discrete Mathematics, a graph is a set of points(vertices) that may or may not contain data connected by a set of lines(edges), which again may or may not contain data.

A Graph may look like this.

The graph above doesn’t have data stored inside the edges. But some other graphs may have.

The lines can be visualized as “relationships” between any two vertices.

Vertices are often referred to as nodes in a graph.

Terms Used in Graphs:

Since we will be dealing with many complex methods on graphs in further, we need to define some basic terms which we will use there.

1. Node:
A node is basically a point or a circle (it may be represented as some other shape as well). It is the fundamental unit from which a graph is made of. A node can contain data as per requirement.

2. Degree:
Degree is defined for some node in a graph. The degree of a particular node is the number of edges incident on that node.

3. Adjacency:
Adjacency is a property satisfied by two nodes. Two nodes satisfy this property if they are adjacent. Two nodes are adjacent if and only if there is an edge connecting them. Adjacent nodes are also termed as neighbors.

4. Edge:
An edge is represented as a straight line that connects two nodes. This line may represent a unidirectional or bidirectional connection. We draw a simple line for bidirectional connection and a line with an arrow symbol on one of the ends for a unidirectional connection. A unidirectional edge is also termed as a directed edge, and a bidirectional edge is termed as undirected edge.

5. Multiple Edges:
A graph is said to have multiple edges if there exist some pairs of nodes such that there are more than one edges that connect these two nodes. In case of directed edges, there has to be more than one edge that connects the first node to the second node or vice versa. These edges are also called parallel edges.

6. Path :
A path is a sequence of one or more edges that, if followed, will take us from one node to some other node in the graph. The sequence of edges hence formed has to be connected. In other words, for any two adjacent edges in the path, there should be a node in the graph such that the first edge is an incoming edge for it and the second edge is an outgoing one. The number of edges in the path is the length of the path. In a graph with additional information on the edges (or weights), the path length(weight) may be considered as the sum of lengths(weights) of edges involved in the path.

7. Cycle:
A cycle is a path that begins and ends on the same node. A cycle of length one is called a loop (i.e a node connected to itself).

Visualization of Graphs:

Understanding graphs by theoretical definitions may be difficult at times.

So here is a simple explanation that would help you understand graphs.
Consider the following connection of different cities by roads.

All the cities can be considered as nodes and the roads connecting them as edges. All nodes have data that represents the name of the city. All edges have data that represents the length of the road.

A path from one city to another city(one node to another node) is a connected sequence of roads(edges). The length of a path is the number of roads(edges) in it. And the distance between two cities(nodes) is the sum of the lengths of roads involved in the path connecting these cities.

All the roads(edges) are two-way (bidirectional/undirected) in this graph.

If some road is one way only, we may need to provide additional data about the direction of the roads (usually represented as an arrow).

Classification of graphs

Graphs can be classified in many aspects.
Here a few very common classifications of Graphs:

1. Null Graph :

Graphs having no edges are termed as Null Graphs. A null graph with just one vertex is called a Trivial Graph.

4. Directed Graph:

Graphs having directed edges are called directed graphs.
In other words, The relationship between any two nodes is unidirectional. A simple example is a one-way road. A directed graph is often referred to as a Digraph.

5. Undirected Graph:

Graphs having simple/undirected edges are called undirected graphs. A connection between any two nodes is bidirectional in nature. A simple example is a two-way road.

Unless mentioned, a graph is by convention considered as undirected.

6. Weighted and Unweighted Graphs:

A weighted graph is a graph that has data present on the edges, whereas an unweighted graph doesn’t.

7. Simple Graph:

A simple graph is also called a strict graph. A simple graph is an unweighted undirected graph with no loops or multiple edges.

8. Multigraph:

A graph having multiple edges and self-loops is called a Multi Graph.

9. Tree :

A tree is a connected, acyclic, and undirected graph. The tree is a very special variant of graphs. In a tree, the path from a node to any other node is unique. In a tree with n nodes, the number of edges is always equal to n-1.

10. Sub Graph :

A subgraph of some graph(parent) is defined as a graph whose vertices and edges are a subset of the parent graph.

11. Spanning and Induced Subgraph :

A spanning subgraph of some graph(parent) is a subgraph, which consists of all the vertices of the parent graph.
And an induced subgraph is the one having all the edges of the parent graph.

12. Spanning Tree :

A spanning tree of a graph is a spanning subgraph which is also a tree.

A spanning tree of a weighted graph, which has a minimum total weight of edges is also called Minimum Spanning Tree.

13. Bipartite Graph :

A bipartite graph is a graph in which it is possible to divide the vertices into two disjoint sets U and V such that every edge in the graph connects a vertex in U with a vertex in V and no edge connects a vertex to another vertex in the same set.

If for a vertex in a particular set, there is an edge connecting it with every vertex in the other set, then this bipartite graph is called Complete Bipartite Graph. A complete bipartite graph looks like the following.

Representation of Graphs

By now, we know that graphs are a collection of vertices and edges. But we have not seen how we can store and use them as a data type. There are different ways to optimally represent a graph, depending on the density of its edges, type of operations to be performed, and ease of use.

In General Programming, we have two major types of representations of graphs.

1. Adjacency Matrix Representation.
2. Adjacency List Representation.

We need these representations in order to store graphs in computer memory.

Adjacency Matrix Representation:

In this type of representation, we use a nXn matrix to store the information about the edges of the graph. The nXn matrix provides us a place to store all possible edges (which indeed are equal to n2) between n nodes.

More formally -

Adjacency Matrix representation is a sequential representation.
It is used to represent the information about two nodes that have an edge between them.
In this representation, we have a nXn matrix, where if we have an edge from node i to node j, then the element in the ith row and jth column is 1 and otherwise 0. In the case of weighted graphs, we can also store the value of the weight of the edge in that matrix element.

For example, the graph shown below can have a matrix representation that looks like the one given on its right.

For a weighted graph, the representation looks like this -

Implementation of Adjacency Matrix Representation (in c++)

In c++, the adjacency matrix representation of graphs is done by using a 2-Dimensional Array of size nXn, where n is the number of nodes in the graph.

int adj[n+1][n+1]; // n+1 for 1-indexing

After declaring the matrix (or 2-D array), once we receive any information about an edge, we simply add it to the matrix.

Let say, we have m edges in our graph, and each edge is given input in this format,
a b

Where a and b are the node numbers of nodes that are the endpoints of this edge. So, the code for matrix filling would look like.

Adjacency List Representations:

We have seen Adjacency List implementation for representing a graph. But as we can notice, the number of edges in a graph may not always be close to n2. In real life implementations and in most of the problems in Competitive Programming, the graphs are sparse. In other words, the number of edges in a graph is close to O(n).

Adjacency List is an array of lists, where the list present at the ith index is the list of nodes that are adjacent or reachable from node i. Below is a visualization of adjacency list.

Graph Traversals

We already know about representation of graphs and how to store data with help of graphs.
Since graph is a linked data structure, we will now learn how to traverse a graph, or search in a graph.
A graph traversal is a method of visiting each vertex in a graph, starting from a source vertex. The order in which the traversal algorithm visits the nodes in the graph is important and may depend on the problem you are solving. Each vertex is visited exactly once in a traversal algorithm.

There are two major graph traversal algorithms:

Breadth First Search (BFS)
Depth First Search (DFS)

1. Breadth-First Search :

In Breadth-First Search traversal of the graph, we start from a source vertex and we visit all the nodes that are at a distance of one unit from the source, and then we visit all the nodes that are at a distance of two units from the source and then at a distance of three and so on.

This kind of traversal can be visualized as a social network, where we begin from a person (considered to be the source) and then we visit all the friends of this person then we visit all the friends of friends of this person and so on.

Since we will need to have a track of which node to visit first, we will use a
list of nodes yet to be visited and add nodes to this list. Initially, the source node will be added to the list as we begin the depth-first search.

For implementation purposes, we use queue data structure to play the role of the list of nodes yet to be visited. So, the algorithm becomes simple.

1. Create a queue of integers to store the node numbers of nodes yet to be visited.
2. Push the source into the queue.
3. While there are some elements in the queue, extract the first element of the queue and store it in some variable say node, currently you are at this node, goto step 4. If the queue is empty, goto step 5.
4. Push all the unvisited adjacents of node into the queue, mark them as visited and goto step 3.
5. Bfs Traversal is completed.

To keep track of already visited nodes, we use an auxiliary array. If the value at ith index of the array is 1, the ith node is visited else no. We initialize this array by 0.

int visited[N+1]={0};

We will use adjacency list representation.

vector<int> adj[N+1];

Here is the implementation for the same.

                                                        
void bfs(int source)
{
  queue<int> q;
  q.push(source);
  visited[source]=1;
  // step 1 and 2 complete
  while(!q.empty())
  {
    int node = q.front();
    q.pop();
    //we extract the front node of the queue

    cout<<node<<" "; // we print the node on the screen

    for (int adjacent : adj[node])
    {
      if(visited[adjacent]==0) //we skip all visited adjacents
      {
        visited[adjacent]=1;
        q.push(adjacent);
      }
    }
    // step 4 complete
  }
  // our bfs traversal is complete
}
                                                    

Analysis of BFS traversal:

Considering |V| as the number of vertices and |E| as the number of edges in the graph.
The time complexity of this algorithm is O(|V|+|E|) as we traverse every vertex and edge at most once.
Auxiliary space required by this algorithm is O(|V|) as the queue can have |V|-1
vertices in it at once in the worst case.

2. Depth First Search:

In Depth First Search of a graph, we start from a source vertex and mark it as visited. Now, we move to its unvisited adjacents one by one and repeat this process. In this way, we traverse the depth of the graph first, rather than traversing the breadth. Here is a simple visualization of the same.

The algorithm is as follows.

Let's say that dfs function is called for a particular node.
First, mark this node as visited.
Now iterate over all its adjacents.
If a node is already visited, skip it. Else call dfs for this adjacent.
Once we exit the iteration, the dfs function returns.

We will use an adjacency list representation and a visited array.

vector<int> adj[N+1];
int visited[N+1]={0};

Implementation of DFS.

0-1 BFS

0-1 BFS is a special kind of BFS traversal done on a weighted graph, where the weights on the edges can be one of two values, 0 and 1. And we have to find the weight of the shortest path from source vertex to every other vertex.

A simple example of a 0-1 weighted graph is shown below.

In normal BFS, when we reach a node, we push its adjacent nodes in the back of the queue because they are one level below the current node. But in this case, the nodes having edge weight 0 between them are actually at the same level! So we push those nodes on the front of the queue and that’s it, our 0-1 BFS Algorithm is complete.

Algorithm

1. Start from a source vertex, push it into the queue and mark it as visited. And its distance is zero.

2. While the queue is not empty, pop a node from the front of the queue and goto step 3. If the queue is empty, goto step 4.

3. For all unvisited adjacents of this node, if the edge weight is 0, push the node in the front of the queue and set the distance of this node as same as distance of the popped node else push it in the back of the queue and set the distance one more than the distance of the popped node. Mark this node as visited and goto step 2.

4. Our 0-1 BFS traversal is complete.

We will use adjacency list representation with weight information and an auxiliary array for keeping track of visited nodes. For the purpose of pushing in front of the queue, we will use a deque data structure, instead of queue data structure. We use another auxiliary array to store the final distance of ith node from the source vertex.

vector<pair<int,int>> adj[N+1];
int visited[N+1]={0};
deque<int> q;

Implementation of 0-1 BFS.

                                                        
void zero_one_bfs(int source) 
{
  deque<int> q;
  // initialize a double ended queue
  q.push_back(source);
  visited[source]=1;
  // step 1 complete

  while(!q.empty()){ // step 2 begins
    int node = q.front();
    q.pop_front();

    cout<<node<<" "; // we print the node on the screen
    for(pair<int, int> info : adj[node])
    {
      int adjacent = info.first;
      int weight = info.second;
      // extract the adjacency information

      if(visited[adjacent]==0){ // we skip all visited adjacents
        if(weight==0){
          q.push_back(adjacent);
        }
        else {
          q.push_back(adjacent);
        }
        visited[adjacent]=1;
      }
        // step 3 complete
    }
  }
}
                                                    

Analysis of 0-1 BFS :

This algorithm is no different from a normal BFS algorithm. The key implementation difference is the double-ended queue.

Hence the time complexity of this algorithm is O(|V|+|E|) and space complexity is O(|V|).

Connectivity in Graphs

Graphs are based on connection of several different points with each other. These points are kept on a plane and a line is drawn between any two points to connect them.
Since a very important aspect of a graph is connection, we define the connectivity of a graph as follows.

Connectivity is a basic concept of graph theory, it defines whether a graph is connected or not.
A graph is said to be connected if it is possible to traverse from any vertex to every other vertex by following a sequence of connected edges.

A graph is said to be disconnected if there exists a pair of vertices such that there is no path between them.

Let’s now define some terms related to graph connectivity.

1. Connected Component:

A connected component of a graph is a maximal connected subgraph of it. A maximal connected subgraph is a subgraph which cannot be further expanded to include more nodes of it’s parent node. Two connected components of a graph cannot be connected within themselves, in other words, the connected components of a graph are disjoint. The union of all connected components forms, the set of all vertices, i.e. the graph. A connected graph is a connected component of itself.

2. Cut Vertex:

A cut vertex is defined for a connected graph. It is a vertex, removal of which results in the connected graph being disconnected.

3. Cut Edge (Bridge):

A cut Is also defined for a connected graph. It's an edge, the removal of which results in the graph being disconnected.

4. Cut Set:

If deleting a certain number of edges in a graph makes it disconnected then those deleted edges is called a cut set of the graph. The removal of some but not all edges of the cut set does not disconnect the graph.

5. Edge Connectivity:

It is the minimum number of edges whose removal makes it disconnected. In other words it is the minimum size of the cut set of the graph.

6. Vertex Connectivity:

It is the minimum number of vertices that need to be removed from the graph to make it disconnected.

Connected Component Algorithms:

Finding the connected components of a given graph can be done algorithmically. We use normal BFS or DFS traversal to find the connected components of a graph. We need an auxiliary array to keep track of the visited nodes. The algorithm is as follows.

1. Iterate on every node from 1 to N.

2. If the note is visited then skip to the next node. Else go to step 3.

3. Cal DFS or BFS traversal for that particular node and print a new line character.

4. As we exit the iteration, we have counted all connected components of the graph.

We are going to need an auxiliary array to keep track of visited nodes and an adjacency list representation of the graph. We will be using the traverse() function, the internal implementation of which may either be BFS or DFS.

int visited[N+1];
vector<int> adj[N+1];
void traverse(int source);

Here is the implementation.

Cycle Detection in graphs

Graphs are a connection of points with help of some lines. Each relation between any two points is independent of the relation between some other pair of points. In such cases, the edges are added independently.

We define a path as a sequence of edges that takes us from a point to another point in the graph. But since the edges are added independently, we can have a path that has a non-zero length and it starts and terminates at the same point. We call this a cycle. The only repeated vertices in the cycle must be the first and the last vertices. Edges should not get repeated.

Cycle Detection in Undirected Graphs:

A cycle represents a path that starts and ends at the same vertex. To check if there is a cycle in an undirected graph, we will need to check if we can reach a vertex, starting from another vertex using some path that has no-zero length and doesn’t contain repeating edges.

We can easily achieve this using a simple BFS/DFS traversal algorithm. In each of the above mentioned traversals, we have an auxiliary array that keeps track of already visited nodes. But the question is how we come to know about the existence of a cycle?

The answer is pretty simple. While in the traversal, checking for the adjacent nodes of the node we are currently at, if we encounter a node that is already visited but is not a parent of the current node, this is a cycle! The proof is quite intuitive and simple. Consider a simple path that connects two points in a graph. This path is not a cycle and connects two different points. The only thing that can make this path a cycle is an extra edge between it’s two endpoints. And that is exactly we are searching for. The algorithm is as follows.

Algorithm for cycle detection:
1. Start DFS/BFS traversal from any point in the graph.

2. While searching for unvisited adjacent nodes, if we encounter an already visited node, goto step 3.

3. Check if the node is the parent of the current node. If yes, go back to step 2, else go to step 4.

4. We have found a cycle.

For implementation purposes, we use an adjacency list, an auxiliary array to keep track of visited nodes.

vector<int> adj[N+1];
int visited[N+1];

DFS based algorithm:
In order to check if a node is the parent of some node in that particular traversal, we pass an extra parameter to the dfs function, named as par. This variable will store the information about the parent of the node we are currently at.

DFS based implementation of Cycle Detection Algorithm:

                                                        
bool isCyclic(int node, int par){
  // enter the DFS traversal

  visited[node]=1;

  for(int x: adj[node]){
    // check for all adjacent nodes

    if(visited[x]==1){ // as we encounter a visited node
      if(par==x) continue;
      // if the visited node is the parent of this node 
      // we can skip it

      // else we have detected a cycle
      return true;
    }
    if(dfs(x,node)) { //if we detect a cycle in DFS call
      // for a child
      return true; // then this DFS call must also return true
    }
  }
  // if no cycle found
  return false;
}
                                                    

For implementation purposes, we use adjacency list representation, an auxiliary array to keep track of visited nodes, and a queue of pairs to store the information about the parent of each node.

vector<int> adj[N+1];
int visited[N+1];
queue<pair<int,int>> q;

BFS based implementation :

                                                        
bool isCycle(int source){
  queue<pair<int, int>> q;

  q.push({source,source}); //we consider the parent of the 
  // source node as the source node itself

  while(!q.empty()){
    pair<int, int> p = q.front();
    q.pop();
    int node = p.first;
    int parent = p.second;
    for(int x:adj[node]){  //for all adjacents to the current node

      // if we encounter a visited node
      if(visited[x]){
        //if the node is the parent
        if(x==parent) continue;
        // else we found a cycle
        return true;
      }
      //else we push this node in the queue
      visited[x]=1;
      // the parent of x is node
      q.push({x, node});
    }
  }
  // if we traversed all the nodes and didn't find a cycle
  return 0;
}
                                                    

Analysis:

Both the BFS and DFS based algorithms have same time complexities as normal BFS and DFS algorithms.

Given a binary tree and two nodes x and y, find the lowest common ancestor.

Given below are a few examples:

Approach
The main approach is that we recursively search left and right for the two given nodes, i.e. x or y.
If we find either of the nodes, we return the node. Else if we do not find the node in a sub-tree, we return null.
After we are done searching both left and right subtrees of a node, we come across three possibilities:
1.If both left and right are not null – We found the LCA and return the LCA

2.If both left and right are null – We continue our search

3.If either left or right are not null –
3.a)If left is null, return the right node
3.b)If right is null, return the left node

Example

We start from the node having the value 3. Since it is not equal to either 4 or 6, we move to the left subtree (i.e. node 5). The same happens with the node 5 and we move further to the left side (i.e. node 6).
Now we find our first match and the left of node 5 stores node 6. …(a)
Moving to the right subtree of node 5, node 2 is also not equal to 6 or 4. Left of node 2 (i.e. node 7) returns null and right of node 2 (i.e. node 4) returns node 4 since we found out our second match.
Node 2 returns node 4 to the right of node 5. …(b)
Since both the left and right of node 5 are not null [by (a) and (b)], we found the LCA.
The entire tree will be traversed similarly, which will end up giving the final result as LCA(6,4) =5.

In a weighted undirected graph, let’s say there are V vertices and E edges
[ G = ( V,E ) ]. So minimum spanning tree is a subgraph of a graph that is a tree and it connects all the vertices together besides having the least weight (i.e. the sum of weights of edges is minimal).

To get least weight , we want less no of edges. So for all the vertices to get connected, we require minimum (V - 1) edges in overall.

In Fig 1(a), there are 8 vertices and 10 edges and all vertices are connected. Fig 1(b) is a subgraph of graph 1(a) and it has 8 vertices and 7 ( 8 - 1 ) edges and we can clearly see that all vertices are connected with minimum no of edges.

If the above edges were weighted, we had to choose such a path such that the total weight is minimum and edges present in that subgraph is (V-1).

Prim's Algorithm

The minimum spanning tree is built gradually by adding edges one at a time.

At first the spanning tree consists only of a single vertex (chosen arbitrarily).

After that the spanning tree now consists of two vertices. Now we select the edge which is having the minimum weight and also,it must be outgoing from any of the selected 2 vertices.

And so on, i.e. every time we select and add the edge with minimal weight that connects one selected vertex with one unselected vertex. The process is repeated until the spanning tree contains all vertices (or equivalently until we have n−1 edges).

In the end the constructed spanning tree will be minimal. If the graph was originally not connected, then there doesn't exist a spanning tree, so the number of selected edges will be less than V−1.

So minimum weight spanning tree is 5 + 5 + 4 + 3 = 17.

Dense graphs: O(n²) [ n : vertices ]

                                                        
int n; //no of vertices
vector<vector<int>> adj; // adjacency matrix of graph
const int INF = 1000000000; // weight INF means there is no edge
 
struct Edge {
    int w = INF, to = -1;
};
 
void prim() {
 
    int total_weight = 0;
 
    vector<bool> selected(n, false); // no vertex selected yet
    vector<Edge> min_e(n);
 
    min_e[0].w = 0;
 
    for (int i = 0; i < n; ++i) {
 
        int v = -1;
        for (int j = 0; j < n; ++j) {
 
            if (!selected[j] && (v == -1 || min_e[j].w < min_e[v].w))
                v = j;
        }
 
        if (min_e[v].w == INF) 
        {
            cout << "No Minnimum Spanning Tree!" << endl;
            exit(0);
        }
 
        selected[v] = true;
        total_weight += min_e[v].w;
        
        if (min_e[v].to != -1)
            cout << v << " " << min_e[v].to << endl;
 
        for (int to = 0; to < n; ++to) {
            if (adj[v][to] < min_e[to].w)
                min_e[to] = {adj[v][to], v};
        }
    }
 
    cout << total_weight << endl;
}
                                                    

Sparse graphs: O(mlogn) [ n : vertices, m : edges ]

                                                        
const int INF = 1000000000;
 
struct Edge {
    int w = INF, to = -1;
    bool operator<(Edge const& other) const {
 
        return make_pair(w, to) < make_pair(other.w, other.to);
    }
};
 
int n;
vector<vector<Edge>> adj;
 
void prim() {
    int total_weight = 0;
    vector<Edge> min_e(n);
    min_e[0].w = 0;
    set<Edge> q;
    q.insert({0, 0});
    vector<bool> selected(n, false);
    for (int i = 0; i < n; ++i) {
        if (q.empty()) {
            cout << "No MST!" << endl;
            exit(0);
        }
 
        int v = q.begin()->to;
        selected[v] = true;
        total_weight += q.begin()->w;
        q.erase(q.begin());
 
        if (min_e[v].to != -1)
            cout << v << " " << min_e[v].to << endl;
 
        for (Edge e : adj[v]) {
            if (!selected[e.to] && e.w < min_e[e.to].w) {
                q.erase({min_e[e.to].w, e.to});
                min_e[e.to] = {e.w, v};
                q.insert({e.w, e.to});
            }
        }
    }
 
    cout << total_weight << endl;
}
                                                    

Kruskal's algorithm

Firstly,all edges are sorted by weight (in non-decreasing order).

We pick all edges from the first to the last (in sorted order), and if the ends of the currently picked edge belong to different subtrees, these subtrees are combined, and the edge is added to the answer. After iterating through all the edges, all the vertices will belong to the same sub-tree, and we will get the answer.

Consider the following situation:

There are 10 locks- all possessing a strange property:
A lock might require few other locks to be unlocked before one can unlock it. You have been provided the dependencies of the locks and are asked to unlock all of them.

So, how to find an order to unlock all the locks, or to check if it is impossible to do so?

The kind of technique which should be employed to achieve such an order is termed as Topological Sorting.

In the above example, one approach could be to unlock all the locks firstly which does not depend on any other locks. Now the dependency of a few locks would have been reduced. Those that no longer require any other locks to be unlocked before them, can now be unlocked. We repeat the process until all the locks have been unlocked.
This implementation is similar to that of Kahn’s Algorithm.

Note: It might not always be possible to find a valid unlocking order for the locks.

Prerequisites for Topo(Topological) sort:
Basic knowledge on Graphs
Array Manipulation
(Optional)Knowledge of queue STL

Definition:
A topological sort is an ordering of the nodes of a directed graph such that if there is a path from node a to node b, then node a appears before node b in the ordering. For example, for the graph:

One possible topological order can be : 1,2,4,3,5
Here, every node is placed before a node with an edge directed towards it from that very node.

An acyclic graph always has a topological sort. However, if the graph contains a cycle, it is not possible to form a topological sort, because no node of the cycle can appear before the other nodes of the cycle in the ordering. It turns out that depth-first search can be used to both check if a directed graph contains a cycle and, if it does not contain a cycle, to construct a topological sort!

Algorithm:

The idea is to go through the nodes of the graph and always begin a depth-first search at the current node if it has not been processed yet. During the searches, the nodes have three possible states:
State 0:the node has not been processed.
State 1:th node is under processing.
State 2:the node has been processed.
Initially, the state of each node is 0. When a search reaches a node for the first time, its state becomes 1. Finally, after all successors of the node have been processed, its state becomes 2.
If the graph contains a cycle, we will find this out during the search, because sooner or later we will arrive at a node whose state is 1. In this case, it is not possible to construct a topological sort
If the graph does not contain a cycle, we can construct a topological sort by adding each node to a list when the state of the node becomes 2. This list in reverse order is a topological sort

Hence, we can draw the following conclusions with respect to topological sorting:

•Any node prior to a node after it in the ordering, cannot have a directed edge towards itself from that node.

•Topological sorting is applicable only for acyclic graphs.

For Example, Topological sort is not applicable for this graph,since there is a cycle in it.

While implementing our algorithm, we take us of the following states:
State 0:The nodes have yet not been visited.
State i -the nodes of this state are under process.
If we encounter any node of the same state while doing a depth first search, we can safely assume that the graph contains a cycle.

Implementation:

Kahn’s Algorithm:
Kahn’s Algorithm is another method for finding Topological sort of a directed acyclic graph(DAG).The algorithm provides an efficient method for finding the topological sort of a graph.
The algorithm works by finding vertices with no incoming edges and removing all outgoing edges from these vertices.

Algorithmic Steps:
The idea is to maintain in-degree information of all graph vertices, by storing them in an array/vector.
In-degree- Count of the number of incoming edges directed towards a vertex.

•The algorithm starts with a vertex having indeg=0.

•The edges directed from this vertex to other nodes are removed, by decreasing their indegrees by 1.

•Processes 1 and 2 are repeated until no vertices with 0 indegree is left.

•If the graph contained a cycle, it would still have edges remaining after the process ends.

Implementation:

Shortest path between two points implies the minimum summation of the edges connecting the given points.

Consider the following situation:
Suppose you are standing in city A, and you have to reach the city Z. Each of the cities named B to Y, have interconnecting passages of varying lengths. The distances are provided to you, but you want to reach Z travelling the shortest path possible.
This is actually a real-life application of shortest distance algorithms.

PREREQUISITES:

Knowledge about the different components of a graph- nodes,edges,weights of a graph.
Knowledge on STL containers like Priority Queue, Multisets, and/or queues,vectors.
Basic array manipulation

Algorithms:

1)Bellman-Ford Algorithm: This Algorithm is used to find the shortest distance from a source vertex to other nodes.
This algorithm uses different edges to reduce the distance of nodes from the vertex until it can no longer be reduced. Initially, the distances are initialised to a maximal value which can possibly not be an ans.(we’ll call it infinity or just inf.).
A very important use of this algorithm is to detect the presence of negative cycles.

Negative Cycles:
If the graph contains a negative cycle, we can shorten infinitely many times any path that contains the cycle by repeating the cycle again and again. Thus, the concept of a shortest path is not meaningful in this situation.
A negative cycle can be detected using the Bellman–Ford algorithm by running the algorithm for n rounds. If the last round reduces any distance, the graph contains a negative cycle. Note that this algorithm can be used to search for a negative cycle in the whole graph regardless of the starting node.

Algorithm steps:

•The outer loop traverses from 0 to n−1

•Loop over all edges, check if the next node distance > current node distance + edge weight, in this case update the next node distance to "current node distance + edge weight".
This algorithm depends on the relaxation principle where the shortest distance for all vertices is gradually replaced by more accurate values until eventually reaching the optimum solution. In the beginning all vertices have a distance of "Infinity", but only the distance of the source vertex = 0, then update all the connected vertices with the new distances (source vertex distance + edge weights), then apply the same concept for the new vertices with new distances and so on.

A diagrammatic representation of Bellman-Ford’s algorithm:

Implementation:

                                                        
struct edge
{
    int a, b, cost;
};

int n, m, v;
vector<edge> e;
const int INF = 1000000000;

void solve()
{
    vector<int> d (n, INF);
    d[v] = 0;
    for (int i=0; i<n-1; ++i)
        for (int j=0; j<m; ++j)
            if (d[e[j].a] < INF)
                d[e[j].b] = min (d[e[j].b], d[e[j].a] + e[j].cost);
    // display d, for example, on the screen
}
                                                    

Shortest Path Faster Algorithm (SPFA)
The SPFA algorithm is a variant of the Bellman–Ford algorithm that is often more efficient than the original algorithm.
The SPFA algorithm does not go through all the edges on each round, but instead, it chooses the edges to be examined in a more intelligent way.
The main idea is to create a queue containing only the vertices that were relaxed but that still could further relax their neighbors. And whenever you can relax some neighbor, you should put him in the queue. This algorithm can also be used to detect negative cycles as the Bellman-Ford.The efficiency of the SPFA algorithm depends on the structure of the graph: the algorithm is often efficient, but its worst case time complexity is still O(nm)
and it is possible to create inputs that make the algorithm as slow as the original Bellman–Ford algorithm.

Implementation: