Lu, Yukuan

Outline：

• NPC = P ？
• NPC判定问题
• 规约： 等价

Ref:

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

Outline:

• BestFS
• MCE

Ref:

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

Outline:

• Decision Problem
• The class P
• The class NP
• Reduction between problems
• NP-Complete Problems
• Other advanced topics

Ref:

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

Outline:

• Basic Idea of Dynamic Programming(DP)
  • Smart scheduling of subproblems
• Minimum Cost Matrix Multiplication
  • BF1, BF2
  • A DP solution
• Weighted Binary Search Tree
  • The "same" DP with matrix multiplication
• From the DP perspective
  • All-pairs shortest paths SSSP over DAG
• More DP problems
  • Edit distance
  • Highway restaurants; Separating Sequence of words
  • Changing coins
• Elements of DP

Ref:

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

Outline:

• Single-Sources shortest paths( SSSP )

  • Dijkstra algorithm by example
  • Priority queue-based implementation
  • Proof of correctness

• All-pairs shortest paths( APSP )

  • Shortest path and transitive closure
  • Warshall algorithm for transitive closure
    • BF1, BF2, BF3 => Warshall algorithm
    • Floyd algorithm for shortest paths

Ref:

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

Outline:

• Optimization Problem
• Greedy Strategy

Ref:

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

• 数学归纳法
• QuickSort
• 堆

Ref:

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

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