2011년 1학기 CS500 Algorithm Design and Analysis – 필기 자료

석사 입학 후 들었던 과목 중 하나입니다. 이 과목에서는 이름에서 알 수 있듯 알고리즘의 전반적인 것들을 배울 수 있었습니다. 연구와는 그리 큰 관련이 없는 듯싶었지만, 전산학도라면 알아 두어야 할 알고리즘 및 기초 내용에 대한 소개가 있어 좋았습니다.

여기에는 교수님께서 설명하신 것들을 필기한 자료들을 올립니다. 학부 때와 달리 수업에 큰 비중을 두지 않았기에 적지 못한 필기도 있지만, 어느 정도는 도움이 되지 않을까 하여 이렇게 스캔하여 보관하였습니다.

수업 소개 및 알고리즘의 기본적인 정의를 얘기합니다.
Minimum cut problem, Turing machine, Hamiltonian Path Problem, P and NP
Reduction, P and NP, NP-Hard and NP-Complete, SAT problem, Cook-Levin Theorem, 3SAT
이유를 모르겠으나 4번은 없네요.
Clique, Independent Set, Hamiltonian Path, Vertex Cover
Approximation Algorithm, Vertex-Cover, 2-Approximation for TSP
2-Approximation for TSP, Planar Graph, PTAS, MIS, k-outerplanar graph, Baker’s PTAS algorithm
Hardness of Approximation, Gap Problem, Gap-3SAT, PCP Theorem, Clique, Gap-Clique
Gap Preserving Reductions, Clique, Gap-Clique, Divide and Conquer, Iterative Substitution, Recursion Tree, Guess-and-Test Method, Master Theorem
Master Theorem, 0/1 Knapsack Problem, Dynamic Programming, Optimal Matrix-Parenthesization Problem
이유를 모르겠으나 11번은 없네요.
Optimal Matrix-Parenthesization Problem, All-Pairs Shortest Path Problem, Matrix multiplication problem, Floyd’s All-Pairs Shortest Path
Graph, Adjacency List, Adjacency Matrix, Single-Source Shortest Path, Dijkstra Algorithm
Single-Source Shortest Path, Dijkstra Algorithm, Minimum Spanning Tree, Prim Algorithm
Flow network, Maximum-flow problem, Ford-Fulkerson method, Residual network, Max-flow Min-Cut Theorem
Randomized Algorithm, Probabilistic Turing Machine, Las Vegas, Monte Carlo, Randomized Quick Sort, Random Sampling
Randomized Algorithm, Quick Sort, Random Sampling
Random Sampling, Chernoff Bound, Hit and Run Algorithm
Markov Chain, Random Walk, Stationary Distribution, Markov chain Monte Carlo, PageRank
Linear Programming, Simplex
Linear Programming, Convexity of Feasible Region, Ellipsoid Algorithm, Integer Programming, Cutting Plane Technique, Branch-and-Bound Technique, Solution tree
Branch-and-Bound Technique, Solution tree, String Pattern Matching, Rabin-Karp hash
KMP Algorithm, RSA, Fermat’s Theorem Euler Totient Funtion
Traditional Marriage Algorithm에 대한 전반적인 설명입니다. 개인적으로는 재미있게 살펴보았고, 여기에 대해서 블로그에 정리글을 적으려고 하였으나 시간이 오래 걸려 간단히 여기에 필기 자료를 올리는 것으로 대체합니다.
마지막의 것은 기말 고사 대비 자료입니다.