알고리즘설계와분석 (CSE3081(2 반 )) 기말고사 (2015년 12월17일 ( 목 ) 오전 9시 30분 ) 담당교수 : 서강대학교컴퓨터공학과임인성대상 : 2학년 2학기생 < 주의 > 문제지는총6쪽이며, 제공한답안지에답을쓴후제출할것. 만약공간이부족하면답안지의뒷면을이용하고반드시답을쓰는칸에어느쪽의뒷면에답을기술하였는지명시할것. 연습지는수거하지않음. 1. 다음은 Cormen 등의 Introduction to Algorithms라는책에서발췌한 Minimum Spanning Tree에대한정리및증명에관한문제이다. 가. 위의정리에서 cut (S, V - S) 란그래프 G의 vertex 집합 V를그의부분집합 S와나머지 V-S로 partition한것을의미한다. 이때 G의 edge 집합 E의부분집합 A에대해, cut (S, V S) 가 A를 respect 한다는것은위정리의문맥상무엇을뜻하는지정확히기술하라. 나. 위의정리에서가정한바와같이, A가어떤특정 minimum spanning tree의 edge들의집합의부분집합이라고하자. 이때 A에속하지않는어떤 edge (u, v) 가 A에대해 safe 하다는것을무엇을의미하는지정확히기술하라. 다. 위의정리에서 (HERE) 부분에는 E의 edge 중어떤 edge (u, v) 에대한설명이주어져있다. 문맥상 (u, v) 는어떤 edge이어야할까? 라. 아래그래프의 minimum spanning tree의총비용을얼마일까? 마. 위문제의그래프의 minimum spanning tree 는 unique 할까? ( 즉오로지한개만존재할까?) 예 / 아니 오 로답하고자신의답에대한이유를기술하라. 바. 다음은 adjacency matrix 를사용하여구현한 minimum spanning tree 코드이다. 그래프 G = (V, E) 에대해, n = V, m = E 라할때, 이방법의시간 복잡도를 Big-O 기호를사용하여기술하라. #define NOT_SELECTED 0 #define SELECTED 1 #define COST(G, I, J) ((G)->cost_matrix[(I)*(G)->n_v + (J)]) typedef struct _GRAPH { int n_v; int *cost_matrix; GRAPH; int find_next_vertex(int n_v, int *MinCost, int *Selected) { int w, min_cost, selected_w; min_cost = INT_MAX; for (w = 0; w < n_v; w++) { if (Selected[w] == NOT_SELECTED && MinCost[w] < min_cost) { min_cost = MinCost[w]; selected_w = w; if (min_cost == INT_MAX) return -1; else return selected_w; int MST_Prim(GRAPH *graph_ptr) { int i, v_next, w, *int_ptr[3]; int *Parent, *MinCost, *Selected; if (allocate_int_arrays(3, graph_ptr->n_v, int_ptr) == -1) return -1; Parent = int_ptr[0]; MinCost = int_ptr[1]; Selected = int_ptr[2]; for (i = 0; i < graph_ptr->n_v; i++) { MinCost[i] = INT_MAX; Selected[i] = NOT_SELECTED; MinCost[0] = 0; Parent[0] = 0; for (i = 0; i < graph_ptr->n_v - 1; i++) { v_next = find_next_vertex(graph_ptr->n_v, MinCost, Selected); if (v_next == -1) { <HERE2> fprintf(stderr, "(... )"); return -1; Selected[v_next] = SELECTED; for (w = 0; w < graph_ptr->n_v; w++) { <HERE4> if (Selected[w] == NOT_SELECTED && <HERE3> ) { Parent[w] = v_next; MinCost[w] = COST(graph_ptr, v_next, w); print_any_mst_information_here(graph_ptr, Parent, 0); free_int_arrays(3, int_ptr); return 0; 1
사. 위코드에서 <HERE2> 에서와같이변수 v_next 가 1인경우에는이그래프에어떤문제가있다는것을암시하는것일까? 아. 위코드에서 <HERE3> 에들어갈내용을 C/C++ 언어문법에맞게정확히기술하라. 자. 위구현의골격을유지하면서그래프에대한자료구조만 adjacency matrix에서 adjacency list로바꾸어다시구현한다고가정하자. 이때 <HERE4> 의 for 문장내부의계산이 minimum spanning tree를구하는데필요한총계산중얼마만큼의비용을차지할지, 위문제에서정의한 n과 m에대해 Big-O 기호를사용하여기술하라. 2. 주어진양의정수 k에대해 n = 2 k -1개의노드를가지는 full binary tree T n 의노드를루트노드부터시작하여레벨별로하나씩방문하면서어떤계산을수행하려한다. ( 아래의그림은 k = 4, 즉 n = 15인경우의트리를도시하고있는데, 루트노드의레벨은 1로가정함 ) 가. 만약각노드에대한계산비용이각노드가속한레벨 l에대해 k-l이라할경우에대해, T n 에대한전체처리비용 C(n) 은얼마가될지그값을정확하게 n의함수로표현하라. ( 주의 : 계산량을와같은식으로표현한후자신의답에이르게된계산과정을기술할것 ) 3 Level 1 2 2 Level 2 1 1 1 1 Level 3 0 0 0 0 0 0 0 0 Level 4 나. 이때의시간복잡도를 n에대하여 Big-O 기호를사용하여기술하라. 다. 이문제의계산비용을 n이아니라 k의함수로 D(k) 와같이표현한다고할때, k = 1, 2, 3,... 에대해 D(k) 를 recurrence relation을사용하여기술하라. 3. 다음은 Heap Sort 방법의구현에관한문제이다. 가. 아래코드에서 (A) 에들어갈내용을 C/C++ 언어문법에맞게정확히기술하라. 나. 아래코드의 (B) 와 (C) 에들어갈내용을 C/C++ 언어문법에맞게정확히기술하라. 다. list[] 배열의 list[1] 부터 list[10] 까지의장소에다음과같이 10개의정수가저장되어있다고하자. (25, 0, 78, 48, 61, 13, 59, 15, -1, 18) 만약이상태의배열에대해 adjust(list, 2, 10); 과같은함수를호출할경우위배열의내용이어떻게변할지기술하라. 라. list[] 배열의 list[1] 부터 list[10] 까지의장소에다음과같이 10개의정수가저장되어있다고하자. (60, 48, 59, 15, 19, 11, 26, 5, 0, 78) 만약이상태의배열에대해 SWAP(list[1], list[9], temp); adjust(list, 1, 8); 과같은함수를호출할경우위배열의내용이어떻게변할지기술하라. 마. n개의원소를가지는배열 list[] 에대해위의 heapsort() 함수를호출할경우, 이함수의첫번째 for 문장수행에필요한계산비용을 Big-O 기호를사용하여기술하라. 바. ( 위문제에대해 ) 두번째 for 문장수행에필요한계산비용을 Big-O 기호를사용하여기술하라. 2
4. 다음은 min-max heap 에관한문제이다. 가. list[] 배열의 list[1] 부터 list[12] 까지의장소에 아래와같이저장되어있는 min-max heap 에서값이 5 인원소를삽입한후의 list[1] 부터 list[13] 까지의내용 을기술하라. (7, 70, 40, 30, 9, 10, 15, 45, 50, 30, 20, 12) 나. list[] 배열의 list[1] 부터 list[12] 까지의장소에 아래와같이저장되어있는 min-max heap 에서가장 작은원소를제거한후의 list[1] 부터 list[11] 까지의내 용을기술하라. (7, 70, 40, 30, 9, 10, 15, 45, 50, 30, 20, 12) 다. 다음은 min-max heap 에서가장작은원소를제 거해주는함수이다. 문맥상 min_element() 함수가찾 아주는원소의인덱스의범위를기술하라. ( 만약인덱 스가 4, 5, 6, 7, 8, 9 의값을가질수있다면 [4, 9] 와 같이기술할것. 배열의크기는매우크다고가정함 ) element del_min(element heap[], int *s) { int i, last, m, parent; element temp, x; if (!(*s)) { heap[0].key = INT_MAX; return(heap[0]); heap[0] = heap[1]; x = heap[(*s)--]; for (i = 1, last = (*s) / 2; i <= last; ) { m = min_element(i, *s); if (x.key <= heap[m].key) break; <CASE-A> heap[i] = heap[m]; if (m <= <HERE> ) { i = m; break; <CASE-B> parent = m / 2; if (x.key > heap[parent].key) SWAP(heap[parent], x, temp); <CASE-C> i = m; heap[i] = x; return heap[0]; 라. 이함수가제대로작동하기위해서 <HERE> 에 들어갈내용을 C/C++ 언어문법에맞게정확히기술 하라. 마. 다음그림의네가지경우중프로그램의 <CASE-A> 옆의 break; 문장이수행되는경우의번호 를모두기술하라. [ 경우 1] [ 경우 2] [ 경우 3] [ 경우 4] 바. 위그림의네가지경우중프로그램의 <CASE-B> 옆의 break; 문장이수행되는경우의번호를모두기술하라. 사. 위그림의네가지경우중프로그램의 <CASE-C> 옆의매크로함수가수행되는경우의번호를모두기술하라. 3
5. 다음은 Dijkstra 의 Single-source Shortest Path 알 고리즘에관한문제이다. 가. 다음과같은 weighted directed graph 에대해, vertex A를 source vertex로하여 Dijkstra의알고리즘을적용할경우생성되는 (A를 root로하는 ) spanning tree를그려라. ( 화살표방향에주의할것 ) 나. 아래는이알고리즘을단계적으로기술하고있다. 6. 다음은 Floyd-Warshall 알고리즘에관한문제이다. 여기서 l(u,v) 는서로다른 vertex u와 v에대해어떤값을가진다고가정할지, u와 v 사이에꼭지점이있을경우와그렇지않을경우로나누어기술하라. 다. 문맥상 8번문장에서지워진부분에들어갈내용을위알고리즘의기호를사용하여정확히기술하라. 라. V = n이고 E = m인그래프 G = (V, E) 를내부적으로 adjacency matrix를사용하여표현할경우, 위알고리즘의시간복잡도를 Big-O 기호를사용하여표현하라. 마. 이문제의마지막에는위에서기술한알고리즘이올바르게원하는결과를산출한다는사실에대한간략한증명이주어져있다. 여기서 (HERE) 에들어갈내용을 v 0, v, S 등의기호를사용하여정확히기술하라. 바. (HERE2) 부분에서 v는 P의어떤 vertex를의미할지기술하라. 사. (HERE3) 부분에서공통적으로들어갈수식을기술하라. 가. 이문제를다음과같은 recurrence relation을사용하여해결하려한다. 과연여기서 A k [i][j] 는어떤값을가지는변수인지정확히기술하라. 나. 위의식에서 (HERE) 에들어갈수식을기술하라. 다. n개의 vertex로구성된그래프 G에대해위의식을사용하여가급적효율적으로문제를풀려고할때의시간복잡도를 Big-O 기호를사용하여기술하라. 라. 바로위문제의시간복잡도를얻기위하여사용한알고리즘설계방법의이름은무엇일까? 4
7. 다음은 Huffman 코딩알고리즘에관한문제이다. 가. 압축을하려하는어떤문서를분석한결과각문 자에대한빈도수는다음과같다. 함을보이는증명에관한그림이다. 문자 A B C D E F 빈도수 46 13 20 10 5 6 이때 Huffman 코딩알고리즘의수행결과생성되는각 문자의 Huffman 코드를기술하라. ( 주의 : 본알고리즘 에서이진트리구축시항상빈도수가낮은노드나트 리가왼쪽 ( 비트 0 에해당하는쪽 ) 에와야함. 빈도수가 같은경우, height 가낮은트리가왼쪽에오며, 둘다 동일할경우 A 쪽에가까운문자를포함하는트리가왼 쪽에옴 ) 나. 아래의코드는 Huffman 트리를구축해주는코드의 일부이다. 문맥상 <HERE> 와 <HERE2> 부분에들어 갈내용을 C/C++ 언어문법에맞게정확히기술하라. typedef struct _node { char symbol; int freq; struct _node *left; struct _node *right; NODE; NODE *u, *v, *w; for (i = 1; i <= n; i++) { <HERE3> /* insert the n single-node trees */ for (i = 1; i <= n-1; i++) { <HERE> w = make_a_new_node(); w->left = u; w->right = v; w->freq = <HERE2>; PQ_insert(w); w = PQ_delete(); 다. 위프로그램에서 min heap 에기반을두어 priority queue 를구현한다고가정하자. 이때 <HERE3> 의 for 문장에대한계산을최대한효율적으로구현한다고할 때걸리는시간을 Big-O 기호를사용하여기술하라. 라. 위프로그램에서 min heap 이아니라 sorted array 에기반을두어 priority queue 를구현한다고가정하자. 이때위의프로그램의수행하는데필요한총시간비용 을 Big-O 기호를사용하여기술하라. 마. Huffman 코딩알고리즘은각각의문자를한개의 원소를가지는트리로초기화한후, 반복적으로두개 의트리를선택하여결합하면서한개의트리가나올 때까지진행된다. ( 즉위의프로그램에서와같이 n 개의 문자에대해 n-1 번의동일한과정이반복된다 ) 이때 매단계에서어떤두트리가선택이되는지정확히기 술하라. 바. 다음은 Huffman 코딩기법이최적의코드를생성 이제다음과같은 Huffman 코딩알고리즘에대한증명의일부를살펴보자. S를 i 번째단계라끝났을때까지구축된트리들의집합이라고하자. 또한 u와 v를각각현재 (i+1) 번째단계에서결합이되는두트리의루트노드라하자. 만약 u 와 v가최적의트리 T에서형제관계라면증명끝. 만약그렇지않다면 ( 위의그림에서와같이 ) u의깊이가 v의깊이보다같거나크고, 이때 T에서 w가 u의형제라고가정하자. 이때 w를루트노드로하는 T의 branch를생각하면, 이 branch는 S에속하는트리이거나 S의트리들을내부에포함한다. ( 왜냐하면, u를루트로하는 branch가 S에속해야하므로, S의트리가 w 노드를벗어날수없음 ) 지금어떤노드 u에대해 f(u) 를 u를 root로하는 branch에포함되는모든문자들의빈도수의합이라고하자. 위에서밑줄친마지막문장은 f(u), f(v), 그리고 f(w) 값간에어떤관계를암시하는지, 이를수식으로정확히표현하라. 사. ( 위문제에이어 ) 지금어떤노드 u에대해 d(u) 를해당트리내에서 u의 root node로부터의깊이라하자. 위그림에서왼쪽트리 T에대해각각 v와 w를루트로하는 branch를서로바꾸어새로운트리 T'( 오른쪽트리 ) 를생성하였는데, 이때전체문서를암호화하는데있어증가하는비용 bit(t') - bit(t) 를위의 d() 와 f() 함수를사용하여표현하라. 8. 다음과같은 scheduling 문제를고려하자. 가. 아래에주어진 11개의 activity로구성된집합 A에 5
대해위문제에서요구하는 activity 집합 S 를구하라. ( 즉 A 의부분집합인 S 의원소들을해당하는 a i 들로표 현할것 ) i 1 2 3 4 5 6 7 8 9 10 11 s i 3 3 0 1 11 8 5 2 6 5 8 f i 6 8 6 4 14 12 9 13 10 7 11 나. 다음은이문제를해결해주는한알고리즘의일부 이다. 이알고리즘이올바르게작동하기위하여어느 부분에어떠한계산이추가되어야하는지정확히기술 하라. 다. 문제의크기 n 에대하여위알고리즘의시간복잡 도 ( 위문제의내용이추가된후 ) 를 Big-O 기호를사용 하여표현하라. 9. 다음과같은 scheduling 문제를고려하자. 아래에주어진 6 개의 job 으로구성된집합 J 에대해위 문제에서요구하는최적의 schedule S 를구하라. ( 답은 수행이되는순서대로 job 의번호를기술하고, 최종 maximum lateness L 값을기술할것 ) i 1 2 3 4 5 6 t i 2 1 3 3 4 2 d i 15 8 6 14 9 7 10. 다음의단답식질문에답하라. 가. V = n 인 undirected graph G = (V, E) 의임 의의두 vertex 사이에는항상정확히한개의 path 만 이존재할때, 이그래프의 E 값은? 나. 다음은 forest 라는그래프의정의이다. A forest is an undirected graph, all of whose connected components are trees. V = n 이고 E = m 인 forest G = (V, E) 가 k 개 의 connected component를가질경우, m을 n과 k의식으로표현하라. 다. 어떤 undirected graph가 simple graph라는것은넓은의미의 general graph에서어떤두가지경우가없어야한다. 그두가지가무엇일까? 라. 다음괄호안에들어갈정확한용어를영어단어로기술하라. Two vertices v and w of a graph G are said to be adjacent if there is an edge joining them. The vertices v and w are then said to be ( ) to such an edge. 마. 다음괄호안에들어갈정확한용어를영어단어로기술하라. A simple graph in which every pair of distinct vertices are adjacent is called a ( ) graph. 바. 다음괄호안에들어갈정확한용어를영어단어로기술하라. A ( ) is a connected graph that has no articulation points. 사. V = n이고 E = m인그래프 G = (V, E) 를 adjacency matrix로표현한후, depth first search를수행할경우시간복잡도를 Big-O 기호를사용하여표현하라. 아. V = n이고 E = m인그래프 G = (V, E) 를 adjacency list로표현한후, 한꼭지점 u에서또다른꼭지점 v까지경로가존재하는지여부를가급적효율적으로판별하려한다. 이러한계산의시간복잡도를 Big-O 기호를사용하여표현하라. 자. 그래프에대한추가적인정보가없는상태에서 insert edge, find if v is isolated, destroy, remove edge 등의그래프연산중 adjacent matrix나 adjacent list 중어떤자료구조를사용하여구현하건 ( 최악의경우의 ) 비용이동일한연산은어떤것이며, 그때의비용을위문제의 n과 m을사용하여 Big-O 기호를통하여기술하라. 차. V = n인 tree graph G = (V, E) 를 adjacency matrix로표현한후, breadth first search를수행할경우시간복잡도를 Big-O 기호를사용하여 n 의함수로표현하라. 카. V = n인 tree graph G = (V, E) 를 adjacency list로표현한후, breadth first search를수행할경우시간복잡도를 Big-O 기호를사용하여 n의함수로표현하라. 수고많았습니다! 6