Analysis of Algorithms : An Active Learning Approach

8.2 TYPICAL NP PROBLEMS 223 number of terms, the possible combination of trues and falses that would have to be checked can get ...

224 NONDETERMINISTIC ALGORITHMS 8.3 What Makes Something NP? We have looked at a lot of problems that are in the class P and a h ...

8.3 WHAT MAKES SOMETHING NP? 225 combinations from consideration.^3 So instead, we need to look at all of them. If we could exam ...

226 NONDETERMINISTIC ALGORITHMS one has been able to prove that the smallest lower bound for these problems must be larger than ...

8.4 TESTING POSSIBLE SOLUTIONS 227 ate in polynomial time. This section will look at algorithms that check pro- posed solutions ...

228 NONDETERMINISTIC ALGORITHMS return yes else return no end if The requirement of the class NP is that we are able to check th ...

8.4 TESTING POSSIBLE SOLUTIONS 229 for j = 1 to N do for k = 1 to graph[j].edgeCount do if (colors[j] = colors[ graph[j].edge[k] ...

This page intentionally left blank ...

Chapter 9 Other Algorithmic Techniques PREREQUISITES Before beginning this chapter, you should be able to Write and explain an ...

232 OTHER ALGORITHMIC TECHNIQUES should also try to answer any questions before reading on. A hint or the answer is in the sente ...

9.1 GREEDY APPROXIMATION ALGORITHMS 233 and Value(Soptimal)≥ Value(S) for all S∈ PSI if the problem is a maximization problem. ...

234 OTHER ALGORITHMIC TECHNIQUES technique to find an approximate algorithm. The cost of traveling between cit- ies could be rep ...

9.1 GREEDY APPROXIMATION ALGORITHMS 235 ■ 9.1.2 Bin Packing Approximations One technique to approximate the bin packing problem ...

236 OTHER ALGORITHMIC TECHNIQUES first fit, we will use the optimal three bins. If we sort first, we get the list (0.8, 0.6, 0.5 ...

9.1 GREEDY APPROXIMATION ALGORITHMS 237 pass of this algorithm considers additional cases. The first pass begins with the empty ...

238 OTHER ALGORITHMIC TECHNIQUES For example, with a set of items of sizes {27, 22, 14, 11, 7, 1} and an upper limit on the size ...

9.1 GREEDY APPROXIMATION ALGORITHMS 239 a polynomial algorithm that could color any graph with no more than twice as many colors ...

240 OTHER ALGORITHMIC TECHNIQUES only when an object will not fit in any of the current bins. Write an algo- rithm for best fit. ...

9.2 PROBABILISTIC ALGORITHMS 241 Buffon’s Needle Let’s say that you have a set of 355 sticks and the lengths of these sticks are ...

242 OTHER ALGORITHMIC TECHNIQUES shape. We would just generate random points in a surrounding square and determine the ratio tha ...