Solutions for Algorithms Stanford Course By Tim Roughgarden on Coursera

Requirements

• Python 3+

Solutions

Divide and Conquer, Sorting and Searching and Randomized Algorithms

• Counting Inversions - O(n log n)
• Number of Comparisons - average O(n log n)

Graph Search, Shortest Paths and Data Structures

• Karger's Minimum Cut - O(n^2)
• Kosaraju's Strongly Connected Components - O(m + n)
• Dijkstra's Shortest paths - O(n*m)
• Dijkstra's Shortest paths Heap - O(m log n)
• Median Maintenance - O(n log n)
• 2 Sum Algorithm - O(n)
• Binary Search Tree - average operations O(height)

Greedy Algorithms, Minimum Spanning Trees and Dynamic Programming

• Scheduling Jobs - O(n log n)
• Prim's Minimum Spanning Tree - O(m log n)
• Kruskal's Minimum Spanning Tree - O(m log n)
• Union Find by Rank and Path Compression - O(m log n)
• Clustering 1, Clustering 2- O(m log n)
• Huffman Coding - O(m log n)
• Maximum Weight Independent Set - O(n)
• Knapsack Max Capacity - O(mn)

Shortest Paths Revisited, NP-Complete Problems and What To Do About Them

• Bellman-Ford Shortest Path - O(mn)
• Floyd-Warshall Shortest Shortest Path - O(n^3)
• Johnson's Shortest Shortest Path - O(mn log n)
• Traveling Salesman Problem - NP
• Traveling Salesman Problem Heuristic - NP
• 2-Satisfiability - NP