Skip to content

Latest commit

 

History

History
77 lines (64 loc) · 3.42 KB

README.md

File metadata and controls

77 lines (64 loc) · 3.42 KB

Stanford Algorithms Specialization (Coursera)

Algorithms Specialization offered by Stanford University through Coursera.

Certificate: Link

Courses:

  • Course 1 - Divide and Conquer, Sorting and Searching, and Randomized Algorithms - Done
  • Course 2 - Graph Search, Shortest Paths, and Data Structures - Done
  • Course 3 - Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming - Done
  • Course 4 - Shortest Paths Revisited, NP-Complete Problems and What To Do About Them - Done

Course 1 and 2 are also called Design and Analysis of Algorithms I, while Course 3 and 4 are also called Design and Analysis of Algorithms II.

Topics

✔️ = implemented

1. Divide and Conquer, Sorting and Searching, and Randomized Algorithms

  • Part 1: Divide and Conquer:
    • Integer Multiplication
    • Karatsuba Multiplication ✔️
    • Merge Sort
  • Part 2: Asymptotic Analysis (Big-oh, Omega and Theta notation)
  • Part 3: Divide and Conquer:
    • Counting Inversions ✔️
    • Strassen’s Matrix Multiplication Algorithm
  • Part 4: The Master Method
  • Part 5: QuickSort ✔️
  • Part 6: QuickSort Analysis
  • Part 7: Probability Review
  • Part 8: Linear-time Selection (for Quick Sort)
  • Part 9: Graphs and The Minimum Cut
    • Karger's Contraction Algorithm ✔️

2. Graph Search, Shortest Paths, and Data Structures

  • Part 10: Graph Search and Connectivity
    • Depth-First Search (DFS), Breath-First Search (BFS)
    • Kosaraju’s Two‐Pass Algorithm for SCC detection ✔️
  • Part 11: Dijkstra's Shortest-Path Algorithm ✔️
  • Part 12: Heaps data structure
    • Median tracking ✔️
  • Part 13: Binary Search Tree data structure
  • Part 14: Hashing, Hash Table, Bloom Filter data structure
    • 2-Sum Algorithm ✔️

3. Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming

  • Part 1&2: Recap
  • Part 3: Greedy algorithm
  • Part 4: Greedy algorithm - Scheduling
  • Part 5: Prim's Minimum Spanning Tree ✔️
  • Part 6: Kruskal Minimum Spanning Tree
  • Part 7: Clustering (using Kruskal's Algorithm) ✔️
  • Part 8: Union-find data structure
  • Part 9: Huffman's Encoding Algorithm ✔️
  • Part 10: Maximum-Weighted Independent Set ✔️
  • Part 11: Knapsack Problem ✔️
  • Part 12: Sequence Alignment
  • Part 13: Optimal Binary Search Tree

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

  • Part 14: Bellman-Ford Single-Source Shortest Path Algorithm ✔️
  • Part 15: All-Pairs Shortest Paths
    • Floyd-Warshall algorithm
    • Johnson’s Algorithm ✔️
  • Part 16: NP-completeness
    • 2SAT Problem (using Kosaraju’s Two‐Pass Algorithm) ✔️
  • Part 17: Exact Algorithms for NP-Complete Problems
    • Travelling salesman problem (DP, greedy heuristic and local search) ✔️
  • Part 18: Approximation Algorithms for NP-Complete Problems
    • Knapsack Problem revisit
  • Part 19: Local search
    • Random Walks on a Line
  • Part 20: Beyond