viii Contents 6.The Efficiency of Algorithms 129 or,Getting It Done Cheaply Part lll.Limitations and Robustness 157 7.Inefficiency and Intractability 159 or,You Can't Always Get It Done Cheaply 8.Noncomputability and Undecidability 191 or,Sometimes You Can't Get It Done At All! 9.Algorithmic Universality and Its Robustness 219 or,The Simplest Machines That Get It Done Part IV.Relaxing the Rules 255 10.Parallelism,Concurrency,and Alternative Models 257 or,Getting Lots of Stuff Done at Once 11.Probabilistic Algorithms 297 or,Getting It Done by Tossing Coins 12.Cryptography and Reliable Interaction 317 or,Getting It Done in Secret Part V.The Bigger Picture 335 13.Software Engineering 337 or,Getting It Done When It's Large ■14.Reactive Systems 357 or,Getting It to Behave Properly Over Time 15.Algorithmics and Intelligence 379 or,Are They Better at It Than Us?P1: GIG PE002-FM PE002-Harel PE002-Harel-FM-v1.cls March 19, 2004 19:35 viii Contents ■ 6. The Efficiency of Algorithms 129 or, Getting It Done Cheaply Part III. Limitations and Robustness 157 ■ 7. Inefficiency and Intractability 159 or, You Can’t Always Get It Done Cheaply ■ 8. Noncomputability and Undecidability 191 or, Sometimes You Can’t Get It Done At All! ■ 9. Algorithmic Universality and Its Robustness 219 or, The Simplest Machines That Get It Done Part IV. Relaxing the Rules 255 ■ 10. Parallelism, Concurrency, and Alternative Models 257 or, Getting Lots of Stuff Done at Once ■ 11. Probabilistic Algorithms 297 or, Getting It Done by Tossing Coins ■ 12. Cryptography and Reliable Interaction 317 or, Getting It Done in Secret Part V. The Bigger Picture 335 ■ 13. Software Engineering 337 or, Getting It Done When It’s Large ■ 14. Reactive Systems 357 or, Getting It to Behave Properly Over Time ■ 15. Algorithmics and Intelligence 379 or, Are They Better at It Than Us?