Lu, Yukuan

DAG(Directed Acyclic Graph), DAG's topological ordering and SCC(Strongly Connected Component).

Ref: 算法设计与分析(Algorithm design and analysis) by 黄宇.

Outline：

• General DFS/BFS Skeleton
• Depth-First Search Trace

Ref: 算法设计与分析(Algorithm design and analysis) by 黄宇

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 黄宇

Union Find algorithm.

Ref:

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

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 黄宇

Latex grammer.

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 黄宇

Outline:

• Heap

• HeapSort

• FixHeap

• ConstructHeap

• Accelerated HeapSort

Ref:

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

Outline:

• Inversion

• InsertionSort

• Analysis of InsertionSort

• QuickSort

• Analysis of QuickSort

Ref:

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

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 黄宇