.. Stack, 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

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

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

E. Solutions, 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

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

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

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

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

E. Solutions, 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

.. Optimal-algorithms-for-homogeneous-resources, 249 11.1.1 Dynamic-programming algorithm 250 11.1.2 Binary search algorithm, p.250

I. Searching, 109 xiii xiv 5.6 Splay trees, p.112

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

S. Single-machine, 213 9.5 Scheduling independent tasks in parallel, p.216