Standford University

Graph Search, Shortest Paths, and Data Structures 강의 수강 후기

Coursera Standford University Algorithms 분야의 두 번째 강의인 Graph Search, Shortest Paths, and Data Structures의 수강을 완료했다. 수강 기간은 2020년 1월 29일 ~ 2020년 2월 21일.

  1. Divide and Conquer, Sorting and Searching, and Randomized Algorithms
  2. Graph Search, Shortest Paths, and Data Structures
  3. Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming
  4. Shortest Paths Revisited, NP-Complete Problems and What To Do About Them

첫 번째 강의보다 쉽고 재밌었다. 알고리즘보다 자료구조를 좋아하는 성향 때문인 것 같기도 하고, 수식이 덜 나와서 그런 것 같기도 하고, 무엇보다 Programming Assignment가 가장 재미있어서 매주 할당된 강의를 다 소화하기도 전에 관련 내용 공부가 끝나면 바로 도전했다. 이번에도 역시 Go언어를 사용했고 그 과정은 즐거웠다.

VSCode에서 Go언어로 Dijkstra’s Alrogithm 구현하기

공부한 주제들 중 비중있는 녀석들의 제목만 추려보면 다음과 같다.

  • Graph Search
    • Connected Components
    • Shortest Paths
      • Dijkstra’s Algorithm
  • Heap
  • Balanced Binary Search Tree
    • Red-Black Tree
  • Hash Table
    • Bloom Filter

2월 13일 아내의 복직 이후로 육아를 전담하게 되면서, 아이가 깨어나기 전 새벽에, 낮잠 잘 때, 잠든 후 밤 늦게 틈틈히 공부한다고 눈 앞에 보이는 주제에만 겨우 집중했는데, 4주 과정을 다 종합해보니 이렇게 많이 다뤘나 싶다.

Correctness에 대한 Proof, Performance에 대한 Analysis 그리고 틀린 시험 문제 등 100% 이해하지 못하고 넘어가는 부분들이 꺼림직하게 느껴질 때도 있지만, ‘공부를 이어나가는 게 어딘가’ 하는 핑계를 대어본다. 그래도 허락된 시간 안에서는 관련 자료도 찾아보면서 이해하려고 애썼던 기억이 난다. ‘회사에 있을 때 동료들과 같이 강의를 소화하면서 서로 모르는 것 물어보고 토론할 수 있었다면 더 좋았을텐데’ 하는 아쉬움이 남는다.

지금까지 3개의 Programming Assignment에서 Graph를 사용했는데, 3개의 Graph를 별도로 구현해야했다. 필요한 operation이 서로 다르고, 각 operation에 대하여 최적의 실행시간을 제공하기 위해선 내부 자료구조도 다를 수 밖에 없었기 때문이다. 반면에 최근 몇년간 업무에서 사용했던 자료구조는 대부분 프로그래밍 언어에서 제공하는 Hash Table을 확장한 수준을 벗어나지 못했다. 개발자로서 실력을 유지하려면 PS를 취미로 하는 등 별도의 개인적인 노력이 필요할 것 같다고 느꼈다.

세 번째 강의를 듣기 전에 2~3주 정도의 공백을 두려고 한다. 그 사이에는 Dijkstra’s Algorithm에서 Heap을 사용하는 버전을 Go언어로 구현해보고, 이 강의를 들으면서 시간 부족으로 중단했던 <Go 언어를 활용한 마이크로서비스 개발>의 진도를 뽑아볼 생각이다. Dijkstra’s Algorithm에서 사용하는 Heap은 중간 노드를 삭제할 수 있는 operation이 필요해서 직접 구현해야 하기 때문에 좋은 공부가 될 것 같다.

Divide and Conquer, Sorting and Searching, and Randomized Algorithms 강의 수강 후기

Coursera Standford University Algorithms 분야의 첫 번째 강의인 Divide and Conquer, Sorting and Searching, and Randomized Algorithms의 수강을 완료했다. 수강 기간은 2019년 12월 17일 ~ 2020년 1월 12일.

  1. Divide and Conquer, Sorting and Searching, and Randomized Algorithms
  2. Graph Search, Shortest Paths, and Data Structures
  3. Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming
  4. Shortest Paths Revisited, NP-Complete Problems and What To Do About Them

Tim Roughgarden 교수님 알고리즘 강의의 좋은점은 특정 패러다임(e.g., Randomized Algorithms)으로 분류되는 알고리즘(e.g., Random Contraction Algorithm)들 중 한 두개를 선택하여 동작 원리와 실행시간 분석을 증명을 포함하여 깊이있게 설명해준다는 점이다.

Divide and Conquer 알고리즘의 경우 알고리즘의 실행시간(~ # of lines of code)을 분석할 때, Recursion Tree 또는 The Master Method를 활용할 수 있는데, 매우 유용한 The Master Method를 처음 접했다는 사실이 의아했다. (학부, 대학원 때 수업을 아무리 대충 들었더라도 기억에 아주 없지는 않을텐데…)

The Master Method

Randomized 알고리즘을 분석하기 위해서는 Probability Theory의 몇 가지 기본 개념(Sample Space, Event, Random Variable, Expectation, Linearity of Expectation, Conditional Probability)들을 이해해야 한다. 이 역시 배운 기억이 없는…

Probability Theory를 활용한 QuickSort 실행시간 분석과정

증명 과정에서 특정 항을 같은 값을 가지는 다른 항으로 대체하거나, 특정 수식을 수학적으로 증명된 수식으로 대체하는 부분이 흥미로웠다.

Randomized Slection 알고리즘의 실행시간 분석과정에서, 재귀호출에 대한 기대값을 동전 던지기에 대한 기대값으로 치환

Karatsuba 알고리즘이나 Strassen 알고리즘처럼 변형된 수식을 도입해 기존 계산 결과를 활용하여 재귀 호출의 수를 줄이는 아이디어도 기억해두면 좋을 것 같다.

Strassen’s Algorithm

Programming Assignment #1~4는 모두 Go언어로 풀었는데 재밌었다. Go언어에 익숙하지 않아서 시간이 오래 걸리기도 하였지만, 그만큼 Go언어 코드 작성 능력을 향상시킬 수 있는 좋은 기회였다. 간단한 알고리즘 코드를 작성할 때도 상위 레벨에서 필요한 인터페이스를 먼저 설계하고, 그 인터페이스를 효율적으로 구현할 수 있는 자료구조를 선택하고, 인터페이스를 구현한 다음 유닛 테스트까지 꼭 작성해야 한다는 교훈을 얻었다. Random Contraction 알고리즘을 구현할 때 그래프 자료구조를 몇 번씩이나 다시 구현하게 된 원인은 그래프에 필요한 모든 인터페이스들을 종합적으로 고려하지 않았기 때문이었다.

매주 풀어야했던 Problem Set #1~4는 어려웠다. 뒤로 갈수록 점점 더 어려워져서 Final Exam 통과할 수 있을까 걱정이 컸는데, 다행히 Final Exam은 쉽게 나와서 한 번에 통과할 수 있었다. 영어가 부족하니 문제를 해석하는 것부터 버거운 경우도 있었고, 수학이 부족하니 수식을 다 세워놓고도 log 계산을 못해서 정확히 답을 도출하지 못하기도 했다. 때로는 자괴감을 느끼기도 했다.

가장 큰 소득은 실력이 부족하다는 것을 알게 된 것. 다음은 Divide and Conquer, Randomized 패러다임의 알고리즘을 설계할 때, 실행시간을 분석할 수 있는 수학적 도구를 얻게 된 것.

두 번째 강의는 구정 연휴 지나 1월 마지막 주에 시작할 예정이다. 그 사이에 수학의 기본기를 다질 수 있는 책을 찾아 보아야겠다.