technojam/ultimate_algorithms_repository

This is a collection of Data Structures and Algorithms

DATA STRUCTURE AND ALGORITHMS(C++)

DISCLAMER

1. Knowing a programming language and DSA are two different things .

   eg. you might be knowing python , c, c++ , java etc but if you know DSA then you can implement them in any programming language with minor syntatic modifications.

2. This Repository does not intend to spoon feed , it can be used for studying in the right direction , but the efforts should be solely yours .

WHY ?

1. If you want to crack the interviews and get into the product based companies.
2. Nearly everything functional in computer science is an implementation of data structure along with certain algorithms
3. If you love to solve the real-world complex problems.

ROADMAP

1. 1-D Arrays
2. 2-D Arrays
3. Array ADT
4. Character Arrays
5. Strings
6. Pointers
7. Dynamic Memory Allocation
8. STL - ALGO'S
9. Sorting Algorithms
10. BINARY SEARCH
11. Vectors
12. Bit Manipulation
13. Number Theory
14. Recursion
15. Backtracking
16. Space and Time Complexities
17. OOP'S
18. Linked List
19. Stacks
20. Queues
21. Deque
22. Binary Tree
23. Binary Search Tree
24. Heaps
25. Hashing
26. Greedy Algorithms
27. Dynamic Programming
28. Graph
29. Segment Tree/Fenwick Tree

Contributing

When contributing to this repository, please first discuss the change you wish to make via issue, email, or any other method with the owners of this repository before making a change.

Please note we have a code of conduct, please follow it in all your interactions with the project.

Pull Request Process

1. Ensure that every PR is linked with an issue, all standalone PRs will be rejected by the maintainers.
2. Discuss all the features and requirements in issue section before sending an PR.
3. It would be really appreciated if you try to look into previous created issue instead of a new one.
4. Use proper template and be describe all the changes that you are addressing in a PR.
5. Add relevant comments explaining what the code is all about (if possible write the Time and Space complexities)
6. Any type pf plagrised code or fishy code will not be merged.
7. Once you follow above points and your PR gets approved by more than 2 reviewers it will be merged by the maintainers.

Code of Conduct

Our Pledge

In the interest of fostering an open and welcoming environment, we as contributors and maintainers pledge to making participation in our project and our community a harassment-free experience for everyone, regardless of age, body size, disability, ethnicity, gender identity and expression, level of experience, nationality, personal appearance, race, religion, or sexual identity and orientation.

Our Standards

Examples of behavior that contributes to creating a positive environment include:

• Using welcoming and inclusive language
• Being respectful of differing viewpoints and experiences
• Gracefully accepting constructive criticism
• Focusing on what is best for the community
• Showing empathy towards other community members

Examples of unacceptable behavior by participants include:

• The use of sexualized language or imagery and unwelcome sexual attention or advances
• Trolling, insulting/derogatory comments, and personal or political attacks
• Public or private harassment
• Publishing others' private information, such as a physical or electronic address, without explicit permission
• Other conduct which could reasonably be considered inappropriate in a professional setting

Contact Info

Feel free to contact us to discuss any issues, questions, or comments. Our contact info can be found on our GitHub page.

ultimate_algorithms_repository's Issues

Linked List

Title or Name of the Data Structure
A linked list is a linear data structure where each element is a separate object.
Linked list elements are not stored at contiguous location; the elements are linked using pointers.

Describe the Data Structure
Each node of a list is made up of two items - the data and a reference to the next node. The last node has a reference to null. The entry point into a linked list is called the head of the list. It should be noted that head is not a separate node, but the reference to the first node. If the list is empty then the head is a null reference.

Applications of Linked List

1. Image viewer – Previous and next images are linked, hence can be accessed by next and previous button.
   2.Previous and next page in web browser – We can access previous and next url searched in web browser by pressing back and next button since, they are linked as linked list.
2. Music Player – Songs in music player are linked to previous and next song. you can play songs either from starting or ending of the list.
   4.Implementation of stacks and queues
3. Implementation of graphs : Adjacency list representation of graphs is most popular which is uses linked list to store adjacent vertices.
4. Dynamic memory allocation : We use linked list of free blocks.
5. Maintaining directory of names
6. Performing arithmetic operations on long integers
7. Manipulation of polynomials by storing constants in the node of linked list

Add Egg Dropping Problem

Egg Dropping Problem

Egg dropping refers to a class of problems in which it is important to find the correct response without exceeding a (low) number of certain failure states. In a toy example, there is a tower of nn floors, and an egg dropper with mm ideal eggs. The physical properties of the ideal egg is such that it will shatter if it is dropped from floor n^n or above, and will have no damage whatsoever if it is dropped from floor n^-1n
−1 or below. The problem is to find a strategy such that the egg dropper can determine the floor n^*n in as few egg drops as possible.

Want to work on this.
Kindly assign me thanks! 👍

Z and Manachar's algorithms

Some Algorithms for Strings which should be added.

• Z Algorithm
  This Algorithm finds the count of given pattern in the given string in O(N) complexity and O(N) space.
• Manachar's Algorithm
  This Algorithm gets us the maximum length substring which is palindrome in complexity of O(N) and space of O(N).

I think both Algorithms are useful for Competitive Programming and should be there in this repository.

Add Prefix Sum Array

Title or Name of the Algorithm

• Prefix Sum Array

Describe the algorithm
Given an array of n integers, this algorithm returns the the sum of values in range [a, b]

Russian Peasant Algorithm

Title or Name of the Algorithm

• Russian Peasant Algorithm

Describe the algorithm
Multiplying two numbers without using '*' operator by bit manipulation.

Counting Sort

Title or Name of the Algorithm
Counting Sort

Describe the algorithm
The algorithm simply counts the number of occurences of a number in a count array. This count array can be used as a more efficient way to calculate the position of elements in a sorted array when the numbers are small and repetitive.

Kahn's Algorithm

Title or Name of the Algorithm
Kahn's Algorithm

Describe the algorithm

In directed graphs, the most commonly asked question is about to find the topological sort of the directed acyclic graph. Kahn's Algorithm helps us to find the topological sort of the directed acyclic graph. One special task that Kahn's algorithm achieves is that it can be modified to find the lexicographically smallest topological sort of the directed acyclic graph.

Kahn's algorithm uses indegree of the vertices to find the topological sort.

Those who dont know what a topological sort is:
A topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.

DSA for all language

We can do DSA in C++, Java, Python to make a separate folder for all languages and anyone can start contributing to it.

Topics of Mathematics for Coders

#28

Traversal of a 2D matrix in a clockwise spiral

Traversal of a 2D matrix in a clockwise spiral

Given a 2D array, Traverse the array in a spiral form.
See the following examples.

Examples:

Input: 
        1    2   3   4
        5    6   7   8
        9   10  11  12
        13  14  15  16
Output: 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10 
Explanation: The output is matrix in spiral format. 

Input:  
        1   2   3   4  5   6
        7   8   9  10  11  12
        13  14  15 16  17  18
Output: 1 2 3 4 5 6 12 18 17 16 15 14 13 7 8 9 10 11

Explanation :The output is matrix in spiral format.

DSA for all languages.

We can do DSA in C++, Java, Python, or any other language and anyone who is comfortable with it can contribute.

Sieve of Eratosthenes

Algorithm

• Finds all prime numbers under n

Description
Python program to print all primes smaller than or equal to n using Sieve of Eratosthenes.

[Pigeonhole Sorting]

Title or Name of the Algorithm

• Pigeonhole Sorting

Describe the algorithm
Pigeonhole sorting is a sorting algorithm that is suitable for sorting lists of elements where the number of elements and the number of possible key values are approximately the same.
It requires O(n + Range) time where n is the number of elements in the input array and ‘Range’ is a number of possible values in the array.

Kadane's Algorithm

Dynamic Programming

• Kadane's Algorithm

Description
An efficient way to find the sum of contiguous subarray within a one-dimensional array of numbers which has the largest sum.

0/1 KnapSack algorithm | Dynamic Programming

Title or Name of the Algorithm

• 0/1 KnapSack Algorithm using Dynamic Programming in C++

Describe the algorithm
0/1 Knapsack is very important problem which creates the base for dynamic programming using which you can solve various problems such as Subset Sum Problem,Equal Sum Partition Problem.
In 0/1 knapsack problem we are a sack and some items and we have to add items in sack but sack's capacity is bounded by certain weight and we can't add more items than weight of knapsack. We are given items weight and profit array and target is to maximize the profit. 0/1 means either we can include the item or not.

Merge Algo

MERGE ALGO IN C++

Describe the algorithm
Merge algorithms are a family of algorithms that take multiple sorted lists as input and produce a single list as output, containing all the elements of the inputs lists in sorted order. These algorithms are used as subroutines in various sorting algorithms, most famously merge sort.
Code of Algo
#include <iostream.h>
int a[50];
void merge(int,int,int);
void merge_sort(int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
merge_sort(low,mid);
merge_sort(mid+1,high);
merge(low,mid,high);
}
}
void merge(int low,int mid,int high)
{
int h,i,j,b[50],k;
h=low;
i=low;
j=mid+1;

while((h<=mid)&&(j<=high))
{
if(a[h]<=a[j])
{
b[i]=a[h];
h++;
}
else
{
b[i]=a[j];
j++;
}
i++;
}
if(h>mid)
{
for(k=j;k<=high;k++)
{
b[i]=a[k];
i++;
}
}
else
{
for(k=h;k<=mid;k++)
{
b[i]=a[k];
i++;
}
}
for(k=low;k<=high;k++) a[k]=b[k];
}
void main()
{
int num,i;

cout<<"***************************************************"<<endl;
cout<<" MERGE SORT PROGRAM
"<<endl;

cout<<"*******************************************************"<<endl;
cout<<endl<<endl;
cout<<"Please Enter THE NUMBER OF ELEMENTS you want to sort [THEN
PRESS
ENTER]:"<<endl;
cin>>num;
cout<<endl;
cout<<"Now, Please Enter the ( "<< num <<" ) numbers (ELEMENTS) [THEN
PRESS ENTER]:"<<endl;
for(i=1;i<=num;i++)
{
cin>>a[i] ;
}
merge_sort(1,num);
cout<<endl;
cout<<"So, the sorted list (using MERGE SORT) will be :"<<endl;
cout<<endl<<endl;

for(i=1;i<=num;i++)
cout<<a[i]<<" ";

cout<<endl<<endl<<endl<<endl;

}

Prim's Minimum Spanning Tree

I want to work on this issue

Lowest Common Ancestor in Binary-Tree

LCA*

• Lowest Common Ancestor in Binary-Tree

Let T be a rooted tree. The lowest common ancestor between two nodes n1 and n2 is defined as the lowest node in T that has both n1 and n2 as descendants.

Depth First Search

Title or Name of the Algorithm
Depth First Search

Describe the algorithm
Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.

Prim's Algorithm for minimum spanning tree

Title or Name of the Algorithm
Prim's Algorithm for minimum spanning tree

Describe the algorithm
Prim's Algorithm is used to find the minimum spanning tree in a graph. It finds the subset of edges that includes every vertex of the graph such that the sum of the weights of the edges can be minimized. Prim's algorithm starts with a single node and explores all the adjacent nodes with all the connecting edges at every step. The edges with the minimal weights causing no cycles in the graph get selected.

Prefix Sum Array

Title or Name of the Algorithm

• Prefix Sum Array

Describe the algorithm
Given an array of N integers, this algorithm processes Q queries of the form: what is the sum of values in range [A,B]?

Find sum of all right leaves in a given Binary Tree .

In Tree data structure i want to add how to find sum of all right leaves in BST.
I can do this in C++ along with an explanation can I do this .

Kruskal’s Algorithm

Title or Name of the Algorithm
Kruskal’s Algorithm

Describe the algorithm
Kruskal's Algorithm finds the minimum spanning tree in an undirected graph in O(ElogV), where E is the number of edges & V is the number of nodes. It falls under a class of algorithms called greedy algorithms that find the local optimum in the hopes of finding a global optimum. We start from the edges with the lowest weight and keep adding edges until we reach our goal.

What is a Spanning Tree?
Given an undirected and connected graph, a spanning tree of the graph is a tree that spans (that is, it includes every vertex of ) and is a subgraph of (every edge in the tree belongs to )

What is a Minimum Spanning Tree?
The cost of the spanning tree is the sum of the weights of all the edges in the tree. There can be many spanning trees. The minimum spanning tree is the spanning tree where the cost is minimum among all the spanning trees. There also can be many minimum spanning trees.

Heap Sort

Heap Sort

Description
Heap sort is a comparison based sorting technique based on Binary Heap data structure. It is similar to selection sort where we first find the maximum element and place the maximum element at the end. We repeat the same process for the remaining elements.

djikstra implementation in graphs

I want to implement djikstra algorithm for weighted graph in c++ ,can i do it?

Coin Problem | Optimal Strategy for a Game

Optimal Strategy for a Game

*Description : *

Consider a row of n coins of values v1 . . . vn, where n is even. We play a game against an opponent by alternating turns. In each turn, a player selects either the first or last coin from the row, removes it from the row permanently, and receives the value of the coin. Determine the maximum possible amount of money we can definitely win if we move first.

Note: The opponent is as clever as the user.

Let us understand the problem with few examples:

5, 3, 7, 10 : The user collects maximum value as 15(10 + 5)
8, 15, 3, 7 : The user collects maximum value as 22(7 + 15)
Does choosing the best at each move gives an optimal solution? No.
In the second example, this is how the game can be finished:

…….User chooses 8.
…….Opponent chooses 15.
…….User chooses 7.
…….Opponent chooses 3.
Total value collected by user is 15(8 + 7)
…….User chooses 7.
…….Opponent chooses 8.
…….User chooses 15.
…….Opponent chooses 3.
Total value collected by user is 22(7 + 15)
So if the user follows the second game state, the maximum value can be collected although the first move is not the best.

Counting Subarray with equal zeros and ones

Title or Name of the Algorithm
Count number of Subarrays with Equal Zero and Ones

Describe the algorithm

1. Take a variable currSum.

2. Take the sum of the entire array considering all zeroes as -1 and 1 as 1.

3. Simultaneously keep updating the value of hashmap as you traverse through the array.

4. Now traverse through the hashmap and look if any value of currSum appears more than once.
   Why do we do this?

   Imagine an array like this: [1, 0, 0, 1, 0, 1, 1]
   Making all zeroes as -1.
   [1, -1, -1, 1, -1, 1, 1]

   Now the hashmap would have values such as this:
   -1 --- 2
   0 --- 3
   1 --- 2

5. Now as if we encounter the same sum more than twice, that means the value of the subarray between the two indices is zero. So we add that to our answer.

6. Finally add the hashmap value of 0 to our answer as the subarray with zero-sum also need to be counted.

GCD(Euclidean algorithm)

May i work on this?

Rotated Sorted Array Search

Rotated Sorted Array Search using Binary Search

Given an array of integers A of size N and an integer B. Array A is rotated at some pivot unknown to us beforehand.A target value B is given to search. If found in the array, the algorithm return its index, otherwise return -1.

Reverse Linked list

I want to contribute to this Repo with:

1. Reversing the linked list using Recursion.
2. Reversing the linked list without Recursion.

Quick Sort

Title or Name of the Algorithm

• Quick Sort

Describe the algorithm
Quicksort is a highly efficient sorting algorithm and is based on the partitioning of an array or the divide and conquer approach of data into smaller arrays. A large array is partitioned into two arrays one of which holds values smaller than the specified value, say pivot, based on which the partition is made and another array holds values greater than the pivot value.
Quicksort partitions an array and then calls itself recursively twice to sort the two resulting subarrays. This algorithm is quite efficient for large-sized data sets as its average and worst-case complexity are O(N log N) and O(n^2) respectively.

Kosaraju Algorithm

Title or Name of the Algorithm

• Kosaraju Algorithm

Describe the algorithm
Used to find strongly connected components in a graph.
It is based on the idea that if one is able to reach a vertex v starting from vertex u, then one should be able to reach vertex u starting from vertex v and if such is the case, one can say that vertices u and v are strongly connected - they are in a strongly connected sub-graph.

Radix Sort

Radix Sort.

• Radix sort is a non-comparison based sorting algorithm which uses counting sort as a subroutine.
• Currently the repo has counting sort but for higher range of integers, Radix sort performs better.

I would like to work on radix sort, Please assign me the issue.

[NEW Algorithm] N-Queen problem

BackTracking Algorithm

• Famous N-Queen Problem

Describe the algorithm
When Given a number n as input
It outputs the number of ways of arranging queens in that NxN chessboard such that no two queens can kill each other.

for eg: n=4
there are two possible ways which are outputted like this-

.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..

Can I work on this problem

Sorting Algorithms

I want to contribute the repo with some programs in C language for sorting algorithms.
These are:

1. Bubble sort
2. Selection sort
3. Insertion sort
4. Quick sort
5. Merge sort

LCS[NEW Algorithm]

Title or Name of the Algorithm
LCS

• enter name of the algorithm here
  LONGEST COMMOM SUBSEQUENCE

Describe the algorithm
A brief description of what your algorithm does
LCS is a dynamic programming algorithm. Given 2 strings we've to find the longest common subsequence
ex : A = "abbcdef" , B = "acddfcb"
LCS = "adef"

String ATOI implementation

Title or Name of the Algorithm

• ATOI for C++ string

Describe the algorithm
Converts a string to int, counting only the leading valid characters (digits or sign). Ignores leading spaces. Assumes string fits in given size of int (overflows if string is too big).

Add Basic Programs

Add some basic algorithms to the basic algorithms folder. Some sample programs are given below.

• Check whether a number is prime or not
• Check whether a given string is plaindrome
• Count the frequency of all characters in a string
• Sum of all elements in an array
• Sum of diagonal elements of matrix of size n*n
• Print nth Fibonacci number
• Subtract 2 Matrix
• Print the table of nth number
• Check if a number is a perfect square

Algorithm for competative coding

For a competitive coder, they are not able to find "how and from where should we start" at GU. When I was in the first year, I was confused about what should do or leave. If Technojam starts a GitHub repository dedicated to the competitive coder and its opportunity.

Stacks and its associated functions

18)Stacks

• Stack implementation using array
• Stack implementation using Linked List
• Multiple Stack
• Parenthesis Checker
• Infix to Postfix
• Infix to Prefix
• Prefix evaluation
• Postfix Evaluation

I can do this. Please assign to me

LinkedList Reversing

I want to contribute to this Repo with:

Reversing the linked list using Recursion.
Reversing the linked list without Recursion.

Extended Euclids Algo

Title or Name of the Algorithm

• Extended Euclids Algo

Describe the algorithm

• Extended Euclidean algorithm finds integer coefficients x and y such that:

  ax + by = gcd(a, b)

• It is also used to find multiplicative modulo inverse of a w.r.t b

Bubble Sort

Title or Name of the Algorithm

• Bubble Sort

Describe the algorithm
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.

[NEW Algorithm]

Title or Name of the Algorithm

• Juggling Algorithm

Describe the algorithm
The algorithm rotates the arr[] of size n by d elements.
Time complexity:- O(n)
Space Complexity:- O(1)

Knuth Morris Pratt Algorithm

Title or Name of the Algorithm
Knuth Morris Pratt Algorithm

Describe the algorithm
A string matching algorithm

[NEW Algorithm]

Easy implementation for binary search

A standard way to go through all binary search problems

Bleak Number

Title or Name of the Algorithm
Bleak Number

Describe the algorithm
A number is called Bleak if it cannot be represented as sum of a positive number 'x' and set bit count in 'x', i.e.,
x + countSetBits(x) is not equal to n for any non-negative number x.

[Karp-Rabin String Matching Algorithm]

Title or Name of the Algorithm

• Karp Rabin String Matching Algorithm

Describe the algorithm
Given a text and a pattern, write a function that prints all occurrences of pattern in text.
Karp-Rabin algorithm slides the pattern one by one like the naive algorithm. But unlike the Naive algorithm, it matches the hash value of the pattern with the hash value of current substring of text, and if the hash values match then only it starts matching individual characters.

Checking Anagrams

Checking Anagrams

An Algorithm which checks if two strings are anagrams or not

Example: teststring & strtesting are anagrams of each other

Dynamic Programming

Dynamic Programming

• Knapsack Algorithm

1.Fractional Knapsack Problem
This is more of Greedy algorithm than dynamic programming

2. 0/1 Knapsack Problem
This is pure dynamic programming . Many problem are there to solve using this. Eg. Subset sum, Subset difference, Target Sum.

3. Unbounded Knapsack Problem
The main difference here is we allow repetition of items as compared to 0/1 Knapsack which allow item to be put once only. Eg. Rod Cutting Problem

I want to contribute to this algorithms. can I?