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

By | 2012/02/26

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

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

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

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

CS500 Algorithm Lecture 24.pdf

CS500 Algorithm Final Exam Note.pdf

Leave a Reply