PREFACE ookbe thoughvvof th niques used in the mathematical analysis of algorithms.The material covered draws from classical mathematical topics,including discrete mathe- matics,elementary real analysis,and combinatorics,as well as from classical computer science topics,including algorithms and data structures.The focus ison“average-case”or“probabilistic”"analysis,though the basic mathematical tools required for“worst-case”or“complexity”analysis are covered as well.. We assume that the reader has some familiarity with basic concepts in both computer science and real analysis.In a nutshell,the reader should be able to both write programs and prove theorems.Otherwise,the book is intended to be self-contained. The book is meant to be used as a textbook in an upper-level course on analysis of algorithms.It can also be used in a course in discrete mathematics for computer scientists,since it covers basic techniques in discrete mathemat- ics as well as combinatorics and basic properties of important discrete struc- tures within a familiar context for computer science students.It is traditional to have somewhat broader coverage in such courses,but many instructors may find the approach here to be a useful way to engage students in a substantial portion of the material.The book also can be used to introduce students in mathematics and applied mathematics to principles from computer science related to algorithms and data structures. Despite the large amount of literature on the mathematical analysis of algorithms,basic information on methods and models in widespread use has not been directly accessible to students and researchers in the field.This book aims to address this situation,bringing together a body of material intended to provide readers with both an appreciation for the challenges of the field and the background needed to learn the advanced tools being developed to meet these challenges.Supplemented by papers from the literature,the book can serve as the basis for an introductory graduate course on the analysis of algo- rithms,or as a reference or basis for self-study by researchers in mathematics or computer science who want access to the literature in this field. Preparation.Mathematical maturity equivalent to one or two years'study at the college level is assumed.Basic courses in combinatorics and discrete mathematics may provide useful background(and may overlap with some www.it-ebooks.infoP R E F A C E T HIS book is intended to be a thorough overview of the primary tech￾niques used in the mathematical analysis of algorithms. Ļe material covered draws from classical mathematical topics, including discrete mathe￾matics, elementary real analysis, and combinatorics, as well as from classical computer science topics, including algorithms and data structures. Ļe focus is on “average-case” or “probabilistic” analysis, though the basic mathematical tools required for “worst-case” or “complexity” analysis are covered as well. We assume that the reader has some familiarity with basic concepts in both computer science and real analysis. In a nutshell, the reader should be able to both write programs and prove theorems. Otherwise, the book is intended to be self-contained. Ļe book is meant to be used as a textbook in an upper-level course on analysis of algorithms. It can also be used in a course in discrete mathematics for computer scientists, since it covers basic techniques in discrete mathemat￾ics as well as combinatorics and basic properties of important discrete struc￾tures within a familiar context for computer science students. It is traditional to have somewhat broader coverage in such courses, but many instructors may ŀnd the approach here to be a useful way to engage students in a substantial portion of the material. Ļe book also can be used to introduce students in mathematics and applied mathematics to principles from computer science related to algorithms and data structures. Despite the large amount of literature on the mathematical analysis of algorithms, basic information on methods and models in widespread use has not been directly accessible to students and researchers in the ŀeld. Ļis book aims to address this situation, bringing together a body of material intended to provide readers with both an appreciation for the challenges of the ŀeld and the background needed to learn the advanced tools being developed to meet these challenges. Supplemented by papers from the literature, the book can serve as the basis for an introductory graduate course on the analysis of algo￾rithms, or as a reference or basis for self-study by researchers in mathematics or computer science who want access to the literature in this ŀeld. Preparation. Mathematical maturity equivalent to one or two years’ study at the college level is assumed. Basic courses in combinatorics and discrete mathematics may provide useful background (and may overlap with some www.it-ebooks.info