석사 입학 후 들었던 과목 중 하나입니다. 이 과목에서는 이름에서 알 수 있듯 알고리즘의 전반적인 것들을 배울 수 있었습니다. 연구와는 그리 큰 관련이 없는 듯싶었지만, 전산학도라면 알아 두어야 할 알고리즘 및 기초 내용에 대한 소개가 있어 좋았습니다.
여기에는 교수님께서 설명하신 것들을 필기한 자료들을 올립니다. 학부 때와 달리 수업에 큰 비중을 두지 않았기에 적지 못한 필기도 있지만, 어느 정도는 도움이 되지 않을까 하여 이렇게 스캔하여 보관하였습니다.
- 수업 소개 및 알고리즘의 기본적인 정의를 얘기합니다.
- 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에 대한 전반적인 설명입니다. 개인적으로는 재미있게 살펴보았고, 여기에 대해서 블로그에 정리글을 적으려고 하였으나 시간이 오래 걸려 간단히 여기에 필기 자료를 올리는 것으로 대체합니다.
- 마지막의 것은 기말 고사 대비 자료입니다.
CS500 Algorithm Lecture 01.pdf
CS500 Algorithm Lecture 02.pdf
CS500 Algorithm Lecture 03.pdf
CS500 Algorithm Lecture 05.pdf
CS500 Algorithm Lecture 06.pdf
CS500 Algorithm Lecture 07.pdf
CS500 Algorithm Lecture 08.pdf
CS500 Algorithm Lecture 09.pdf
CS500 Algorithm Lecture 10.pdf
CS500 Algorithm Lecture 12.pdf
CS500 Algorithm Lecture 13.pdf
CS500 Algorithm Lecture 14.pdf
CS500 Algorithm Lecture 15.pdf
CS500 Algorithm Lecture 16.pdf
CS500 Algorithm Lecture 17.pdf
CS500 Algorithm Lecture 18.pdf
CS500 Algorithm Lecture 19.pdf
CS500 Algorithm Lecture 20.pdf
CS500 Algorithm Lecture 21.pdf
CS500 Algorithm Lecture 22.pdf
CS500 Algorithm Lecture 23.pdf