알고리즘설계와분석 (CSE3081(2 반 )) 기말고사 (2016년 12월15일 ( 목 ) 오전 9시40분 ~) 담당교수 : 서강대학교컴퓨터공학과임인성 < 주의 > 답안지에답을쓴후제출할것. 만약공간이부족하면답안지의뒷면을이용하고, 반드시답을쓰는칸에어느쪽의뒷면에답을기술하였는지명시할것. 연습지는수거하지않음. function MakeSet(x) { x.parent := x; x.rank := 0; function Find(x) { if (x.parent == x) return x; else return here ; function Union(x, y) { xroot := Find(x); yroot := Find(y); if (xroot == yroot) return; if ( there-1 ) xroot.parent := yroot; else if ( there-2 ) yroot.parent := xroot; else { yroot.parent := xroot; xroot.rank := xroot.rank + 1; Find(x) x here Union(x) there-1 there-2 Union(x) Union(x) Find(x) herethere function Find(x) { if (x.parent!= x) x.parent := herethere ; return x.parent; KRUSKAL(G, w) { 1. A := ; 2. for each v V 3. MakeSet(v); 4. Sort the edges in E by non-increasing weight; 5. for each edge (u, v) E in the sorted order { 6. if ( here ) { 7. A := A {(u, v); 8. Union(u, v); 9. 10. 11. return A; 12. here Find(x) 1
Let G = (V, E) be a connected, undirected graph with a real-valued weight function w defined on E. Let A be a set of E, possibly empty, that is included in some minimum spanning tree for G, let (S, V-S) be any cut of G that respects A, and let (u, v) be a light edge crossing (S, V-S). Then, edge (u, v) is safe for A. let (S, V-S) be any cut of G that respects A edge (u, v) is safe for A here 2
A linear ordering of all its vertices such that if G contains an edge (u, v), then here in the ordering. F[i][ j] = F[i][j] there ; return (F[n][L]); here there 3 Level 1 2 2 Level 2 Merge-Lists(, + ) 1 1 1 1 Level 3 0 0 0 0 0 0 0 0 Level 4 Trim(L, ) F[0][0] = TRUE; for (i = 1; i <= t; i++) F[0][i] = FALSE; for (i = 1; i <= n; i++) { for (j = 0; j <= t; j++) { F[i][ j] = here ; if ( j - x[i] >= 0) 3
Trim(*) here APPROX_SUBSET_SUM(*) Trim(, / ) APPROX_SUBSET_SUM(*) whichone i d i g i 1 3 120 2 1 115 3 4 105 4 1 100 5 3 90 6 2 85 7 6 80 8 4 50 9 5 40 4
character frequency a 10 e 15 i 12 s 3 t 5 sp(space) 13 nl(newline) 1 5
struct AdjListNode { int dest; int weight; struct AdjListNode* next; ; struct AdjList { struct AdjListNode *head; ; // Size of array will be V (number of vertices in graph) struct Graph { int V; struct AdjList* array; ; struct MinHeapNode { int v; int dist; ; struct MinHeap { int size; // Number of heap nodes present currently int capacity; // Capacity of min heap int *pos; // This is needed for decreasekey(). struct MinHeapNode **array; ; struct MinHeapNode* newminheapnode(int v, int dist) { struct MinHeapNode* minheapnode = (struct MinHeapNode*) malloc(sizeof (struct MinHeapNode)); minheapnode->v = v; minheapnode->dist = dist; return minheapnode; struct MinHeap* createminheap(int capacity) { struct MinHeap* minheap = (struct MinHeap*) malloc(sizeof(struct MinHeap)); minheap->pos = (int *) malloc(capacity * sizeof(int)); minheap->size = 0; minheap->capacity = capacity; minheap->array = (struct MinHeapNode**) malloc(capacity * sizeof(struct MinHeapNode*)); return minheap; void dijkstra(struct Graph* graph, int src) { int V = graph->v; int dist[n_max_vertices]; struct MinHeap* minheap = createminheap(v); for (int v = 0; v < V; ++v) { dist[v] = INT_MAX; minheap->array[v] = newminheapnode(v, dist[v]); minheap->pos[v] = v; minheap->size = V; dist[src] = 0; decreasekey(minheap, src, dist[src]); // Line C while (!isempty(minheap)) { struct MinHeapNode* minheapnode = extractmin(minheap); // Line A int u = minheapnode->v; struct AdjListNode* pcrawl = graph->array[u].head; while (pcrawl!= NULL) { // Point A int v = pcrawl->dest; if (isinminheap(minheap, v) && dist[u]!= INT_MAX && (here) < dist[v]) { dist[v] = (here) ; decreasekey(minheap, v, dist[v]); // Line B pcrawl = pcrawl->next; // print the calculated shortest distances printarr(dist, V); dijkstra(*) Line A extractmin(minheap); dijkstra(*) Point A dijkstra(*) Line A extractmin(minheap); dijkstra(*) Line B decreasekey(minheap, v, dist[v]); (here) decreasekey(*) void swapminheapnode(struct MinHeapNode** a, struct MinHeapNode** b) { struct MinHeapNode* t = *a; *a = *b; *b = t; 6
void decreasekey(struct MinHeap* minheap, int v, // Get the index of v in heap array int i = minheap->pos[v]; minheap->array[i]->dist = dist; while (i && minheap->array[i]->dist int dist) { < minheap->array[ (there) ]->dist) { minheap->pos[minheap->array[i]->v] = (there) ; minheap->pos[minheap->array[ (there) ]->v] = i; swapminheapnode(&minheap->array[i], i = (herethere) ; &minheap->array[ (there) ]); (there) decreasekey(*) (herethere) dijkstra(*) Line C dijkstra(*) extractmin(minheap) void minheapify(struct MinHeap* minheap, int idx) { int smallest, left, right; smallest = idx; left = (here) ; right = (there) ; // Line A = minheap->array[smallest]; MinHeapNode *idxnode = minheap->array[idx]; minheap->pos[smallestnode->v] = idx; minheap->pos[idxnode->v] = smallest; swapminheapnode(&minheap->array[smallest], (herethere) ; // Line B int isempty(struct MinHeap* minheap) { return minheap->size == 0; &minheap->array[idx]); struct MinHeapNode* extractmin(struct MinHeap* minheap) { if (isempty(minheap)) return NULL; struct MinHeapNode* root = minheap->array[0]; struct MinHeapNode* lastnode = minheap->array[minheap->size - 1]; minheap->array[0] = lastnode; minheap->pos[root->v] = minheap->size - 1; minheap->pos[lastnode->v] = 0; minheapify(minheap, 0); return root; minheapify(minheap, 1); if (left < minheap->size && minheap->array[left]->dist < minheap->array[smallest]->dist) smallest = left; if (right < minheap->size && minheap->array[right]->dist < minheap->array[smallest]->dist) smallest = right; if (smallest!= idx) { MinHeapNode *smallestnode Line A (here) (there) idx // Line B 7
(herethere) extractmin(*) minheap->size extractmin(*) 수고했습니다. 8