In this post, final exam of Algorithm lecture is introuduced. # Final  (간선 가중치는 위 그림과 다름. a->b:1, c->a:0, d->c:-1, a->d:0, b->c:2) 1. topological sort를 수행하시오. (10) 2. SCC (Strongluy Connected Component)를 구하시오. (10) 3. (20) - Floyd-Marshall 알고리즘을 이용하여, All pair Shortest Path를 구하시오. - matrix를 이용하여 d->b로의 weighted shortest path를 구하는 과정을 보이시오. 4. heapsort (30) - (10) BUILD-MAX-HEAP과 MAX-HEAPIFY(A, 1)이 주어질 때, HEAP-SORT를 구현하시오. - (10) HEAP-SORT 알고리즘의 correctness를 증명하시오. - (10) HEAP-SORT 알고리즘의 time-complexity를 증명하시오. 5. RANDOMIZED-SELECT (10) - 배열 A[p:r]에서 i번째 작은 원소를 찾는 RANDOMIZED-SELECT(A, p, r, i)를 구현하시오. 이 때, q=RANDOMIZED-PARTITION(A, p, r)이 주어진다. - 위 알고리즘의 correctness를 증명하시오. 6. MST 알고리즘의 DP foumulation을 쓰시오. (10) 7. (10) 서로 다른 금액의 $n$가지 동전 $\set{D_1, D_2, ..., D_n}$ 이 있고 각 동전을 중복 사용가능할때, target 금액 A를 맞출 수 있는 동전 조합의 가짓 수. 3+1=1+3 같은 것으로 취급) DP를 이용하여 구하는 방법 서술하시오. 
Leave a Comment