Algorithms

Algorithms and data structures are fundamental to efficient code and good software design. Creating and designing excellent algorithms is required for being an exemplary programmer. This repository presents the Python code implementation of the provided algorithms and data structures from William Fiset at: https://github.com/williamfiset/Algorithms.

Running an algorithm implementation

To run any of the algorithms here, you need at least Python version 3.9:

python <algorithm-filepath>

Data Structures

• Binary Search Tree
• Fenwick Tree
• Linked List
• Priority Queue
  • Min Binary Heap
• Queue
  • Queue (list)
  • Queue (linked list)
• Stack
  • Stack (list)
  • Stack (linked list)
• Union Find

Graph Theory

Tree algorithms

• Rooting an undirected tree - O(V + E)
• Identifying isomorphic trees - O(?)

Main graph theory algorithms

• Breadth first search (adjacency list) - O(V + E)
• Depth first search (adjacency list, iterative) - O(V + E)
• Depth first search (adjacency list, recursive) - O(V + E)

Mathematics

• Extended euclidean algorithm - ~O(log(a + b))
• Greatest Common Divisor (GCD) - ~O(log(a + b))
• Primality check - O(√n)
• Least Common Multiple (LCM) - ~O(log(a + b))
• Modular inverse - ~O(log(a + b))

Search algorithms

• Binary search - O(log(n))

Sorting algorithms

• Bubble sort - O(n²)
• Bucket sort - Θ(n + k)
• Counting sort - O(n + k)
• Heapsort - O(nlog(n))
• Insertion sort - O(n²)
• Mergesort - O(nlog(n))
• Quicksort - Θ(nlog(n))
• Selection sort - O(n²)

String algorithms

License

This repository is released under the MIT license. In short, this means you are free to use this software in any personal, open-source or commercial projects. Attribution is optional but appreciated.