Description
Taylor & Francis Ltd Methods In Algorithmic Analysis 2009 Edition by Vladimir A. Dobrushkin
Explores the Impact of the Analysis of Algorithms on Many Areas within and beyond Computer ScienceA flexible, interactive teaching format enhanced by a large selection of examples and exercisesDeveloped from the author's own graduate-level course, Methods in Algorithmic Analysis presents numerous theories, techniques, and methods used for analyzing algorithms. It exposes students to mathematical techniques and methods that are practical and relevant to theoretical aspects of computer science.After introducing basic mathematical and combinatorial methods, the text focuses on various aspects of probability, including finite sets, random variables, distributions, Bayes' theorem, and Chebyshev inequality. It explores the role of recurrences in computer science, numerical analysis, engineering, and discrete mathematics applications. The author then describes the powerful tool of generating functions, which is demonstrated in enumeration problems, such as probabilistic algorithms, compositions and partitions of integers, and shuffling. He also discusses the symbolic method, the principle of inclusion and exclusion, and its applications. The book goes on to show how strings can be manipulated and counted, how the finite state machine and Markov chains can help solve probabilistic and combinatorial problems, how to derive asymptotic results, and how convergence and singularities play leading roles in deducing asymptotic information from generating functions. The final chapter presents the definitions and properties of the mathematical infrastructure needed to accommodate generating functions.Accompanied by more than 1,000 examples and exercises, this comprehensive, classroom-tested text develops students' understanding of the mathematical methodology behind the analysis of algorithms. It emphasizes the important relation between continuous (classical) mathematics and discrete mathematics, which is the basis of computer science. PRELIMINARIESWhy Do We Analyze Algorithms? Proofs Iteration and RecursionCOMBINATORICSProperties of SummationMultiple SumsPrinciples of CountingPermutations and CombinationsBinomial CoefficientsBinomial Coefficient and Hypergeometric FunctionsStirling ApproximationPROBABILITYSet OperationsSample Space and Random VariablesCalculating ProbabilitiesRandom VariablesConditional ProbabilitiesIndependenceJoint DistributionsDependent Random VariablesMORE ABOUT PROBABILITYSpecial DistributionsTypes of Probabilistic ConvergenceThe Theorem of Total ProbabilityBayes' TheoremConvolutionOrder StatisticsChebyshev InequalitySundry ExamplesRECURRENCES OR DIFFERENCE EQUATIONSHow Do Difference Equations Arise?Properties of Difference EquationsFirst Order Linear Difference EquationsDivide-and-Conquer RecurrencesQuicksort RecurrenceRecurrences in Numerical AnalysisContinued FractionsPartial Difference EquationsSome ApplicationsINTRODUCTION TO GENERATING FUNCTIONSGenerating Functions-DefinitionsExtraction of CoefficientsCounting Binary TreesSolving RecurrencesSnake Oil SummationApplications in ProbabilityThe Langrage Inversion TheoremENUMERATION WITH GENERATING FUNCTIONSDefinition of EnumeratorsSum and Product RulesCounting Compositions of IntegersFurther Set OperationsPartition of IntegersExponential EnumeratorsFURTHER ENUMERATION METHODSEnumeration of TreesOccupancy EnumerationThe Principle of Inclusion and Exclusion (PIE)Extensions and Further Applications of the PIEProbabilistic Inclusion-Exclusion Principle Runs in PermutationsSpecial TopicsCOMBINATORICS OF STRINGSOperations on LanguagesRegular LanguagesCounting Regular LanguagesWaiting Time Probabilistic Problems Algorithms and Markov ChainsINTRODUCTION TO ASYMPTOTICSAsymptotic Notation and ApplicationsThe Critical Range Method Rice's MethodThe Euler Summation FormulaFinding PrimesAsymptotics from RecurrencesLimit Laws in ProbabilityASYMPTOTICS AND GENERATING FUNCTIONSElementary Bounds from Generating FunctionsEstimates from SingularitiesEstimates from Entire FunctionsExamples and ExercisesREVIEW OF ANALYTIC TECHNIQUESComplex NumbersReview of Power SeriesFunctions of a Complex Variable: Basic ConceptsDifferential OperatorsPartial Fraction DecompositionSome Special Functions Stieltjes IntegralsAPPENDICESBIBLIOGRAPHYANSWERS/HINTS TO SELECTED PROBLEMS INDEX