:computer: Data Structures and Algorithms in Python

Related tags

Algorithms
Overview

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.singly_linked_list_test
python -m tests.modular_exponentiation_test
python -m tests.modular_multiplicative_inverse_test
Issues
  • Create gcd_test.py

    Create gcd_test.py

    Unit test for GCD.py

    opened by vedangmehta 9
  • Updated sieve_of_eratosthenes.py

    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

    Create sieve_of_eratosthenes.py

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

    opened by vedangmehta 6
  • Binary search

    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

    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.

    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.

    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
  • Added LCS and updated README

    Added LCS and updated README

    opened by vedangmehta 3
  • fix initial value

    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

    Miller rabin primality

    opened by SanketDG 2
  • Added Doubly Linked List

    Added Doubly Linked List

    opened by adi0311 0
  • changes

    changes

    i made changes

    opened by ramakrishna7946 0
  • Update quicksort.py

    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

    Adding two algorithms

    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

    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

    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

    Added Subset Sum Problem solution using Dynamic Programming

    opened by hetpandya98 0
  • Added Bubble sort program

    Added Bubble sort program

    Bubble sort with optimization

    opened by Rahulsharma4298 0
Owner
Prakhar Srivastav
Prakhar Srivastav
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

null 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

Prabhu Pant 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

Nic Young 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

Vinta Chen 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

Travis Jungroth 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

The Algorithms 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

Prakhar Srivastav 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

Atsushi Sakai 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

Laurent Luce 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

Dom De Felice 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.

Hybrid Theory 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

Sakis Kasampalis 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

null 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

Grant Jenks 2.2k Jun 13, 2021