xxii Preface relevant to computer science students.The first leaves students complain- ing that they are being forced to take too much "irrelevant"'mathematics before they can take their first computer science course.The second leaves professors (who are often mathematicians)trying to explain fairly advanced computer science topics such as hashing,binary trees,and recursive pro- grams to students who may never have written a program.Even under the best of circumstances,this approach significantly reduces the depth of the mathematics that can be taught.Our analysis led to a different approach, creating a course that appears slightly later in students'studies.While we do not explicitly assume students have taken calculus,we assume familiar- ity with and make significant use of summation notation,logarithms,and exponential functions,so that a strong understanding of precalculus mate- rial is very helpful.?This course is meant to be taken after an introductory computer science course where students have seen recursive programs.Ide- ally it would be taken concurrently with or after a data structures course, but we explain the data structures that we use as examples.Therefore a data structures course is not a prerequisite for this course. We feel that there are several advantages to this placement.Particular examples include: Students have already had serious experience thinking about problem solving,algorithms,and writing code. Students have learned or are ready to learn several important computer science concepts such as hashing,recursion,sorting and searching,and basic data structures. Students know enough computer science that they already know the motivating examples or the examples are straightforward enough for them to understand.For example, Hashing can be used to motivate the study of probability Analysis of recursive programs such as mergesort and quicksort can be used to motivate recurrence relations and their solutions -Analyzing how often we expect to find a new minimum in a procedure that finds the minimum element of a list can be used to motivate studying linearity of expectation and harmonic numbers. 2Most of our students have had calculus.In isolated places we make use of elementary derivatives and in optional subsections in probability we use natural logarithm and exponential functions and elementary power series.By ignoring the few proofs or problems using derivatives and the optional subsections in probability,the instructor can avoid calculus.xxii Preface relevant to computer science students. The first leaves students complain￾ing that they are being forced to take too much “irrelevant” mathematics before they can take their first computer science course. The second leaves professors (who are often mathematicians) trying to explain fairly advanced computer science topics such as hashing, binary trees, and recursive pro￾grams to students who may never have written a program. Even under the best of circumstances, this approach significantly reduces the depth of the mathematics that can be taught. Our analysis led to a different approach, creating a course that appears slightly later in students’ studies. While we do not explicitly assume students have taken calculus, we assume familiar￾ity with and make significant use of summation notation, logarithms, and exponential functions, so that a strong understanding of precalculus mate￾rial is very helpful.2 This course is meant to be taken after an introductory computer science course where students have seen recursive programs. Ide￾ally it would be taken concurrently with or after a data structures course, but we explain the data structures that we use as examples. Therefore a data structures course is not a prerequisite for this course. We feel that there are several advantages to this placement. Particular examples include: • Students have already had serious experience thinking about problem solving, algorithms, and writing code. • Students have learned or are ready to learn several important computer science concepts such as hashing, recursion, sorting and searching, and basic data structures. • Students know enough computer science that they already know the motivating examples or the examples are straightforward enough for them to understand. For example, – Hashing can be used to motivate the study of probability. – Analysis of recursive programs such as mergesort and quicksort can be used to motivate recurrence relations and their solutions. – Analyzing how often we expect to find a new minimum in a procedure that finds the minimum element of a list can be used to motivate studying linearity of expectation and harmonic numbers. 2Most of our students have had calculus. In isolated places we make use of elementary derivatives and in optional subsections in probability we use natural logarithm and exponential functions and elementary power series. By ignoring the few proofs or problems using derivatives and the optional subsections in probability, the instructor can avoid calculus