Programming Algorithms

Programming Algorithms

Vsevolod Domkin
Buy on Leanpub

Table of Contents

1 Introduction›

  • 1 Introduction
    • Why Algorithms Matter
    • A Few Words about Lisp
  • 2 Algorithmic Complexity
  • 3 A Crash Course in Lisp
    • The Core of Lisp
    • A Code Example
    • The REPL
    • Basic Expressions
    • Sequential Execution
    • Branching
    • Looping
    • Procedures and Variables
    • Comments
    • Getting Started

Essential Data Structures›

  • 4 Data Structures
    • Data Structures vs Algorithms
    • The Data Structure Concept
    • Contiguous and Linked Data Structures
    • Tuples
    • Passing Data Structures in Function Calls
    • Structs in Action: Union-Find
    • Take-Aways
  • 5 Arrays
    • Arrays as Sequences
    • Dynamic Vectors
    • Why Are Arrays Indexed from 0
    • Multi-Dimensional Arrays
    • Binary Search
    • Binary Search in Action: a Fast Specialized In-Memory DB
    • Sorting
    • O(n^2) Sorting
    • Quicksort
    • Production Sort
    • Performance Benchmark
    • Take-Aways
  • 6 Linked Lists
    • Lists as Sequences
    • Lists as Functional Data Structures
    • Different Kinds of Lists
    • FIFO & LIFO
    • Queue
    • Stack
    • Deque
    • Stacks in Action: SAX Parsing
    • Lists as Sets
    • Merge Sort
    • Parallelization of Merge Sort
    • Lists and Lisp
    • Take-Aways
    • Concrete Key-values
    • Simple Arrays
    • Associative Lists
    • Hash-Tables
    • Structs
    • Trees
    • Operations
    • Memoization
    • Memoization in Action: Transposition Tables
    • Cache Invalidation
    • Second Chance and Clock Algorithms
    • LFU
    • LRU
    • Low-Level Caching
    • Take-Aways

Derivative Data Structures›

  • 7 Hash-Tables
    • Implementation
    • Dealing with Collisions
    • Hash-Code
    • Advanced Hashing Techniques
    • Hash-Functions
    • Operations
    • Initialization
    • Access
    • Iteration
    • Perfect Hashing
    • Implementation
    • The CHM92 Algorithm
    • Distributed Hash-Tables
    • Hashing in Action: Content Addressing
    • Take-Aways
  • 8 Trees
    • Implementation Variants
    • Tree Traversal
    • Binary Search Trees
    • Splay Trees
    • Complexity Analysis
    • Red-Black and AVL Trees
    • B-Trees
    • Heaps
    • Tries
    • Trees in Action: Efficient Mapping
    • Take-Aways
  • 9 Graphs
    • Graph Representations
    • Topological Sort
    • MST
    • Prim’s Algorithm
    • Kruskal’s Algorithm
    • Pathfinding
    • Dijkstra’s Algorithm
    • A* Algorithm
    • Maximum Flow
    • Graphs in Action: PageRank
    • Implementation
    • Take-Aways
  • 10 Strings
    • Basic String-Related Optimizations
    • Strings in the Editor
    • Substring Search
    • Knuth-Morris-Pratt (KMP)
    • Boyer-Moore (BM)
    • Rabin-Karp (RK)
    • Aho-Corasick (AC)
    • Regular Expressions
    • Implementation of the Thompson’s Construction
    • Grammars
    • String Search in Action: Plagiarism Detection
    • Take-aways

Selected Algorithms›

  • 11 Dynamic Programming
    • Fibonacci Numbers
    • String Segmentation
    • Text Justification
    • Pathfinding Revisited
    • LCS and Diff
    • DP in Action: Backprop
    • Take-aways
  • 12 Approximation
    • Combinatorial Optimization
    • Local Search
    • Evolutionary Algorithms
    • Branch & Bound
    • Gradient Descent
    • Improving GD
    • Sampling
    • Matrix Factorization
    • Singular Value Decomposition
    • Fourier Transform
    • Fourier Transform in Action: JPEG
    • Take-Aways
  • 13 Compression
    • Encoding
    • Base64
    • Lossless Compression
    • Huffman Coding
    • Huffman Coding in Action: Dictionary Optimization
    • Arithmetic Coding
    • DEFLATE
    • Take-Aways
  • 14 Synchronization
    • Synchronization Troubles
    • Low-Level Synchronization
    • Mutual Exclusion Algorithms
    • High-Level Synchronization
    • Lock-Free Data Structures
    • Data-Parallelism and Message Passing
    • STM
    • Distributed Computations
    • Distributed Algorithms
    • Distributed Data Structures
    • Distributed Algorithms in Action: Collaborative Editing
    • Persistent Data Structures
    • Take-Aways
  • Afterword
    • Acknowledgments

Notes›

    Programming Algorithms/overview

    Programming Algorithms

    course_overview

    A comprehensive guide to writing efficient programs with examples in Lisp

    count_parts
    ·
    count_chapters
    begin_reading
    download
    part_count

    1 Introduction3 chapters

    Begin part ›
    1. 1 Introduction

    2. 2 Algorithmic Complexity

    3. 3 A Crash Course in Lisp

    part_count

    Essential Data Structures3 chapters

    Begin part ›
    1. 4 Data Structures

    2. 5 Arrays

    3. 6 Linked Lists

    part_count

    Derivative Data Structures4 chapters

    Begin part ›
    1. 7 Hash-Tables

    2. 8 Trees

    3. 9 Graphs

    4. 10 Strings

    part_count

    Selected Algorithms5 chapters

    Begin part ›
    1. 11 Dynamic Programming

    2. 12 Approximation

    3. 13 Compression

    4. 14 Synchronization

    5. Afterword

    part_count

    Notes0 chapters

    Begin part ›