# Preface This third edition of *Foundations of Algorithms Using C++ Pseudocode* retains the features that made the second edition successful. As in the second edition, we still use pseudocode and not actual C++ code. The presentation of complex algorithms using all the details of any programming language would only cloud the students' understanding of the algorithms. Furthermore, the pseudocode should be understandable to someone versed in any high-level language, which means it should avoid details specific to any one language as much as possible. Significant deviations from C++ are discussed on pages 5–7 of the text. This text is about designing algorithms, complexity analysis of algorithms, and computational complexity (analysis of problems). It does not cover other types of analyses, such as analysis of correctness. Our motivation for writing this book was our inability to find a text that rigorously discusses complexity analysis of algorithms, yet is accessible to computer science students at mainstream universities such as Northeastern Illinois University. The majority of Northeastern's students have not studied calculus, which means that they are not comfortable with abstract mathematics and mathematical notation. The existing texts that we know of use notation that is fine for a mathematically sophisticated student, but is a bit terse for our student body. To make our text more accessible, we do the following: - assume that the student's mathematics background includes only college algebra and discrete structures; - use more English description than is ordinarily used to explain mathematical concepts; - give more detail in formal proofs than is usually done; - provide many examples. Additionally, improvements to the this edition include the following: - A section on data compression using Huffman code has been added to the chapter on greedy algorithms. - A chapter on numerical algorithms has been added. The chapter includes a review of basic number theory, Euclid's Algorithm for finding the greatest common divisor, a review of modular arthmetic, 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. - A discussion of cryptography, one of the most important topics in recent years. In particular, the volume includes coverage of the RSA public-key cryptosystem Because the vast majority of complexity analysis requires only a knowledge of finite mathematics, in most of our discussions we are able to assume only a background in college algebra and discrete structures. That is, for the most part, we do not find it necessary to rely on any concepts learned only in a calculus course. Often students without a calculus background are not yet comfortable with mathematical notation. Therefore, wherever possible, we introduce mathematical concepts (such as "big *O*") using more English description and less notation than is ordinarily used. It is no mean task finding the right mix of these two; a certain amount of notation is necessary to make a presentation lucid, whereas too much vexes many students. Judging from students' responses, we have found a good mix. This is not to say that we cheat on mathematical rigor. We provide formal proofs for all our results. However, we give more detail in the presentation of these proofs than is usually done, and we provide a great number of examples. By seeing concrete cases, students can often more easily grasp a theoretical concept. Therefore, if students who do not have strong mathematical backgrounds are willing to put forth sufficient effort, they should be able to follow the mathematical arguments and thereby gain a deeper grasp of the subject matter. Furthermore, we do include material that requires knowledge of calculus (such as the use of limits to determine order and proofs of some theorems). However, students do not need to master this material to understand the rest of the text. Material that requires calculus is marked with a  symbol in the table of contents and in the margin of the text; material that is inherently more difficult than most of the text but that requires no extra mathematical background is marked with a  symbol. ## Prerequisites As mentioned previously, we assume that the student's background in mathematics includes only college algebra and finite mathematics. The actual mathematics that is required is reviewed in [Appendix A](LiB0093.html#1281). For computer science background, we assume that the student has taken a data structures course. Therefore, material that typically appears in a data structures text is not presented here.