Algorithms

# Algorithms in Python

Implementations of a few algorithms and datastructures for fun and profit!

## Completed

• Karatsuba Multiplication
• Basic Sorting
• Rabin-Miller primality test
• Sieve of Eratosthenes for prime numbers
• Binary Search
• Counting Inversions in an array
• Selecting ith order statistic in an array
• Graph datastructure (directed & undirected)
• Graph Algos
• Topological Sorting
• Shortest hops
• DFS
• BFS
• Connected Components
• Dijkstra's Shortest Path - O(mlogn)
• Prim's Minimum Cost Spanning Tree - O(mlogn)
• Kruskal's Minimum Spanning Tree - O(mlogn)
• Max k Clustering
• Bellman Ford
• Floyd Warshall
• Johnson's Algorithm
• Heap datastructure
• Max heaps
• Min heaps (priority queue)
• Heapsort
• Job Scheduling
• UnionFind Data Structure
• Binary Search Tree
• Kandane's Algorithm
• Knapsack Problem (0/1 and unbounded)
• Longest Increasing Subsequence
• Longest Common Subsequence
• Prefix Tries
• Stack ADT (with example problems)
• String Reverse
• Parenthesis Matching
• Infix to Postfix
• Modular exponentiation
• Modular multiplicative inverse

## Tests

``````python -m tests.graph_test
python -m tests.digraph_test
python -m tests.graph_algorithms_test
python -m tests.heap_test
python -m tests.unionfind_test
python -m tests.modular_exponentiation_test
python -m tests.modular_multiplicative_inverse_test
``````
• #### Create gcd_test.py

Unit test for GCD.py

opened by vedangmehta 9
• #### Updated sieve_of_eratosthenes.py

Added a unit test file and changed the loop to list comprehension.

opened by vedangmehta 6
• #### Create sieve_of_eratosthenes.py

I want to contribute to create a new section of Maths algorithms.

opened by vedangmehta 6
• #### Binary search

A simple iterative binary search algorithm.

Please review. I know I didn't update my fork but can you please merge this by resolving the merge conflicts?

Thank you.

opened by SanketDG 4
• #### Created simple setup.py so I could use union_find package

I wrote a simple setup.py program based on this quickstart guide, which required that I add a README.txt file with the same content as your README.md (I don't believe that the markdown files can be read by the method called), and that I tag the current build as 'v1.0'. I successfully installed the union_find package and was able to use it in my work :+1: :D Hopefully, this fork will give an basis for how to use setup.py, and will allow others to include more of the project's packages if desired. Thank you for this excellent project!

opened by wbkboyer 4
• #### Added Hierholzer's algorithm to find Eulerian Tour in a graph.

This program finds an Eulerian Tour in the given graph. The program is based on Hierholzer's algorithm. You can read about this algorithm at https://en.wikipedia.org/wiki/Eulerian_path

opened by viiicky 4
• #### Queue implementation currently uses a list under the hood. It should be modified to use a deque to make it efficient.

The `Queue` implementation, as it currently stands uses a list and then does a `self.items.insert(0, item)` to insert an item in the `Queue`. This is inefficient. A better approach is to modify `Queue` to use a `deque` under the hood, instead of a list for increased efficiency. Please let me know if you agree with the above approach so that I can send a pull request with the appropriate changes.

opened by the-shank 4

opened by vedangmehta 3
• #### fix initial value

The initial value will be wrongly added twice when is bigger than the second value:

``````    max_till_here[-1] + n
``````

This test case will fail:

``````assert find_max_subarray2(([1,-1]) == 1 // it will return 2
``````
opened by antrianis 3
• #### Miller rabin primality

opened by SanketDG 2

• #### Included count sort in sorting.py

opened by pointer-04 0
• #### changes

opened by ramakrishna7946 0
• #### Added rodcutting problem in the dp section

opened by KillMonger1 0
• #### Update quicksort.py

This python program can generate 10 random numbers and sort them accordingly using the Quick Sort algorithm also implement code for display execution time.

opened by akshaypatil314 0

Adding two algorithms to the repository.

1. fractional knapsack which is a problem of dynamic programming and add to fix an issue #66 in the demand of fractional knapsack
2. Longest palindrome substring is a problem of dynamic programming and add in the repository by seeing the demand of the people to find the solution of the longest palindrome substring in linear time complexity. I use manacher algorithm to find the solution in the least time complexity.
opened by anubhavsharma430 0
• #### Topological sort using Adjacency Lists

Algorithm to find the topological sorting of a given graph in Adjacency Lists format.

opened by apoorvpandey0 0
• #### 0-1 Knapsack

Python program to implement 0-1 knapsack

opened by Pragati-Kalra 0
• #### Added Subset Sum Problem solution

Added Subset Sum Problem solution using Dynamic Programming

opened by hetpandya98 0
• #### Added Bubble sort program

Bubble sort with optimization

opened by Rahulsharma4298 0
###### Algorithms and data structures for educational, demonstrational and experimental purposes.

Algorithms and Data Structures (ands) Introduction This project was created for personal use mostly while studying for an exam (starting in the month

46 May 3, 2021
###### Repository for data structure and algorithms in Python for coding interviews

Python Data Structures and Algorithms This repository contains questions requiring implementation of data structures and algorithms concepts. It is us

1.4k Jun 14, 2021
###### This repository is not maintained

This repository is no longer maintained, but is being kept around for educational purposes. If you want a more complete algorithms repo check out: htt

2.9k May 29, 2021
###### How on earth can I ever think of a solution like that in an interview?!

fuck-coding-interviews This repository is created by an awkward programmer who always struggles with coding problems on LeetCode, even with some Easy

497 Jun 3, 2021
###### A command line tool for memorizing algorithms in Python by typing them.

Algo Drills A command line tool for memorizing algorithms in Python by typing them. In alpha and things will change. How it works Type out an algorith

34 Jun 8, 2021
###### All Algorithms implemented in Python

The Algorithms - Python All algorithms implemented in Python (for education) These implementations are for learning purposes only. Therefore they may

110.1k Jun 13, 2021
###### :computer: Data Structures and Algorithms in Python

Algorithms in Python Implementations of a few algorithms and datastructures for fun and profit! Completed Karatsuba Multiplication Basic Sorting Rabin

2.7k Jun 14, 2021
###### Python sample codes for robotics algorithms.

PythonRobotics Python codes for robotics algorithm. Table of Contents What is this? Requirements Documentation How to use Localization Extended Kalman

12.5k Jun 8, 2021
###### Algorithms implemented in Python

Python Algorithms Library Laurent Luce Description The purpose of this library is to help you with common algorithms like: A* path finding. String Mat

258 May 31, 2021
###### A genetic algorithm written in Python for educational purposes.

Genea: A Genetic Algorithm in Python Genea is a Genetic Algorithm written in Python, for educational purposes. I started writing it for fun, while lea

16 May 25, 2021
###### A fast python implementation of the SimHash algorithm.

This Python package provides hashing algorithms for computing cohort ids of users based on their browsing history. As such, it may be used to compute cohort ids of users following Google's Federated Learning of Cohorts (FLoC) proposal.

6 Apr 13, 2021
###### A collection of design patterns/idioms in Python

python-patterns A collection of design patterns and idioms in Python. Current Patterns Creational Patterns: Pattern Description abstract_factory use a

28.5k Jun 13, 2021
###### A lightweight, object-oriented finite state machine implementation in Python with many extensions

transitions A lightweight, object-oriented state machine implementation in Python with many extensions. Compatible with Python 2.7+ and 3.0+. Installa

3.7k Jun 16, 2021
###### Python Sorted Container Types: Sorted List, Sorted Dict, and Sorted Set

Python Sorted Containers Sorted Containers is an Apache2 licensed sorted collections library, written in pure-Python, and fast as C-extensions. Python

2.2k Jun 13, 2021