Data Science Texts

Discover what you don't know, and attack your weaknesses!

Elementary Algorithms

Strongly Recommended Prerequisites

Recommended Prerequisites

An algorithm is a well-defined procedure for accomplishing a well-defined task. Since computers require well-defined procedures to accomplish tasks, the study of algorithms is an essential component of both computer science and data science. The study of algorithms chiefly concerns proving that a particular algorithm will accomplish a particular task and determining the resources the algorithm will require to do so. Elementary algorithm texts describe the basic techniques used for these two goals, and they also catalog a number of algorithms that are useful in common situations. Since algorithms must often exploit and manipulate data, elementary algorithm textbooks also describe many efficient options for structuring data. Data scientists are often tasked with problems that require large amounts of computational resources, so it is important that they understand the tradeoffs of different algorithms.

Visualization of the "quicksort" Sorting Algorithm

Sorting is a commonly performed task when working with data, so a great deal of thought has gone into making it as fast as possible. The "quicksort" algorithm is a relatively fast algorithm for the average task. Sorting is also a useful didactic device, because it can be used to illustrate many fundamental principles of computer science, such as time complexity, divide and conquer strategies, data structures, etc.

Recommended Books

  1. Introduction to Algorithms

    Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein

    (Image takes you to Amazon.)

    Key Features

    Key Topics

    • Amortized Analysis
    • Approximation Algorithms
    • Asymptotic Analysis
    • Computational Geometry Algorithms
    • Data Structures
    • Divide and Conquer Strategies
    • Dynamic Programming
    • Fast Fourier Transform
    • Graphs and Trees
    • Greedy Algorithms
    • Linear Programming
    • Matrix Operations
    • Multithreaded Algorithms
    • NP-Completeness
    • Number-Theoretic Algorithms
    • Probabilistic Analysis
    • Randomized Algorithms
    • Recursion
    • Sorting and Searching
    • String Matching

    Description

    CLRS is the canonical elementary algorithms textbook. This partly because it is an excellent algorithms text, and partly because so many people use it that otherwise obscure examples in it have become canonical. CLRS will teach you how to prove an algorithm is correct, show you how the resources the algorithm requires will change as the problem size grows, introduces the standard data structures, and contains many well-known algorithms as examples. It also offers a lot of information about randomized algorithms and their analysis. CLRS does have a few potential drawbacks. Some of the exercises are quite difficult for the level of the text, and reliable solutions to the difficult ones are hard to find if you get stuck. Additionally, all the algorithms in the textbook are written in pseudocode, so you're responsible for your own implementation in a real programming language if you wish to experiment. Overall though, this an outstanding book for both learning and reference.

  2. The Algorithm Design Manual

    Steven S. Skiena

    (Image takes you to Amazon.)

    Key Features

    • In-text exercises
    • C++ algorithm implementations
    • Errata

    Key Topics

    • Approximation Algorithms
    • Asymptotic Analysis
    • Combinatorial Algorithms
    • Computational Geometry Algorithms
    • Data Structures
    • Divide and Conquer Strategies
    • Dynamic Programming
    • Graphs and Trees
    • Greedy Algorithms
    • Numerical Algorithms
    • Recursion
    • Sorting and Searching
    • String Algorithms

    Description

    The Algorithm Design Manual is somewhat less well-known than CLRS, but it has a lot going for it as an algorithms text. It is relatively inexpensive, offers a lot of algorithms that are absent in other books, and provides C++ implementations for many of the algorithms. We consider The Algorithm Design Manual a great companion to CLRS, but it can stand alone as an algorithms text, especially for a first pass. CLRS offers more analytic tools, and does a better job with randomized algorithms, but any user of algorithms would benefit from reading this book.