viⅷi Contents l2.4.3 Inheritance… 419 12.5 Chapter Summary… …421 12.6 Exercises 422 Chapter 13 Algorithm Design and Recursion 425 13.1 Searching… 426 13.1.1 A Simple Searching Problem 426 13.1.2 Strategy 1:Linear Search 427 13.1.3 Strategy 2:Binary Search 428 13.1.4 Comparing Algorithms........ 429 13.2 Recursive Problem-Solving........... 431 13.2.1 Recursive Definitions .. 432 13.2.2 Recursive Functions........ 434 13.2.3 Example:String Reversal 435 13.2.4 Example:Anagrams… 437 13.2.5 Example:Fast Exponentiation.. 438 13.2.6 Example:Binary Search 439 13.2.7 Recursion vs.Iteration............ 440 13.3 S0 rting Alg0 rithms444…… 443 13.3.1 Naive Sorting:Selection Sort.......... 443 13.3.2 Divide and Conquer:Merge Sort...... 445 13.3.3 Comparing Sorts. 447 13.4 Hard Problems................ 450 13.4.1 Towers of Hanoi 450 13.4.2 The Halting Problem… 455 13.4.3 Conclusion... 459 13.5 Chapter Summary… 459 13.6 Exercises 460 Appendix A Python Quick Reference 469 Appendix B Using Python and IDLE 479 Appendix C Glossary 491 Index 503VIM Contents 12.4.3 Inheritance 419 12.5 Chapter Summary 421 12.6 Exercises 422 Chapter 13 Algorithm Design and Recursion 425 13.1 Searching 426 13.1.1 A Simple Searching Problem 426 13.1.2 Strategy 1: Linear Search 427 13.1.3 Strategy 2: Binary Search 428 13.1.4 Comparing Algorithms 429 13.2 Recursive Problem-Solving 431 13.2.1 Recursive Definitions 432 13.2.2 Recursive Functions 434 13.2.3 Example: String Reversal 435 13.2.4 Example: Anagrams 437 13.2.5 Example: Fast Exponentiation 438 13.2.6 Example: Binary Search 439 13.2.7 Recursion vs. Iteration 440 13.3 Sorting Algorithms 443 13.3.1 Naive Sorting: Selection Sort 443 13.3.2 Divide and Conquer: Merge Sort 445 13.3.3 Comparing Sorts 447 13.4 Hard Problems 450 13.4.1 Towers of Hanoi 450 13.4.2 The Halting Problem 455 13.4.3 Conclusion 459 13.5 Chapter Summary 459 13.6 Exercises 460 Appendix A Python Quick Reference 469 Appendix B Using Python and IDLE 479 Appendix C Glossary 491 Index 503