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 includ

Size: px

Start display at page:

Download "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 includ"

정근 강
6 years ago
Views:

1 알고리즘설계와분석 (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); return A; 12. here Find(x) 1

2 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

3 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 Level 2 Merge-Lists(, + ) Level 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

4 Trim(*) here APPROX_SUBSET_SUM(*) Trim(, / ) APPROX_SUBSET_SUM(*) whichone i d i g i

5 character frequency a 10 e 15 i 12 s 3 t 5 sp(space) 13 nl(newline) 1 5

6 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

7 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

8 (herethere) extractmin(*) minheap->size extractmin(*) 수고했습니다. 8

Line (A) å j a k= i k #define max(a, b) (((a) >= (b))? (a) : (b)) long MaxSubseqSum0(int A[], unsigned Left, unsigned Right) { int Center, i; long Max

Line (A) å j a k= i k #define max(a, b) (((a) >= (b))? (a) : (b)) long MaxSubseqSum0(int A[], unsigned Left, unsigned Right) { int Center, i; long Max 알고리즘설계와분석 (CSE3081-2반 ) 중간고사 (2013년 10월24일 ( 목 ) 오전 10시30분 ) 담당교수 : 서강대학교컴퓨터공학과임인성수강학년 : 2학년문제 : 총 8쪽 12문제 ========================================= < 주의 > 답안지에답을쓴후제출할것. 만약공간이부족하면답안지의뒷면을이용하고반드시답을쓰는칸에답안지의어느쪽의뒷면에답을기술하였는지명시할것.