Coursera Stanford Graph Search, Shortest Paths and Data Structures

Course can be found in Coursera

Quiz answers and notebook for quick search can be found in my blog SSQ

• Week 1 Lecture slides:
  • 10: Graph Search and Connectivity
    • Generic Graph Search
    • Breadth-First Search (BFS), Application: Shortest Paths, Application: Undirected Connectivity
    • Depth-First Search, Application: Topological Sort
    • Strongly Connected Components(SCC), Kosaraju’s Two‐Pass Algorithm
    • Implementation by Python
    • (Optional)Structure of the Web
• Week 2 Lecture slides:
  • 11: Dijkstra's Shortest-Path Algorithm
    • Dijkstra’s Algorithm, Correctness, Fast Implementation with Heap
    • Implementation by Python
• Week 3 Lecture slides:
  • 12: Heaps
    • Heap: Supported Operations; Application: Sorting; Application: Event Manager; Application: Median Maintenence; Application: Speeding Up Dijkstra
    • Implementation Heap application: Median Maintenence by Python
    • Array Implementation, Insert and Bubble‐Up, Extract‐Min and Bubble‐Down
  • 13: Balanced Binary Search Trees
    • Balanced Search Trees: Supported Operations
    • Binary Search Tree: Searching and Inserting; Min, Max, Pred, And Succ; In-Order Traversal; Deletion; Select and Rank
    • Balanced Search Trees: Red-Black
    • (Optional)Rotations: left rotation; right rotation
    • (Optional)Insertion In A Red-Black Tree
• Week 4 Lecture slides:
  • 14: Hashing
    • Hash Table: Supported Operations; Application: De‐Duplication; Application: The 2‐SUM Problem
    • Implementation by Python
    • Resolving Collisions; Good Hash Function: Bad Hash Function
  • 15: Universal Hash Functions:
    • Motivation
  • 16: Bloom Filters
    • Bloom Filters