Skip to content

Algorithms Specialization offered by Stanford University through Coursera.

Notifications You must be signed in to change notification settings

wxo15/stanford-algorithms-coursera

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

17 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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

About

Algorithms Specialization offered by Stanford University through Coursera.

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published