Understand algorithms and their design with this revised student-friendly textbook. Unlike other algorithms books, this one is approachable, the methods it explains are straightforward, and the insights it provides are numerous and valuable. Without grinding through lots of formal proof, students will benefit from step-by-step methods for developing algorithms, expert guidance on common pitfalls, and an appreciation of the bigger picture. Revised and updated, this second edition includes a new chapter on machine learning algorithms, and concise key concept summaries at the end of each part for quick reference. Also new to this edition are more than 150 new exercises: selected solutions are included to let students check their progress, while a full solutions manual is available online for instructors. No other text explains complex topics such as loop invariants as clearly, helping students to think abstractly and preparing them for creating their own innovative ways to solve problems.
Understand algorithms and their design with this revised student-friendly textbook. Unlike other algorithms books, this one is approachable, the methods it explains are straightforward, and the insights it provides are numerous and valuable. Without grinding through lots of formal proof, students will benefit from step-by-step methods for developing algorithms, expert guidance on common pitfalls, and an appreciation of the bigger picture. Revised and updated, this second edition includes a new chapter on machine learning algorithms, and concise key concept summaries at the end of each part for quick reference. Also new to this edition are more than 150 new exercises: selected solutions are included to let students check their progress, while a full solutions manual is available online for instructors. No other text explains complex topics such as loop invariants as clearly, helping students to think abstractly and preparing them for creating their own innovative ways to solve problems.
Über den Autor
Jeff Edmonds is Professor in the Department of Electrical Engineering and Computer Science at York University, Canada.
Inhaltsverzeichnis
Preface; Introduction; Part I. Iterative Algorithms and Loop Invariants: 1. Iterative algorithms: measures of progress and loop invariants; 2. Examples using more-of-the-input loop invariant; 3. Abstract data types; 4. Narrowing the search space: binary search; 5. Iterative sorting algorithms; 6. Euclid's GCD algorithm; 7. The loop invariant for lower bounds; 8. Key concepts summary: loop invariants and iterative algorithms; 9. Additional exercises: Part I; 10. Partial solutions to additional exercises: Part I; Part II. Recursion: 11. Abstractions, techniques, and theory; 12. Some simple examples of recursive algorithms; 13. Recursion on trees; 14. Recursive images; 15. Parsing with context-free grammars; 16. Key concepts summary: recursion; 17. Additional exercises: Part II; 18. Partial solutions to additional exercises: Part II; Part III. Optimization Problems: 19. Definition of optimization problems; 20. Graph search algorithms; 21. Network flows and linear programming; 22. Greedy algorithms; 23. Recursive backtracking; 24. Dynamic programming algorithms; 25. Examples of dynamic programming; 26. Reductions and NP-completeness; 27. Randomized algorithms; 28. Key concepts summary: greedy algorithms and dynamic programmings; 29. Additional exercises: Part III; 30. Partial solutions to additional exercises: Part III; Part IV. Additional Topics: 31. Existential and universal quantifiers; 32. Time complexity; 33. Logarithms and exponentials; 34. Asymptotic growth; 35. Adding-made-easy approximations; 36. Recurrence relations; 37. A formal proof of correctness; 38. Additional exercises: Part IV; 39. Partial solutions to additional exercises: Part IV; Exercise Solutions; Conclusion; Index.
