2110327 Algorithm Design

• Brute Force
  • Solution Space
  • Enumerating all solutions
  • Combination
  • Permutation
• Sorting
  • Selection Sort
  • Heap Sort
  • Insertion Sort
  • Shell Sort
• Complexity Analysis
  • Review
  • Master Method
• Divide and Conquer
  • Binary Search
  • Merge Sort
  • Quick Sort
  • Quick Select
  • Modular Expo
  • Maximum Contiguous Sum
  • Strassen's Matrix Multiplication
  • Closest Pair
  • Celebrity
• Dynamic Programming
  • Fibonacci Seq.
  • Binomial Coefficient
  • Longest Common Subsequence
  • Maximum Contiguous Sum
  • Matrix-Chain Multiplication
  • 0/1 Knapsack
  • Coin Change
• Greedy Algorithm
  • Activity Selection
  • Fractional Knapsack
• Graph
  • Representation
  • Finding a Path in a Graph
  • BFS - Breadth First Search
  • DFS - Depth First Search
  • CC - Connected Component
    • SCC - Strongly Connected Component
  • Topological Sort
    • Kahn’s Algorithm
  • Minimum Spanning Tree
    • Prim's Algorithm
    • Kruskal's Algorithm
  • Shortest Path
    • Dijkstra
    • Bellman-Ford
    • Floyd-Warshall
• State Space Search
  • State Space Tree Traversing
    • Search tree
    • BFS / DFS
  • State Space Tree Optimization
    • Backtracking
    • Branch-and-Bound
      • Best First Search / Least-Cost Search
• NP-Completeness
  • Decision Problem
  • Undecidability
  • Problem Reduction
  • P, NP, co-NP, NP-hard, NP-C
  • Cook–Levin theorem
  • Proof of NP-Completeness