iiitv/algos

Popular Algorithms and Data Structures implemented in popular languages

algos's Issues

Add me to repo

It would be good if one raises an issue for adding as contrib rather than commenting in an ongoing PR, because it is not referenced to the PR.

Integrate Codacy

Codacy has a good PR integration which comments design issues in the code directly in the PRs.
I think we should be using it.

Mo's Algorithm [CPP]

Explanation link: http://codeforces.com/blog/entry/43230

Binary search on sorted array

http://quiz.geeksforgeeks.org/binary-search/

Add more helpful resources to README

Please add more algorithm lists / tutorial lists / related materials etc to the Resources section of the README.

Define a merge policy

We need a merge policy to fix how we are going to merge PRs. Here's my proposal -

1. One squashed commit merge with PR.
2. Even if PR contains multiple type of changes, it should reflect only a single topic and Rule 1 shall still withhold on it.

Why squashed merge ?

It preserves both the author as well as the committer, something that can be very useful.
Also one commit per PR provides the cleanest commit history possible.

---

@singhpratyush views?

Largest Sum Contiguous Subarray problem [Java]

find the sum of contiguous subarray within a one-dimensional array of numbers.

Heap Sort [C]

https://en.wikipedia.org/wiki/Heapsort

Prime Factors of a Number [C]

https://en.wikipedia.org/wiki/Prime_factor

Add Java skeleton code to guidelines

Add Java skeleton code at https://github.com/iiitv/algos/blob/master/CONTRIBUTING.md#samples

This issue is up for grabs. Anyone can assign themselves and start working on this.

Counting Sort [Java]

A popular algorithm used for sorting under specific constraints but if constraints were followed, It is the one of the fastest sort

www.geeksforgeeks.org/counting-sort/

Trie [Java]

https://en.wikipedia.org/wiki/Trie

Merge Sort [C]

https://en.wikipedia.org/wiki/Merge_sort

Sieve of Erastosthenes [Python]

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Submit a sample implementation of an algorithm to serve as a complete example

The algorithm can be anything.
Language should be one of Java, Python, C or C++.

Depth First Traversal [Java]

http://www.geeksforgeeks.org/depth-first-traversal-for-a-graph/

Merge Sort [CPP]

Quicksort [C]

https://en.wikipedia.org/wiki/Quicksort

Euclidean GCD [CPP]

Insertion Sort [C]

https://en.wikipedia.org/wiki/Insertion_sort
Implementation would be same in c and c++

Insertion Sort [Python]

https://en.wikipedia.org/wiki/Insertion_sort

Stack [Python]

https://en.wikipedia.org/wiki/Stack_(abstract_data_type)

Require following functionalities -

• Print
• Push
• Pop
• Peek
• Get size

Create a class and add example usage in single file.

Binary Search [C]

Add a PULL REQUEST TEMPLATE

It should specifically remind people to have a look at the CONTRIBUTING guidelines before submitting their patch. Also some keys points from the guidelines should be listed out.

Example: https://github.com/aviaryan/awesome-no-login-web-apps/blob/master/PULL_REQUEST_TEMPLATE.md

Selection Algorithm [C]

Suppose you want to find the kth position element in a sorted list without sorting the list, Need to find the median in a Large Data set after Sorting. In these places Selection algorithm can be used.

Split the existing issues based on language

Breadth First Search in a Graph [Java]

https://en.wikipedia.org/wiki/Breadth-first_search

Euclidean GCD [Python]

Euclidean GCD [C]

Finding gcd of two numbers using Eucledian Algorithm. (Recursive and non-recursive both can be implemented).
EDIT:
Link: https://en.wikipedia.org/wiki/Euclidean_algorithm

Add Python sample code

Add a Python sample/skeleton code in the CONTRIBUTING file .. https://github.com/iiitv/algos/blob/master/CONTRIBUTING.md#samples

Anyone who wants to work on this, please assign yourself.

Euclidean GCD [Java]

A* Search [Java]

https://en.wikipedia.org/wiki/A*_search_algorithm

Data structures in this list?

I think we should include DS in this list too. I mean they are very related to the algorithms and are often used in algorithms. Examples - implementation of Stack, Queue, Heap etc.

Please post your views regarding this. @singhpratyush @Monal5031 @yashLadha @aashutoshrathi @jsroyal

The Longest Common Subsequence [C]

LCS Problem Statement: Given two sequences, find the length of longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are subsequences of “abcdefg”. So a string of length n has 2^n different possible subsequences.

Examples:
LCS for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3.
LCS for input Sequences “AGGTAB” and “GXTXAYB” is “GTAB” of length 4.

Backtracking algorithm (N-Queen Problem) [CPP]

A general solution of the N-Queen problem (any board of n X n) in C++ with backtracking.

https://en.wikipedia.org/wiki/Eight_queens_puzzle

QuickSort [java]

https://en.wikipedia.org/wiki/Quicksort

Merge Sort

https://www.khanacademy.org/computing/computer-science/algorithms/merge-sort/a/overview-of-merge-sort

k-NN Algorithm [Python]

https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm

Binary Search [Java]

Coin Change Problem [C]

Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change? The order of coins doesn’t matter.

For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5.

Sieve of Eratosthenes [C]

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
Algorithm to find prime numbers till a number N

Linear Search [C]

https://en.wikipedia.org/wiki/Linear_search

Coding Guidelines

Adding a .md file discussing the guidelines for solutions would be helpful.

Breadth First Search in a Graph [Python]

https://en.wikipedia.org/wiki/Breadth-first_search

Binary Search [python]

Possible Algo. List and Difficulty level

We can compile a possible list of Algorithms to be implemented so that a person attempting as a beginner will not have much problem.
Further, I guess it would be nice to assign the work to implement the algorithms according to the difficulty level. Like a person who is familiar with coding will not attempt beginner level programs and maybe leave them for the new one's. Also, a time constraint would also be a good thing to add so that someone else who is ready to do it will get that chance.

Kadane's Algorithm (Largest Sum Contiguous Subarray problem) [CPP]

A popular Dynamic programming algorithm to find a largest sum contiguous subarray.

https://kartikkukreja.wordpress.com/2013/06/17/kadanes-algorithm/

Stack [JAVA]

https://en.wikipedia.org/wiki/Stack_(abstract_data_type)

Following Functionalities I will add:

• Display stack elements
• Push (Adding element to top of stack)
• Pop (Removing element from top of stack)
• Peek
• Get size

Will create a separate class for it and test in Main class.
Any suggestions over any particular thing I should use?

Modular Exponential [Python]

http://www.geeksforgeeks.org/modular-exponentiation-power-in-modular-arithmetic/

Exponentation by squaring [C]

https://en.wikipedia.org/wiki/Exponentiation_by_squaring

It is very much efficient algorithm to calculate x raised to power k.

Edit: time complexity is O( (nlogx) ^ k)