Foundations of Algorithms, Fifth Edition offers a well-balanced presentation of algorithm design, complexity analysis of algorithms, and computational complexity. Ideal for any computer science students with a background in college algebra and discrete structures, the text presents mathematical concepts using standard English and simple notation to maximize accessibility and user-friendliness. Concrete examples, appendices reviewing essential mathematical concepts, and a student-focused approach reinforce theoretical explanations and promote learning and retention. C++ and Java pseudocode help students better understand complex algorithms.

A chapter on numerical algorithms includes a review of basic number theory, Euclid's Algorithm for finding the greatest common divisor, a review of modular arithmetic, an algorithm for solving modular linear equations, an algorithm for computing modular powers, and the new polynomial-time algorithm for determining whether a number is prime. The revised and updated Fifth Edition features an all-new chapter on genetic algorithms and genetic programming, including approximate solutions to the traveling salesperson problem, an algorithm for an artificial ant that navigates along a trail of food, and an application to financial trading. With fully updated exercises and examples throughout and improved instructor resources including complete solutions, an Instructor’s Manual and PowerPoint lecture outlines, Foundations of Algorithms is an essential text for undergraduate and graduate courses in the design and analysis of algorithms.

Key features include:

• The only text of its kind with a chapter on genetic algorithms

• Use of C++ and Java pseudocode to help students better understand complex algorithms

• No calculus background required

• Numerous clear and student-friendly examples throughout the text

• Fully updated exercises and examples throughout

• Improved instructor resources, including complete solutions, an Instructor’s Manual, and PowerPoint lecture outlines

Table of Contents

1 Algorithms: Efficiency, Analysis, and Order

2 Divide-and-Conquer

3 Dynamic Programming

4 The Greedy Approach

5 Backtracking

6 Branch-and-Bound

7 Introduction to Computational Complexity: The Sorting Problem

8 More Computational Complexity: The Searching Problem

9 Computational Complexity and Intractability: An Introduction to the Theory of NP

10 Genetic Algorithms and Genetic Programming

11 Number-Theoretic Algorithms

12 Introduction to Parallel Algorithms

Appendix A Review of Necessary Mathematics

Appendix B Solving Recurrence Equations: With Applications to Analysis of Recursive Algorithms

About the Author

Richard E. Neapolitan is a mathematician and computer scientist. When he received his Ph.D. in mathematics from the Illinois Institute of Technology in the 1970s, there was a recession in the United States and a glut of mathematicians. So, he worked as a male model and in various computer related positions. The latter experience enabled him to obtain a computer science faculty position at Northeastern Illinois University in 1980, at which time he embarked on his career as a computer science professor and researcher.

Dr. Neapolitan is most well-known for his role in establishing the field of Bayesian networks. In the 1980s, researchers met at the newly formed Workshop on Uncertainty in Artificial Intelligence (now a conference) to discuss how to best perform uncertain inference in artificial intelligence. Dr. Neapolitan's seminal text Probabilistic Reasoning in Expert Systems integrated many of the results of these discussions into the field we now call Bayesian networks. Bayesian networks have arguably become the standard for handling uncertain inference in AI, and many AI applications have been developed using them.

Since 1990, Richard has conducted further theoretical research in philosophy of science, probability and statistics, decision analysis, and cognitive science; and he has applied probabilistic modeling to fields such as medicine, biology, psychology, and finance. Dr. Neapolitan has earned an international reputation both as a theoretician and a practitioner. Other books he has written include Learning Bayesian Networks (2004); Foundations of Algorithms (1996, 1998, 2003, 2010, 2014), which has been translated into three languages; Probabilistic Methods for Financial and Marketing Informatics (2007); Probabilistic Methods for Bioinformatics (2009); and Artificial Intelligence: With an Introduction to Machine Learning (2018). His approach to textbook writing is distinct in that he introduces a concept or methodology with simple examples, and then provides the theoretical underpinning. As a result, his books have the reputation for making difficult material easy to understand without sacrificing scientific rigor.