Translation of the interactive textbook Problem Solving with Algorithms and Data Structures

  • Tutorial
imageHello, Habr!

We (@ali_aliev and avenat ) are pleased to bring to your attention a translation of the interactive textbook Problem Solving with Algorithms and Data Structures by Brad Miller and David Ranum from Luther College in Iowa, USA.

About what?

The textbook details, explains and analyzes the most commonly used data structures and algorithms. The presentation goes from simple (what is an algorithm, how to evaluate its performance) to complex (trees, graphs) with live examples and code. Python was chosen as the programming language, and for those who are new to it, the first chapter has a large section with its concentrated description.

Authors talk about data structures such as stacks, queues (including priority), decks, hash tables, lists, trees, and graphs. The last two are generally devoted to very small chapters. The presentation is not just descriptive: for each structure, a variant (and sometimes more than one) of its implementation in Python is proposed. The emphasis, of course, is on object-oriented programming: a class is created, methods are written for it, some of which the authors leave to readers for their own improvement. Then there are examples of using the considered structure and a description of the algorithms with its participation.

One of the chapters of the textbook is devoted to recursion, including its graphical representation (fractals). Several well-known recursive problems are analyzed, and in the end it is clearly demonstrated that this technique, despite its elegance, is by no means a “silver bullet”.

Classic algorithms for sorting and searching are not deprived of attention. And, of course, for each of them, performance and “pitfalls” are analyzed, as well as recommendations for use. The last chapters on trees and graphs provide a lot of material about their varieties and their associated algorithms. The presentation here becomes more concise, many points are simply described so that after reading the chapter the reader will implement them on his own.

For whom?

The textbook is intended primarily for high school students and students, as well as "floating" in the theory of practical programmers. There is a lot of code, and the closer to the last chapters, the less it is chewed. Therefore, you should be prepared for thoughtful reading of listings. However, the textbook is not in vain called "interactive." The text contains inserts with the so-called ActiveCode, which can be run directly on the page in order to “feel” the program live. Plus for more complex material there is CodeLens - a sort of debugger in which you can view the operation of the code line by line. Most sections have tests for self-testing, and at the end of each chapter are two blocks of tasks for independent work: in theory and in practice.

Technical details

The tutorial is implemented in sphinx using extensions that add interactivity to it (for example, an extension that allows Python source code to be executed in a browser). Like the original project, translation is open source. All sources of the book are posted on github . Therefore, if you find a typo, semantic or stylistic mistake, then join! You can also make a clone of the tutorial repository and read it locally. Assembly instructions can be found here .

And again links

Original: http://interactivepython.org/courselib/static/pythonds/index.html

Translation: http://aliev.me/runestone/

Github translation repository: https://github.com/aliev/runestone

Also popular now: