Outline:

  • The searching problem
    • The ambition of hashing
  • Hashing
    • Brute force table: direct addressing
    • Basic idea of hashing
  • Collision Handling for Hashing
    • Closed address hashing
    • Open address hashing
  • Amortized Analysis
    • Array doubling

Ref:

  • 算法设计与分析(Algorithm design and analysis) by 黄宇
Read more »

Union Find algorithm.

Ref:

  • 算法设计与分析(Algorithm design and analysis) by 黄宇
  • 并查集(Union-Find)算法 by labuladong
Read more »

Outline

  • Lower bound and adversary argument
  • Selection - select the median
    • Expected linear time
    • Worst-case linear time
  • A Lower bound for Finding the Median

Ref:

  • 算法设计与分析(Algorithm design and analysis) by 黄宇
Read more »

Oultline

  • MergeSort
    • Worst-case analysis of MergeSort
    • More than sort: the MergeSort D&C
  • Lower Bounds for comparison-based sorting ( nlogn )
    • Worst-case ( Omega(nlogn) )
    • Average-case (nlogn - 1.443n )

Ref:

  • 算法设计与分析(Algorithm design and analysis) by 黄宇
Read more »

Outline:

  • Heap

  • HeapSort

  • FixHeap

  • ConstructHeap

  • Accelerated HeapSort

Ref:

  • 算法设计与分析(Algorithm design and analysis) by 黄宇
Read more »

Outline:

  • Inversion

  • InsertionSort

  • Analysis of InsertionSort

  • QuickSort

  • Analysis of QuickSort

Ref:

  • 算法设计与分析(Algorithm design and analysis) by 黄宇
Read more »

Outline

  • Recursion in algorithm design
    • The divide and conquer strategy
    • Proving the correctness of recursive procedures
  • Solving recurrence equations
    • Some elementary techniques
    • Master theorem

Ref:

  • 算法设计与分析(Algorithm design and analysis) by 黄宇
Read more »

Outline:

  • How to Compare Two Algorithms
  • Brute Force by Iteration
  • Brute Force by Recursion

Ref:

  • 算法设计与分析(Algorithm design and analysis) by 黄宇
Read more »
0%