README.md

Fun with algorithms

This repository was created during the study of Introduction to Algorithms, Third Edition By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein book.

A well-written book with detailed implementation of algorithms.

Install

python3 -m venv venv 
source venv/bin/activate
pip install --upgrade pip
pip install -r requirements.txt 

List of Algorithms

List of algorithms presented in the book.

• Chapter 1.
  • Insertion sort
• Chapter 2.
  • Merge sort
  • Bubble sort
• Chapter 3.
  • Fibonacci numbers
• Chapter 4.
  • Maximum subarray problem
  • Square matrix multiply
  • Strassen algorithm
• Chapter 5.
  • Hire assistant problem.
  • Birthday problem.
• Chapter 6.
  • Max Heap
  • Heap sort
  • Priority queue
• Chapter 7.
  • Quick sort
  • Randomized quick sort
• Chapter 8.
  • Counting sort
  • Radix sort
  • Bucket sort
• Chapter 9.
  • Order statistic
• Chapter 10.
  • Stack
  • Queue
  • Singly linked list
  • Doubly linked list
  • Linked list with open addressing
• Chapter 11.
  • Hash table
  • Hash with open addressing
  • Double Hashing
  • Perfect hashing
• Chapter 12.
  • Binary Search Tree
• Chapter 13.
  • Red-black Tree
• Chapter 14.
  • Order-statistic tree
  • Josephus problem
• Chapter 15.
  • Rod cutting problem
  • Matrix chain multiplication problem
  • Longest common subsequence problem
  • Optimal binary search tree
  • Edit distance
• Chapter 16.
  • Activity selection problem.
  • Knapsack problem.
  • Huffman coding.
• Chapter 17.
  • Dynamic Hashing
• Chapter 18.
  • B-tree
• Chapter 19.
  • Fibonacci heap
• Chapter 20.
  • Van Emde Boas tree
• Chapter 21.
  • Disjoining-set data structure
  • Disjoining-set forest
  • Least common ancestor
• Chapter 22.
  • Breadth-first search
  • Depth-first search
  • Topological sort
• Chapter 23.
  • Kruskal's algorithm
  • Prim's algorithm
• Chapter 24.
  • Bellman-Ford algorithm
  • Dijkstra's algorithm
• Chapter 25.
  • Floyd-Warshall algorithm
  • Johnson's algorithm
• Chapter 26.
  • Maximum flow problem
  • Ford–Fulkerson algorithm
  • Relabel-to-front algorithm
• Chapter 27.
  • Fibonacci number using multithreading
  • Matrix multiplication using multithreading
  • Multithreading Strassen algorithm
  • Multithreading merge sort
• Chapter 28.
  • LU decomposition
  • LUP decomposition
  • Invertible matrix
• Chapter 29.
  • Simplex algorithm.
• Chapter 30.
  • Recursive FFT.
  • Iterative FFT.
  • Parallel FFT.
• Chapter 31.
  • Euclid algorithm.
  • Modular exponentiation.
  • RSA algorithm.
  • Pseudoprime.
  • Miller–Rabin primality test.
  • Pollard's rho algorithm.
  • Binary GCD algorithm.
• Chapter 32.
  • String searching algorithm.
  • Rabin–Karp algorithm.
  • Knuth–Morris–Pratt algorithm.
• Chapter 33.
  • Line segment intersection.
  • Graham scan.
  • Gift wrapping algorithm.
• Chapter 34.
• Chapter 35.
  • Approximate vertex cover.
  • Approximate travelling salesman problem.
  • Greedy set cover.
  • Exact subset sum.

Sort algorithms comparison

Table of complexity of different sorting algorithms:

For plot beautiful performance chart run following command.

python sort/performance.py

Algorithm	Worst case	Average case
Insertion Sort	O(n^2)	O(n^2)
Merge Sort	O(n*ln(n))	O(n*ln(n))
Heap Sort	O(n*ln(n))	O(n*ln(n))
Quick Sort	O(n^2)	O(n*ln(n))
Counting Sort	O(k + n)	O(k + n)
Radix Sort	O(d(k + n))	O(d(k + n))
Bucket Sort	O(n^2)	O(n)

Matrix multiplication

• Naive matrix multiplication O(n^3)
• Strassen matrix multiplication O(n^2.81)

python matrix/performance.py

Additional

• Performance comparison finding Fibonacci number
• Performance of basic math operation

Useful links:

• Performance comparison Naive and Strassen algorithms in Python, Java and C++
• Matrix Operations in Python
• LU Decomposition in Python and NumPy
• LU decomposition
• Inverting your very own matrix

Linked Lists

• Implementing an Unordered List: Linked Lists
• The Linked List

Binary Tree

• Binary Search Tree library in Python
• Search Tree Implementation
• Binary search tree