In this post, 09 Algorithm lecture is introuduced.

CLRS chater 1 ~ 11 범위의 Quiz 의 내용을 다룬다.

Quiz 1

Yes / No (5 points each)

1. 임의의 배열 A[]에 대해 MAX-HEAPIFY(A, 0) 을 호출하면 Max-heap이 만들어진다.
2. n개의 element를 갖는 Max-heap에서 A[n-1] 은 최솟값이다.
3. Quick sort는 항상 Merge sort 보다 빠르다.
4. Quicksort는 stable sort이다.

Short answer (10 points each)

1. Heap is ( ) data structure ~.
2. A=[13, 2, 5, 25]에 대해서 BUILD-MAX-HEAP을 했을 때, A를 구하시오. ([25, 13, 2, 5] 가 답이도록 문제 주어짐)
3. Heap sort의 time complexity?
4. A=[5, 1, 4, 7, 6]에 대해서 PARTITION을 수행했을 때, A를 구하시오. ([5,1,4,6,7] 이 답이도록 문제 주어짐)
5. 15, 23, 35 가 hash function의 Key 값으로 들어오고, $h(k) = k \ mod \ 10$ 이고, linear-probing을 이용할 때, 각 key가 향하는 index를 구하시오.
6. MERGE(A, p, q, r)이 주어졌을 때, MERGE-SORT(A, p, r) 을 구현하라.
7. Case1의 Case2 중 Big-$O$ time complexity 관계는? (크다, 작다, 같다)

Case1 : $T(n) = 4T(n/2) + n^2$

Case2 : $T(n) = T(n/2) + n^2$

Essay question (10 points)

1. Simultaneous Min/Max 함수의 수도 코드를 작성하고 correctness를 보여라. 그리고 time-complexity를 구하라.