Coursera-Algorithms [Stanford University]

This repo contains course notes and assignments, most implemented both in Java and Python, in the Algorithms specialization from Stanford University on Coursera.

Divide and Conquer, Sorting and Searching, and Randomized Algorithms

1. Karatsuba Multiplication
2. Number of Inversions
3. Closest Pair
4. Quick Sort
5. Random Selection
6. Graph Representation
7. Minimum Cut

Graph Search, Shortest Paths, and Data Structures

Hash Table

BST

• Select & Rank
• AVL Tree
• Red-Black Tree

Graph Search (BFS & DFS)

• BFS and Its Applications
• DFS and Its Applications

Bloom Filter

Greedy Algorithms, Minimum Spanning Tree, and Dynamic Programming

Greedy Algorithm

• Scheduling
• Single-Vertex Shortest Paths
  • Dijkstra's Algorithm
• Minimum Spanning Tree
  • Prim's Algorithm
  • Kruskal's Algorithm
• Data Structure-Union Find
• Huffman Encoding

Dynamic Programming

• Maximum-Weight Independent Set in Path Graph
• Weighted Interval Scheduling
• Knapsack
• Sequence Alignment
• Optimal BST

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

Shortest Paths Revisit

• Bellman-Ford's Algorithm

All-Pair Shortest Paths

• Floyd-Warshall's Algorithm
• Johnson's Algorithm

NP-Complete Problems

• Approach 1-Focus on some computationally tractable special cases (=> Exact algorithms)

  • Maximum-Weight Independent Set
  • 2-SAT

• Approach 2-Solve in exponential-time, but faster than brute-force way (=> Exact algorithms)

  • Knapsack with Dynamic Programming-Based Algorithm
  • Vertex Cover
  • Traveling Salesman

• Approach 3-Use heuristics (efficient algorithms that are not always correct) (=> Approximate algorithm)

  Frequently-used heuristic design paradigms:

  • Greedy
    • Knapsack with Greedy-Based Heuristic
  • Dynamic programming
    • Knapsack with Dynamic Programming-Based Heuristic
  • Local search
    • Maximum Cut

License

This repo is distributed under the MIT license.