# Algorithms

**Topics:**

## Basics

- Introduction to Algorithms.
- Algorithm and its types.
- Algorithm and its properties.
- Time Space Trade-Off of algorithms.
- Time and Space Analysis of Algorithm.

## Sorting Algorithms

- Introduction to Greedy Strategy in Algorithms
- Stability in sorting
- External Merge Sorting Algorithm
- Radix Sort and its Algorithm
- Bucket Sort Algorithm
- Bubble sort Algorithm, Flow Chart and C++ Code
- Insertion sort Algorithm, flowchart and C, C++ Code
- Merge Sort | One of the best sorting algorithms used for large inputs

## Searching Algorithms

- Binary Search in C, C++
- Randomized Binary Search
- Meta Binary Search | One-sided Binary Search
- Difference between Linear Search and Binary Search
- Binary Search in String
- Variants of Binary Search
- Sieve of Eratosthenes to find prime numbers
- Optimal Merge Pattern (Algorithm and Example)
- Given an array of n numbers, Check whether there is any duplicate or not
- Finding the missing number
- Find the number occurring an odd number of times
- Find the pair whose sum is closest to zero in minimum time complexity
- Find three elements in an array such that their sum is equal to given element K
- Bitonic Search Algorithm
- Check whether a number is Fibonacci or not
- Segregate even and odd numbers in minimum time complexity
- Find trailing zeros in factorial of a number
- Find Nearest Greatest Neighbours of each element in an array
- Interpolation search algorithm
- Floor and ceil of an element in an array using C++
- Two Elements whose sum is closest to zero
- Find a pair with a given difference
- Count number of occurrences (or frequency) in a sorted array
- Find a Fixed Point (Value equal to index) in a given array
- Find the maximum element in an array which is first increasing and then decreasing

## Dynamic programming

- Dynamic Programming (Components, Applications and Elements).
- Algorithm for fractional knapsack problem
- Algorithm and procedure to solve a longest common subsequence problem
- Dynamic Programming (Components, Applications and Elements)
- Find the Nth Fibonacci number | C++
- Longest Common Subsequence using Dynamic programming (DP)
- Longest Increasing Subsequence using Dynamic programming (DP)
- Find the maximum sub-array sum using KADANE'S ALGORITHM
- Non-intersecting chords using Dynamic Programming (DP)
- Edit Distance using Dynamic Programming (DP)
- Finding Ugly Number using Dynamic Programming (DP)
- Egg dropping problem using Dynamic Programming (DP)
- Wild card matching problem using Dynamic programming (DP)
- Compute sum of digits in all numbers from 1 to N for a given N
- Minimum jumps required using Dynamic programming (DP)

## Graph Algorithms

- Graph coloring problem's solution using backtracking algorithm
- Breadth First Search (BFS) and Depth First Search (DFS) Algorithms
- Travelling Salesman Problem
- Kruskal's (P) and Prim's (K) Algorithms
- Multistage graph problem with forward approach and backward approach algorithms
- Floyd Warshall algorithm with its Pseudo Code

## Backtracking Algorithms

- Backtracking (Types and Algorithms).
- 4 Queen's problem and solution using backtracking algorithm.
- N Queen's problem and solution using backtracking algorithm.

## Recursion

- Types of Recursion.
- Find the GCD (Greatest Common Divisor) of two numbers using EUCLID'S ALGORITHM
- Compute the value of A raise to the power B using Fast Exponentiation

## Algorithms Implementation

## Operating system algorithms

- Implementations of FCFS scheduling algorithm using C++.
- Implementation of Shortest Job First (SJF) Non-Preemptive CPU scheduling algorithm using C++.
- Implementation of Shortest Job First (SJF) Preemptive CPU scheduling algorithm using C++.
- Implementation of Priority scheduling (Pre-emptive) algorithm using C++.
- Implementation of Priority scheduling (Non Pre-emptive) algorithm using C++.
- Implementation of Round Robin CPU Scheduling algorithm using C++.
- Analysis of LRU page replacement algorithm and Belady's anomaly

## Misc.

- Branch and Bound
- Find the roots of a complex polynomial equation using Regula Falsi Method in C.
- Sieve of Eratosthenes to find prime numbers.
- Implementations of FCFS scheduling algorithm using C++.
- Implementation of Shortest Job First (SJF) Non-Preemptive CPU scheduling algorithm using C++.
- Implementation of Shortest Job First (SJF) Preemptive CPU scheduling algorithm using C++.
- Implementation of Priority scheduling (Pre-emptive) algorithm using C++.
- Divide and Conquer Paradigm (What it is, Its Applications, Pros and Cons).
- Implementation of Priority scheduling (Non Pre-emptive) algorithm using C++.
- Implementation of Round Robin CPU Scheduling algorithm using C++.
- Jump Search Implementation using C++.
- Optimal Merge Pattern (Algorithm and Example).
- Introduction to Greedy Strategy in Algorithms.
- Strassen's Matrix Multiplication in algorithms.
- Huffman Coding (Algorithm, Example and Time complexity).
- Backtracking (Types and Algorithms).
- 4 Queen's problem and solution using backtracking algorithm.
- N Queen's problem and solution using backtracking algorithm.
- Graph coloring problem's solution using backtracking algorithm.
- Tournament Tree and their properties.
- Deterministic and Non Deterministic Algorithms.
- Lower Bound Theory.
- Non Recursive Tree Traversal Algorithm.
- Line Drawing Algorithm.
- Breadth First Search (BFS) and Depth First Search (DFS) Algorithms.
- P and NP problems and solutions | Algorithms.
- Travelling Salesman Problem.
- 2 – 3 Trees Algorithm.
- Kruskal's (P) and Prim's (K) Algorithms.
- Algorithm for fractional knapsack problem.
- Algorithm and procedure to solve a longest common subsequence problem.
- Midpoint Circle Algorithm.
- Multistage graph problem with forward approach and backward approach algorithms.
- Floyd Warshall algorithm with its Pseudo Code.
- Reliability design problem.
- Removing consecutive duplicates from a string
- Fast Exponentiation using Bitmasking

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions