Category: Algorithms

Data Structures and Algorithms with Object-Oriented Design Patterns in Ruby

Author Bruno R. Preiss
Format online HTML
Price free

Create sound software designs with data structures that use modern object-oriented design patterns!

Author Bruno Preiss presents the fundamentals of data structures and algorithms from a modern, object-oriented perspective.

The text promotes object-oriented design using Ruby and illustrates the use of the latest object-oriented design patterns. Virtually all the data structures are discussed in the context of a single class hierarchy.

This framework clearly shows the relationships between data structures and illustrates how polymorphism and inheritance can be used effectively.

Continue reading

Clever Algorithms: Nature-Inspired Programming Recipes

Author Jason Brownlee PhD
Format online HTML
Price free

The book describes 45 algorithms from the field of Artificial Intelligence. All algorithm descriptions are complete and consistent to ensure that they are accessible, usable and understandable by a wide audience.

This book provides a handbook of algorithmic recipes from the fields of Metaheuristics, Biologically Inspired Computation and Computational Intelligence that have been described in a complete, consistent, and centralized manner. These standardized descriptions were carefully designed to be accessible, usable, and understandable. Most of the algorithms described in this book were originally inspired by biological and natural systems, such as the adaptive capabilities of genetic evolution and the acquired immune system, and the foraging behaviors of birds, bees, ants and bacteria. An encyclopedic algorithm reference, this book is intended for research scientists, engineers, students, and interested amateurs. Each algorithm description provides a working code example in the Ruby Programming Language.

Continue reading

Global Optimization Algorithms: Theory and Application

My image
  • Author: Thomas Weise
  • Format: PDF
  • Price: free

This book is about global optimization algorithms, which are methods to find optimal solutions for given problems. It especially focuses on evolutionary computation by discussing evolutionary algorithms, genetic algorithms, genetic programming, learning classifier systems, evolution strategy, differential evolution, particle swarm optimization, and ant colony optimization.

The book also elaborates on other meta-heuristics, such as simulated annealing, hill climbing, tabu search, and random optimization.

According to the author, the book is an ongoing work in progress that has existed for over two years and has been updated and extended throughout that time. However, the book will never be finished since there is always something new to add.

Chapters include:

  • Evolutionary Algorithms
  • Genetic Algorithms
  • Genetic Programming
  • Evolution Strategy
  • Evolutionary Programming
  • Learning Classifier Systems
  • Hill Climbing
  • Random Optimization
  • Simulated Annealing
  • Tabu Search
  • Ant Colony Optimization
  • Particle Swarm Optimization
  • Memetic Algorithms
  • State Space Search
  • Parallelization and Distribution
  • Maintaining the Optimal Set
  • Benchmarks and Toy Problems
  • Contests
  • Real-World Applications
  • Research Applications
  • Sigoa – Implementation in Java
  • Set Theory
  • Stochastic Theory
  • Clustering
  • Theoretical Computer Science

Introduction to Probability: Second Revised Edition

My image
  • Author: Charles M. Grinstead & J. Laurie Snell
  • Format: PDF
  • Price: free

This is a textbook designed for an introductory probability course at the university level for sophomores, juniors, and seniors in mathematics, physical and social sciences, engineering, and computer science. It presents a thorough treatment of ideas and techniques necessary for a firm understanding of the subject.

The text is also recommended for use in discrete probability courses. The material is organized so that the discrete and continuous probability discussions are presented in a separate, but parallel, manner. This organization does not emphasize an overly rigorous or formal view of probabililty and therefore offers some strong pedagogical value. Hence, the discrete discussions can sometimes serve to motivate the more abstract continuous probability discussions.

Key ideas are developed in a somewhat leisurely style, providing a variety of interesting applications to probability and showing some nonintuitive ideas. Over 600 exercises provide the opportunity for practicing skills and developing a sound understanding of ideas. Numerous historical comments deal with the development of discrete probability. The text includes many computer programs that illustrate the algorithms or the methods of computation for important problems.

Chapters include:

  • Discrete probability distributions
  • Continuous probability densities
  • Combinatorics
  • Conditional probability
  • Important distributions and densities
  • Expected value and variance
  • Sums of independent random variables
  • Law of large numbers
  • Central limit theorem
  • Generating functions
  • Markov chains
  • Random walks

Dictionary of Algorithms and Data Structures

My image
  • Author: National Institute of Standards and Technology (NIST)
  • Format: online HTML
  • Price: free

This is a dictionary of algorithms, algorithmic techniques, data structures, archetypal problems, and related definitions, presented by the National Institute of Standards and Technology (NIST).Algorithms include common functions, such as Ackermann’s function. Problems include traveling salesman and Byzantine generals. Some entries have links to implementations and more information. Index pages list entries by area and by type.

It does not include algorithms particular to business data processing, communications, operating systems or distributed algorithms, programming languages, AI, graphics, or numerical analysis. They have a hard enough time keeping up with and covering “general” algorithms and data structures.

Information Theory, Inference, and Learning Algorithms

My image
  • Author: David J. C. MacKay
  • Format: PDF, Postscript, DJVU, latex
  • Price: free

Information theory and inference, often taught separately, are here united in one entertaining textbook. These topics lie at the heart of many exciting areas of contemporary science and engineering – communication, signal processing, data mining, machine learning, pattern recognition, computational neuroscience, bioinformatics, and cryptography.

This textbook introduces theory in tandem with applications. Information theory is taught alongside practical communication systems, such as arithmetic coding for data compression and sparse-graph codes for error-correction. A toolbox of inference techniques, including message-passing algorithms, Monte Carlo methods, and variational approximations, are developed alongside applications of these tools to clustering, convolutional codes, independent component analysis, and neural networks.

The final part of the book describes the state of the art in error-correcting codes, including low-density parity-check codes, turbo codes, and digital fountain codes — the twenty-first century standards for satellite communications, disk drives, and data broadcast.

Richly illustrated, filled with worked examples and over 400 exercises, some with detailed solutions, David MacKay’s groundbreaking book is ideal for self-learning and for undergraduate or graduate courses. Interludes on crosswords, evolution, and sex provide entertainment along the way.

In sum, this is a textbook on information, communication, and coding for a new generation of students, and an unparalleled entry point into these subjects for professionals in areas as diverse as computational biology, financial engineering, and machine learning.

Chapters include:

  • Introduction to Information Theory
  • Probability, Entropy, and Inference
  • More about Inference
  • Data Compression
  • The Source Coding Theorem
  • Symbol Codes
  • Stream Codes
  • Codes for Integers
  • Noisy-Channel Coding
  • Dependent Random Variables
  • Communication over a Noisy Channel
  • The Noisy-Channel Coding Theorem
  • Error-Correcting Codes and Real Channels
  • Further Topics in Information Theory
  • Hash Codes: Codes for Efficient Information Retrieval
  • Binary Codes
  • Very Good Linear Codes Exist
  • Further Exercises on Information Theory
  • Message Passing
  • Communication over Constrained Noiseless Channels
  • Crosswords and Codebreaking
  • Why have Sex? Information Acquisition and Evolution
  • Probabilities and Inference
  • An Example Inference Task: Clustering
  • Exact Inference by Complete Enumeration
  • Maximum Likelihood and Clustering
  • Useful Probability Distributions
  • Exact Marginalization
  • Exact Marginalization in Trellises
  • Exact Marginalization in Graphs
  • Laplace’s Method
  • Model Comparison and Occam’s Razor
  • Monte Carlo Methods
  • Efficient Monte Carlo Methods
  • Ising Models
  • Exact Monte Carlo Sampling
  • Variational Methods
  • Independent Component Analysis and Latent Variable Modelling
  • Random Inference Topics
  • Decision Theory
  • Bayesian Inference and Sampling Theory
  • Neural networks
  • Introduction to Neural Networks
  • The Single Neuron as a Classifier
  • Capacity of a Single Neuron
  • Learning as Inference
  • Hopfield Networks
  • Boltzmann Machines
  • Supervised Learning in Multilayer Networks
  • Gaussian Processes
  • Deconvolution
  • Sparse Graph Codes
  • Low-Density Parity-Check Codes
  • Convolutional Codes and Turbo Codes
  • Repeat-Accumulate Codes
  • Digital Fountain Codes

Algorithms and Complexity, First Edition

My image
  • Author: Herbert S. Wilf
  • Format: PDF
  • Price: free

This is an introductory textbook, suitable for classroom use, on the design and analysis of algorithms, complexity, methods for solving problems on computers and the costs (usually in running time) of using those methods.

The first edition was available in print from 1986 to 1994. The copyright has been returned to the author and he has made it available to the public, free of charge. He also allows reproduction of the book for educational purposes, but you can not distribute it from the internet in any form.

There is a second edition of this book available for purchase, with the only major difference being the inclusion of solutions to most of the exercises that are presented.

Chapters include:

  • Hard vs easy problems
  • Mathematical Preliminaries
  • Orders of magnitude
  • Positional number systems
  • Manipulations with series
  • Recurrence relations
  • Counting
  • Graphs
  • Quicksort
  • Recursive graph algorithms
  • Fast matrix multiplication
  • The discrete Fourier transform
  • Applications of the FFT
  • Algorithms for the network flow problem
  • The algorithm of Ford and Fulkerson
  • The max-flow min-cut theorem
  • The complexity of the Ford-Fulkerson algorithm
  • Layered networks
  • The MPM Algorithm
  • Applications of network flow
  • The greatest common divisor
  • The extended Euclidean algorithm
  • Primality testing
  • Interlude: the ring of integers modulo n
  • Pseudoprimality tests
  • Proof of goodness of the strong pseudoprimality test
  • Factoring and cryptography
  • Factoring large integers
  • Proving primality
  • Turing machines
  • Cook’s theorem
  • Some other NP-complete problems
  • Half a loaf
  • Backtracking (I): independent sets
  • Backtracking (II): graph coloring
  • Approximate algorithms for hard problems