Home Tags Python Tricks

Python Algorithms – Mastering Basic Algorithms in the Python Language :: The book is structured as follows:

Chapter 1: Introduction. You’ve already gotten through most of this. It gives an overview of the book.

Chapter 2: The Basics. This covers the essential concepts and terminology, also as some fundamental math. Among other things, you find out how to be sloppier together with your formulas than ever before, and still get the proper results, using asymptotic notation.

Chapter 3: Counting 101. More math—but it’s really fun math, I promise! There’s some basic combinatorics for analyzing the time period of algorithms, also as a mild introduction to recursion and recurrence relations.

Chapter 4: Induction and Recursion … and Reduction. The three terms within the title are crucial, and that they are closely related. Here we work with induction and recursion, which are virtually mirror images of every other, both for designing new algorithms and for proving correctness. We’ll also take a somewhat briefer look at the idea of reduction, which runs as a standard thread through most algorithmic work.

Chapter 5: Traversal: A Skeleton Key to Algorithmics. Traversal are often understood using the ideas of induction and recursion, but it’s in some ways a more concrete and specific technique. Several of the algorithms in this book are simply augmented traversals, so mastering this concept will offer you a true jump start.

Chapter 6: Divide, Combine, and Conquer. When problems can be decomposed into independent subproblems, you can recursively solve these subproblems and typically get efficient, correct algorithms as a result. This principle has several applications, not all of which are entirely obvious, and it’s a mental tool well worth acquiring.

Chapter 7: Greed is Good? Prove It! Greedy algorithms are usually easy to construct. Not only are they easy to construct, but they’re usually very efficient. The problem is, it are often hard to point out that they’re correct (and often they aren’t). This chapter deals with some well-known examples and a few more general methods for
constructing correctness proofs.

Chapter 8: Tangled Dependencies and Memoization. This chapter is about the planning method (or, historically, the problem) called, somewhat confusingly, dynamic programming. It is a complicated technique which will be hard to master but that also yields a number of the foremost enduring insights and stylish solutions within the field.

Chapter 9: From A to B with Edsger and Friends. Rather than the planning methods of the previous three chapters, the focus is now on a selected problem, with a number of applications: finding shortest paths in networks, or graphs. There are many variations of the matter , with corresponding (beautiful) algorithms.

Chapter 10: Matchings, Cuts, and Flows. How does one match, say, students with colleges so you maximize total satisfaction? In a web community, how does one know whom to trust? And how does one find the entire capacity of a road network? These, and a number of other other problems, are often solved with a little class of closely related algorithms and are all variations of the utmost flow problem, which is roofed during this chapter.

Writer of Python Algorithms – Mastering Basic Algorithms in the Python Language is Magnus Lie Hetland.