Read more
Informationen zum Autor Jeff Edmonds received his Ph.D. in 1992 at University of Toronto in theoretical computer science. His thesis proved that certain computation problems require a given amount of time and space. He did his postdoctorate work at the ICSI in Berkeley on secure multi-media data transmission and in 1995 became an Associate Professor in the Department of Computer Science at York University, Canada. He has taught their algorithms course thirteen times to date. He has worked extensively at IIT Mumbai, India, and University of California San Diego. He is well published in the top theoretical computer science journals in topics including complexity theory, scheduling, proof systems, probability theory, combinatorics, and, of course, algorithms. Klappentext Textbook that teaches students how to think about algorithms like an expert, without getting bogged down in formal proof. Zusammenfassung Gives insights! notations! and analogies to help students describe and think about algorithms like an expert! without grinding through lots of formal proof. Solutions to many problems are included to let students test their progress! while class-tested PowerPoint slides are on the web to help course instructors. Inhaltsverzeichnis Part I. Iterative Algorithms and Loop Invariants: 1. 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; Part II. Recursion: 8. Abstractions, techniques, and theory; 9. Some simple examples of recursive algorithms; 10. Recursion on trees; 11. Recursive images; 12. Parsing with context-free grammars; Part III. Optimization Problems: 13. Definition of optimization problems; 14. Graph search algorithms; 15. Network flows and linear programming; 16. Greedy algorithms; 17. Recursive backtracking; 18. Dynamic programming algorithms; 19. Examples of dynamic programming; 20. Reductions and NP-completeness; 21. Randomized algorithms; Part IV. Appendix: 22. Existential and universal quantifiers; 23. Time complexity; 24. Logarithms and exponentials; 25. Asymptotic growth; 26. Adding made easy approximations; 27. Recurrence relations; 28. A formal proof of correctness; Part V. Exercise Solutions....
