luminus7 / clrs-python-implementations

Python implementations of some algorithms from the CLRS textbook

CLRS-Python-Implementations

Python implementations of some algorithms from the CLRS textbook https://en.wikipedia.org/wiki/Introduction_to_Algorithms

Sorting (sorting.py)

• Insertion sort
• Insertion sort in non-ascending order
• Mergesort
• Heapsort
  • draw_heap() - a function that draws a visual representation of the heap - useful for debugging!
• Quicksort
• Randomized quicksort
• Counting sort

Randomization (randomization.py)

• random(a, b) - generates a random number between a and b using random(0, 1)
• Randomize an array in-place

Dynamic Programming (dynamic_programming.py)

• Rod cutting problem

  • Recursive solution
  • Top-down memoized solution
  • Bottom-up solution

• Longest common subsequence

Min priority queue (min_priority_queue.py)

Greedy algorithm for activity selection (greedy_activity_selection.py)

Huffman code for data compression (huffman.py)

Basic graph algorithms

• Breadth-first search (bfs.py)
• Depth-first search (dfs.py)
• Topological sorting of a directed acyclic graph (DAG) (dfs.py)

Prim's algorithm for minimum spanning tree (min_span_tree.py)

Shortest path algorithms (shortest_paths.py)

• Bellman-Ford algorithm for graphs with negative edges
• Dijkstra's algorithm