Oreilly - Analysis of Algorithms

Oreilly - Analysis of Algorithms

by | Released December 2015 | ISBN: 0134432568

https://www.oreilly.com/library/view/analysis-of-algorithms/9780134432564/

12+ Hours of Video InstructionAnalysis of Algorithms Video Lectures cover the essential information that every serious programmer needs to know about analyzing algorithms, including analytic combinatorics. In these videos, basic coverage of recurrences, generating functions, and asymptotics leads to an introduction to analytic combinatorics, including labeled and unlabeled combinatorial classes. The videos go on to cover survey trees, permutations, strings and tries, and words and mappings, with applications drawn from the study of widely-used algorithms.DescriptionThis collection of video lectures provides an introductory exploration of how to mathematically analyze algorithms. Author Robert Sedgewick emphasizes the mathematics required to support scientific studies that can serve as the basis for predicting algorithms and for comparing different algorithms on the basis of performance. Every lecture is accompanied with suggested related readings that you can find in An Introduction to the Analysis of Algorithms, Second Edition. These lectures provide another perspective on the material presented in the book and are in one-to-one correspondence with the chapters in the textbook.You also can find related resources on the instructors' web site, including the following:Full Java implementationsTest dataExercises and answersLecture slidesOther links to related materialAbout the InstructorRobert Sedgewick is the William O. Baker Professor of Computer Science at Princeton University. He is a Director of Adobe Systems and has served on the research staffs at Xerox PARC, IDA, and INRIA. He earned his PhD from Stanford University under Donald E. Knuth. He is the coauthor (with Kevin Wayne) of Algorithms, Fourth Edition.Skill LevelAll LevelsWhat You Will Learn Historical context and motivation for the scientific study of algorithmic performance.An introduction to recurrence relations.How to use generating functions to solve recurrences. How to derive approximate answers via asymptotic analysis.How to simplify analysis via analytic combinatorics.How to analyze properties of permutations, trees, strings, tries, and mappings. Applications to the analysis of classic algorithms from computer science. Who Should Take This CourseDespite 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 that situation. It is intended for:Anyone interested in learning more about mathematical methods in the analysis of algorithms.Anyone interested in further study in the analysis of algorithms or analytic combinatorics, including study of Knuth's The Art of Computer Programming.Course RequirementsFirst-year calculus, though the more experience in mathematics, the better. First-year programming, though familiarity with Java and a second-year algorithms course is better preparation.Table of ContentsLecture 1: Analysis of Algorithms. We begin by considering historical context and motivation for the scientific study of algorithm performance. Then we consider a classic example that illustrates the key ingredients of the process: the analysis of Quicksort. The lecture concludes with a discussion of some resources that you might find useful during this course.Lecture 2: Recurrences. We begin the course with an overview of recurrence relations, which provide us with a direct mathematical model for the analysis of algorithms. We finish by examining the fascinating oscillatory behavior of the divide-and-conquer recurrence corresponding to the mergesort algorithm and the general "master theorem" for related recurrences.Lecture 3: Generating Functions. Since the 17th century, scientists have been using generating functions to solve recurrences, so we continue with an overview of generating functions, emphasizing their utility in solving problems like counting the number of binary trees with N nodes.Lecture 4: Asymptotics. Exact answers are often cumbersome, so we next consider a scientific approach to developing approximate answers that, again, mathematicians and scientists have used for centuries.Lecture 5: Analytic Combinatorics. With a basic knowledge of recurrences, generating functions, and asymptotics, you are ready to learn and appreciate the basic features of analytic combinatorics, a systematic approach that avoids much of the detail of the classical methods that we have been considering. We introduce unlabelled and labelled combinatorial classes and motivate our basic approach to studying them, with numerous examples.Lecture 6: Trees. The quintessential recursive structure, trees of various sorts are ubiquitous in scientific enquiry, and they arise explicitly in countless computing applications. You can find broad coverage in the textbook, but the lecture focuses on the use of analytic combinatorics to enumerate various types of trees and study parameters.Lecture 7: Permutations. The study of sorting algorithms is the study of properties of permutations. We introduce analytic-combinatoric approaches to studying permutations in the context of this relationship.Lecture 8: Strings and Tries. From DNA sequences to web indices, strings (sequences of characters) are ubiquitous in modern computing applications, so we use analytic combinatorics to study their basic properties and then introduce the trie, an essential and fundamental structure not found in classical combinatorics.Lecture 9: Words and Mappings. We view strings as sets of characters or as functions from [1..N] to [1..M] to study classical occupancy problems and their application to fundamental hashing algorithms. Functions from [1..N] to [1..N] are mappings, which have an interesting and intricate structure that we can study with analytic combinatorics. Show and hide more

Overview
- Brief History 00:09:33
- Analysis of Algorithms 00:16:21
- Context 00:12:44
- Analytic Combinatorics 00:29:16
Lecture 1: Analysis of Algorithms
- History and Motivation 00:11:03
- A Scientific Approach 00:16:38
- Example: Quicksort 00:30:39
- Resources 00:17:39
Lecture 2: Recurrences
- Computing Values 00:10:31
- Telescoping 00:15:18
- Types of Recurrences 00:12:51
- Mergesort 00:18:04
- Master Theorem 00:14:21
Lecture 3: Generating Functions
- Ordinary Generating Functions 00:16:26
- Solving Recurrences 00:18:55
- Catalan Numbers 00:14:04
- Exponential Generating Functions 00:07:24
- Counting with Generating Functions 00:27:32
Lecture 4: Asymptotics
- Standard Scale 00:18:52
- Manipulating Expansions 00:19:23
- Asymptotics of Finite Sums 00:16:43
- Bivariate Asymptotics 00:28:03
Lecture 5: Analytic Combinatorics
- The Symbolic Method 00:25:19
- Labelled Objects 00:29:56
- Coefficient Asymptotics 00:12:10
- Perspective 00:09:20
Lecture 6: Trees
- Trees and Forests 00:14:17
- Binary Search Trees 00:22:50
- Path Length 00:25:56
- Other Types of Trees 00:13:57
Lecture 7: Permutations
- Basics 00:17:23
- Sets of Cycles 00:20:38
- Left-Right-Minima 00:19:30
- Other Parameters 00:15:06
- BGFs and Distributions 00:19:15
Lecture 8: Strings and Tries
- Bitstrings with Restrictions 00:27:50
- Languages 00:12:15
- Tries 00:16:41
- Trie Parameters 00:18:38
Lecture 9: Words and Mappings
- Words 00:11:44
- Birthday Problem 00:06:30
- Coupon Collector Problem 00:13:45
- Hash Tables 00:13:44
- Mappings 00:23:24