Algorithms Specialization

Course can be found in Coursera

Quiz answers and notes can be found in my blog SSQ

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

Course can be found in Coursera

Slides and more details about this course can be found in my Github SSQ

• Week 1:

  • 1: Divide and Conquer:
    • Integer Multiplication;
    • Karatsuba Multiplication;
    • Implementation by Python;
    • Merge Sort.
  • 2: Asymptotic Analysis:
    • Big-oh notation; Omega and Theta notation;

• Week 2:

  • 3: Divide and Conquer:
    • Counting Inversions
    • Implementation by python;
    • Matrix Multiplication Strassen’s Algorithm
    • Closest Pair Optional
  • 4: The Master Method:
    • Motivation; Example; Proof I, Proof II

• Week 3:

  • 5: Randomized Algorithm - QuickSort:
    • Overview; The Partition Subroutine; Proof; Choosing a Good Pivot
    • Implementation of QuickSort with 3 pivots by python
  • 6: QuickSort Analysis:
    • the average running time of QuickSort (with random pivots)
  • 7: Probability Review:

• Week 4:

  • 8: Linear-time Selection
    • Randomized Selection
    • Deterministic Selection
  • 9: Graphs and The Minimum Cut
    • Random Contraction Algorithm
    • Implementation by Python

2. Graph Search, Shortest Paths, and Data Structures

Course can be found in Coursera

Slides and more details about this course can be found in my Github SSQ

• Week 1:
  • 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:
  • 11: Dijkstra's Shortest-Path Algorithm
    • Dijkstra’s Algorithm, Correctness, Fast Implementation with Heap
    • Implementation by Python
• Week 3:
  • 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:
  • 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

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

Course can be found in Coursera

Slides and more details about this course can be found in my Github SSQ

• Week 1:
  • Greedy algorithm;
  • Prim's Minimum Spanning Tree;
  • Implementation based on jupyter notebook.
• Week 2:
  • Kruskal's MST algorithm;
  • applications to clustering;
  • Implementation based on jupyter notebook;
  • advanced union-find (optional).
• Week 3:
  • Huffman's Algorithm;
  • introduction to dynamic programming (max weight independent set);
  • Implementation based on jupyter notebook.
• Week 4:
  • Knapsack Algorithm;
  • Implementation based on jupyter notebook;
  • Sequence alignment;
  • Optimal binary search trees.