Unit 5: Greedy Algorithms
․Course contents: ⎯ ⎯ ⎯ ⎯ ⎯
Elements of the greedy strategy Activity selection Knapsack problem Huffman codes Task scheduling
․Reading: ⎯
Unit 5
Chapter 16
Y.-W. Chang
1
Greedy Algorithm: Vertex Cover ․ A vertex cover of an undirected graph G=(V, E) is a subset V' ⊆ V such that if (u, v) ∈ E, then u ∈ V' or v ∈ V', or both. ⎯
The set of vertices covers all the edges.
․ The size of a vertex cover is the number of vertices in the cover. ․ The vertex-cover problem is to find a vertex cover of minimum size in a graph. ․ Greedy heuristic: cover as many edges as possible (vertex with the maximum degree) at each stage and then delete the covered edges. ․ The greedy heuristic cannot always find an optimal solution! ⎯
Unit 5
The vertex-cover problem is NP-complete.
Y.-W. Chang
2
A Greedy Algorithm ․ A greedy algorithm always makes the choice that looks best at the moment. ․ An Activity-Selection Problem: Given a set S = {1, 2, …, n} of n proposed activities, with a start time si and a finish time fi for each activity i, select a maximum-size set of mutually compatible activities. ⎯ If selected, activity i takes place during the half-open time interval [si, fi). ⎯ Activities i and j are compatible if [si, fi) and [sj, fj) do not overlap (i.e., si ≥ fj or sj ≥ fi).
Unit 5
Y.-W. Chang
3
Activity Selection
Unit 5
Y.-W. Chang
4
The Activity-Selection Algorithm Greedy-Activity-Selector(s,f) /* Assume f1 ≤ f2 ≤ … ≤ fn. */ 1. n ← length[s]; 2. A ← {1}; 3. j ← 1; 4. for i ← 2 to n 5. if si ≥ fj 6. A ← A ∪ {i}; 7. j ← i; 8. return A.
․Time complexity excluding sorting: O(n)
․ Theorem: Algorithm Greedy-Activity-Selector produces solutions of maximum size for the activity-selection problem. ⎯
⎯
⎯
Unit 5
(Greedy-choice property) Suppose A ⊆ S is an optimal solution. Show that if the first activity in A activity k ≠ 1, then B = A - {k} ∪ {1} is an optimal solution. (Optimal substructure) Show that if A is an optimal solution to S, then A' = A - {1} is an optimal solution to S' = {i ∈ S: si ≥ f1}. Prove by induction on the number of choices made. Y.-W. Chang
5
Elements of the Greedy Strategy
․When to apply greedy algorithms? ⎯
⎯
Greedy-choice property: A global optimal solution can be arrived at by making a locally optimal (greedy) choice. Dynamic programming needs to check the solutions to subproblems. Optimal substructure: An optimal solution to the problem contains within its optimal solutions to subproblems. E.g., if A is an optimal solution to S, then A' = A - {1} is an optimal solution to S' = {i ∈ S: si ≥ f1}.
․Greedy algorithms (heuristics) do not always produce optimal solutions. ․Greedy algorithms v.s. dynamic programming (DP) ⎯ ⎯ ⎯
Unit 5
Common: optimal substructure Difference: greedy-choice property DP can be used if greedy solutions are not optimal. Y.-W. Chang
6
Knapsack Problem ․ Knapsack Problem: Given n items, with ith item worth vi dollars and weighing wi pounds, a thief wants to take as valuable a load as possible, but can carry at most W pounds in his knapsack. ․ The 0-1 knapsack problem: Each item is either taken or not taken (0-1 decision). ․ The fractional knapsack problem: Allow to take fraction of items. ․ Exp: = (60, 100, 120), = (10, 20, 30), W = 50
․ Greedy solution by taking items in order of greatest value per pound is optimal for the fractional version, but not for the 0-1 version. ․ The 0-1 knapsack problem is NP-complete, but can be solved in O(nW) time by DP. (A polynomial-time DP??) Unit 5
Y.-W. Chang
7
Coding
․Is used for data compression, instruction-set encoding, etc. ․Binary character code: character is represented by a unique binary string ⎯ Fixed-length code (block code): a: 000, b: 001, …, f: 101 ⇒ ace ↔ 000 010 100. ⎯ Variable-length code: frequent characters ⇒ short codeword; infrequent characters ⇒ long codeword
Unit 5
Y.-W. Chang
8
Binary Tree v.s. Prefix Code
․Prefix code: No code is a prefix of some other code.
Unit 5
Y.-W. Chang
9
Optimal Prefix Code Design ․ Coding Cost of T: B(T)=∑ c ∈ C f(c)dT(c) c : each character in the alphabet C ⎯ f(c): frequency of c ⎯ dT(c): depth of c's leaf (length of the codeword of c) ․ Code design: Given f(c1), f(c2), …, f(cn), construct a binary tree with n leaves such that B(T) is minimized. ⎯ Idea: more frequently used characters use shorter depth. ⎯
Unit 5
Y.-W. Chang
10
Huffman's Procedure ․ Pair two nodes with the least costs at each step.
Unit 5
Y.-W. Chang
11
Huffman's Algorithm Huffman(C) 1. n ← |C|; 2. Q ← C; 3. for i ← 1 to n -1 4. z ← Allocate-Node(); 5. x ← left[z] ← Extract-Min(Q); 6. y ← right[z] ← Extract-Min(Q); 7. f[z] ← f[x] + f[y]; 8. Insert(Q, z); 9. return Extract-Min(Q)
․Time complexity: O(n lg n). ⎯ ⎯
Unit 5
Extract-Min(Q) needs O(lg n) by a heap operation. Requires initially O(n lg n) time to build a binary heap.
Y.-W. Chang
12
Huffman’s Algorithm: Greedy Choice
․Greedy choice: Two characters x and y with the lowest frequencies must have the same length and differ only in the last bit.
Unit 5
Y.-W. Chang
13
Huffman's Algorithm: Optimal Substructure
․Optimal substructure: Let T be a full binary tree for an optimal prefix code over C. Let z be the parent of two leaf characters x and y. If f [z] = f [x] + f [y], tree T' = T {x, y} represents an optimal prefix code for C'= C - {x, y} ∪ {z}.
Unit 5
Y.-W. Chang
14
Task Scheduling ․ The task scheduling problem: Schedule unit-time tasks with deadlines and penalties s.t. the total penalty for missed deadlines is minimized. ⎯ ⎯ ⎯
S = {1, 2, …, n} of n unit-time tasks. Deadlines d1, d2, …, dn for tasks, 1 ≤ di ≤ n. Penalties w1, w2, …, wn : wi is incurred if task i misses deadline.
․ Set A of tasks is independent if ∃ a schedule with no late tasks. ․ Nt(A): number of tasks in A with deadlines t or earlier, t = 1, 2, …, n. ․ Three equivalent statements for any set of tasks A 1. 2. 3.
Unit 5
A is independent. Nt(A) ≤ t, t = 1, 2, …, n. If the tasks in A are scheduled in order of nondecreasing deadlines, then no task is late. Y.-W. Chang
15
Greedy Algorithm: Task Scheduling
․ The optimal greedy scheduling algorithm: 1. 2. 3.
4.
Unit 5
Sort penalties in non-increasing order. Find tasks of independent sets: no late task in the sets. Schedule tasks in a maximum independent set in order of nondecreasing deadlines. Schedule other tasks (missing deadlines) at the end arbitrarily.
Y.-W. Chang
16
Two-layer Channel Routing ․ Local density at column i: total # of nets that cross column i. ․ Channel density: maximum local density. ․ # of horizontal tracks required ≥ channel density.
Unit 5
Y.-W. Chang
17
Standard Cell Layout
Unit 5
Y.-W. Chang
18
Channel Routing Problem ․ Assignments of horizontal segments of nets to tracks. ․ Assignments of vertical segments to connect. ⎯ ⎯
horizontal segments of the same net in different tracks, and the terminals of the net to horizontal segments of the net.
․ Horizontal and vertical constraints must not be violated. ⎯
⎯
Horizontal constraints between two nets: The horizontal span of two nets overlaps each other. Vertical constraints between two nets: There exists a column such that the terminal on top of the column belongs to one net and the terminal on bottom of the column belongs to the other net.
․ Objective: Channel height is minimized (i.e., channel area is minimized). Horizontal constraint
Unit 5
Y.-W. Chang
19
2-L Channel Routing: Basic Left-Edge Algorithm
․ No vertical constraint. ․ One layer for horizontal nets, one for vertical nets. ․ Doglegs are not allowed. ․ Treat each net as an interval. ․ Greedy Algorithm ⎯ ⎯ ⎯
Intervals are sorted according to their left-end x-coordinates. Intervals (nets) are routed one-by-one according to the order. For a net, tracks are scanned from top to bottom, and the first track that can accommodate the net is assigned to the net.
․ Optimality: produces a routing solution with the minimum # of tracks if no vertical constraint.
Unit 5
Y.-W. Chang
20
Basic Left-Edge Algorithm Basic_Left-Edge(U, track[j]) /* U: set of unassigned intervals (nets) I1, …, In; */ /* Ij=[sj, ej]: interval j with left-end x-coordinate sj and right-end ej; */ /* track[j]: track to which net j is assigned. */ 1. U ← { I1, I2, …, In}; 2. t ← 0 ; 3. while (U ≠ ∅ ) 4. t ← t + 1; 5. watermark ← 0; 6. while (there is an Ij ∈ U s.t. sj > watermark) 7. Pick the interval Ij ∈ U with sj > watermark, nearest watermark; 8. track[j] ← t; 9. watermark ← ej; 10. U ← U - {Ij};
Unit 5
Y.-W. Chang
21
Basic Left-Edge Example ․ U = {I1, I2, …, I6}. ⎯
I1 = [1, 3], I2 = [2, 6], I3 = [4, 8], I4 = [5, 10], I5= [7, 11], I6 = [9, 12].
․ t =1: ⎯ ⎯ ⎯
Route I1: watermark = 3; Route I3: watermark = 8; Route I6: watermark = 12;
․ t = 2: ⎯ ⎯
Route I2: watermark = 6; Route I5: watermark = 11;
․ t = 3: Route I4
Unit 5
Y.-W. Chang
22
Over-the-Cell Routing ․ Routing over the cell rows is possible due to the limited use of the 2nd (M2) metal layers within the cells. ․ Divide the over-the-cell routing problem into 3 steps: (1) routing over the cell, (2) choosing the net segments, and (3) routing within the channel. ․ Reference: Cong & Liu, “Over-the-cell channel routing,” IEEE TCAD, Apr. 1990.
Unit 5
Y.-W. Chang
23
Over-the-Cell Channel Routing
․Cong & Liu, “Over-the-cell channel routing,” IEEE TCAD, Apr. 1990.
Unit 5
Y.-W. Chang
24
Supowit's Algorithm ․ Supowit, “Finding a maximum plannar subset of a set of nets in a channel,” IEEE TCAD, 1987. ․ Problem: Given a set of chords, find a maximum plannar subset of chords. ⎯ ⎯
⎯
Label the vertices on the circle 0 to 2n-1. Compute MIS(i, j): size of maximum independent set between vertices i and j, i < j. Answer = MIS(0, 2n-1).
Vertices on the circle Unit 5
Y.-W. Chang
25
Dynamic Programming in Supowit's Algorithm
․Apply dynamic programming to compute MIS(i, j ).
Unit 5
Y.-W. Chang
26