Algorithm

🔥 2020-1학기 POSTECH 안희갑 교수님의 『Algorithm(CSED331)』을 수강하면서 공부한 내용을 정리하였습니다. 😁

PS에 대한 아티클은 요기👀에서 확인하실 수 있습니다 😎

알고리즘 정리를 마무리한 후기는 요기에서 확인하실 수 있습니다.

정규수업에서 다루지 않은 내용은 🎈로 표시하였습니다 😉

Computational Complexity

• Asymptotic Analysis
  • Big-O / Big-Omega / Big-Theta
  • little-o / little-omega / little-theta
• Master Theorem: Recurrence relations
• Fibonacci Number
  • Brute Force
  • DP
  • Matrix-based
• Convex Hull Algorithm
  • Brute Force
  • Graham’s Scan

Divide and Conquer

• Multiplication Algorithm: Karatsuba Algorithm
• Binary Search
  • Off-by-One
  • Approximate Matches
• Merge Sort
  • Skyline Problem 🎈
• Matrix Multiplication: Strassen Algorithm
• Quick Selection
• Closest pair of points

Graph Algorithm

• DFS and BFS
  • DFS and BFS - code
• DFS Tree
• Dijkstra’s Algorithm
• Bellman-Ford Algorithm
• DAG & Topological Sort

Greedy Algorithm

• MST; Minimum Spanning Tree
  • Kruskal’s Algorithm
  • Prim’s Algorithm
  • Disjoint Set & Path Compression
• Intervel Scheduling & Partitioning
• Huffman Encoding
• Clustering of Maximum Spacing

Dynamic Programming

• LIS; Longest Incresaing Subsequences
• Edit Distance
  • Dameraus-Levenshtein Distance 🎈
• Knapsack
• Chain Matrix Multiplication
• Shortest Reliable Paths
• All Pairs Shortest Paths; Floyd-Warshall
• TSP; Traveling Salesman Problem
  • 완전탐색
  • DP
• Independent Sets in Tree
• Weighted Interval Scheduling
• Segmented Least Squares

Linear Programming

• Linear Programming
• Simplex Method

Network Flow

• Max-Flow Min-Cut Theorem
• Ford-Fulkerson Algorithm & Edmons-Karp Algorithm
• Bipartite Matching
• Variations of Network Flow Problem
• Dinic Algorithm 🎈

NP & NP-complete

• P and NP
  • Satisfiability (SAT)
  • Traveling Salesman Problem (TSP)
  • Hamilton Cycle Problem (HCP)
  • Balanced Cut
  • 3D Matching
  • Integer Linear Programming 🎈
  • Independent Set, Vertex Cover, Clique
  • Longest Path, Subset Sum
• Reductions
  • Reduction and NP-complete
    • Mapping Reduction & Polynomial Reduction 🎈
    • NP-complete and NP-hard
  • Reduction (2)
    • 3-SAT → Independent-Set
    • Independent-Set → Vertex Cover
    • Independent-Set → Clique
    • 3-SAT → Clique
  • Reduction (3)
    • 3-SAT → 3D-Matching
  • Reduction (4): Circuit-SAT and Cook-Levin Theorem

Coping with NP-hardness

• Exhaustive Search
  • Backtracking
  • Branch-and-Bound
• Heuristic Algorithm
  • Local Search

Appendix

• Amortized Analysis 🎈
  • Accounting Method
• Implementations of Heap 🎈
  • Heap by unordered array & ordered array
  • Binary Heap
  • d-ary Heap
  • Binomial Heap
    • Binomial Tree
  • Lazy-Binomial Heap
  • Fibonacci Heap 🔥
• FFT; Fast Fourier Transformation 🎈

참고 교재

• 『Algorithms』 Dasgupta, international ed.
• 『알고리즘 문제해결전략』 구종만