114 Solution to Exercise 5.4: Deleting half the elements 115 Solution to Exercise 5.5: Searching and inserting 116 Solution to Exercise 5.6: Splay trees, p.119 ,

133 6.3.3 Growing the class NPC of NP-complete problems . . . 134 6.3.4 Optimization problems versus decision problems, p.135 ,

152 Exercise 7.10: Scheduling independent tasks with p processors 152 ix Exercise 7.11: Scheduling with two processors, p.152 ,

155 Solution to Exercise 7.1: Wheel 156 Solution to Exercise 7.2: Knights of the round table 156 Solution to Exercise 7.3: Variants of CLIQUE 158 Solution to Exercise 7.5: VERTEX-COVER with even degrees 158 Solution to Exercise 7, pp.3-166 ,

170 Solution to Exercise 7, NP-completeness of 2-PARTITION 177 ,

181 8.1.3 Traveling salesman problem (TSP), p.187 ,

202 8.5.1 Backtracking: The n queens 203 8.5.2 Branch-and-bound: The knapsack, p.206 ,

218 Exercise 9.9: Mixed integer linear program for replica placement, p.218 ,

219 Solution to Exercise 9.1: Single machine scheduling 219 Solution to Exercise 9 SUBSET 221 Solution to Exercise 9 223 Solution to Exercise 9, p.226 ,

249 11.1.1 Dynamic-programming algorithm 250 11.1.2 Binary search algorithm, p.250 ,

109 xiii xiv 5.6 Splay trees, p.112 ,

152 7.11 Scheduling with two processors, 13 INDEPENDENT SET, vol.153, issue.7, p.153 ,

213 9.5 Scheduling independent tasks in parallel, p.216 ,