Sorting and Searching Algorithms: A Cookbook

By Thomas Niemann

This is a collection of algorithms for sorting and searching. Descriptions are brief and intuitive, with just enough theory thrown in to make you nervous. I assume you know C, and that you are familiar with concepts such as arrays and pointers.
The first section introduces basic data structures and notation. The next section presents several sorting algorithms. This is followed by techniques for implementing dictionaries, structures that allow efficient search, insert, and delete operations. The last section illustrates algorithms that sort data and implement dictionaries for very large files. Source code for each algorithm, in ANSI C, is available at the site listed below.

Introduction
Arrays and linked lists are two basic data structures used to store information. We may wish to search, insert or delete records in a database based on a key value. This section examines the performance of these operations on arrays and linked lists...

Click to Read More/Download

Labels:

Problems on Algorithms

By William Gasarch and Ian Parberry
The ability to devise effective and efficient algorithms in new situations is a skill that separates the master programmer from the merely adequate coder. The best way to develop that skill is to solve problems. To be effective problem solvers, master-programmers-in-training must do more than memorize a collection of standard techniques and applications -- they must in addition be able to internalize and integrate what they have learned and apply it in new circumstances. This book is a collection of problems on the design, analysis, and verification of algorithms for use by practicing programmers who wish to hone and expand their skills, as a supplementary text for students enrolled in an undergraduate or beginning graduate class on algorithms, and as a self-study text for graduate students who are preparing for the qualifying (often called "breadth" or "comprehensive") examination on algorithms for a Ph.D. program in Computer Science or Computer Engineering. It is intended to augment the problem sets found in any standard algorithms textbook.
Recognizing that a supplementary text must be cost-effective if it is to be useful, the author made two important and perhaps controversial decisions in order to keep its length within reasonable bounds. The first is to cover only what it is considered to be the most important areas of algorithm design and analysis. Although most instructors throw in a "fun" advanced topic such as amortized analysis, computational geometry, approximation algorithms, number-theoretic algorithms, randomized algorithms, or parallel algorithms, it had been chosen not to cover these areas. The second decision is not to search for the origin of the problems used. A lengthy discussion of the provenance of each problem would help make this hook more scholarly, but would not make it more attractive for its intended audience -- students and practicing programmers.
Labels:

Graph-Theoretic Algorithms

By Therese Biedl
This document results from graduate courses that I taught at the University of Waterloo in Fall 1999, Winter 2002 and Winter 2004. Students were asked to take lecture notes in LATEX, which I then compiled and edited for this document.
The topic of graph algorithms is so unbelievably big that it is entirely hopeless to want to hold just one course about them. Even focusing on advanced graph algorithms (whatever "advanced" may mean) doesn't help, because there is still too many algorithms to cover.
The focus of this course was therefore even more specialized: I wanted to look at problems which are "normally" difficult (by which I mean a high polynomial running-time, or even NP-complete), but which can be solved faster when focusing on a specialized subclass. These notes assume that the reader is familiar with the following topics:
  • Data structures, in particular lists, stacks, queues, trees, bucket sorting, graph traversals.
  • Graph theory and combinatorial optimization, in particular graph definitions, shortest paths, °ows, matchings.
  • Analysis of algorithms, in particular the O-notation and NP-completeness.

For some of these topics, a brief review is given here (see the appendix), but for more details, the reader is referred to for example [CLRS00] for data structures and analysis of algorithms, and [Gib85] for graph theory and combinatorial optimization.

Click to Read More/Download

Labels:

Foundations of Computer

By Lawrence C Paulson

This course has two objectives. First (and obvious) is to teach programming. Second is to present some fundamental principles of computer science, especially algorithm design. Most students will have some programming experience already, but there are few people whose programming cannot be improved through greater knowledge of basic principles. Please bear this point in mind if you have extensive experience and find parts of the course rather slow.
The programming in this course is based on the language ML and mostly concerns the functional programming style. Functional programs tend to be shorter and easier to understand than their counterparts in conventional languages such as C. In the space of a few weeks, we shall be able to cover most of the forms of data structures seen in programming. The course also covers basic methods for estimating efficiency.
Courses in the Computer Laboratory are now expected to supply a Learning Guide to suggest extra reading, discussion topics, exercises and past exam questions. For this course, such material is attached at the end of each lecture. Extra reading is mostly drawn from my book ML for the Working Programmer (second edition), which also contains many exercises.

Contents
Introduction
Recursive Functions
O Notation: Estimating Costs in the Limit
Lists
More on Lists
Sorting
Datatypes and Trees
Dictionaries and Functional Arrays
Queues and Search Strategies
Functions as Values
List Functionals
Polynomial Arithmetic
Sequences, or Lazy Lists
Elements of Procedural Programming
Linked Data Structures

Click to Read More/Download

Labels:

Efficient Algorithms for Sorting and Synchronization

By Andrew Tridgell

This thesis presents efficient algorithms for internal and external parallel sorting and remote data update. The sorting algorithms approach the problem by concentrating first on highly efficient but incorrect algorithms followed by a cleanup phase that completes the sort. The remote data update algorithm, rsync, operates by exchanging block signature information followed by a simple hash search algorithm for block matching at arbitrary byte boundaries. The last chapter of the thesis examines a number of related algorithms for text compression, differencing and incremental backup.
Internal Parallel Sorting
My first introduction to the problem of parallel sorting came from a problem in the implementation of an automatic speech recognition training program. A set of speech data needed to be normalized in order to be used as the input to a recurrent neural network system and I decided that a quick-and-dirty way of doing this would be to sort the data, then sample it at regular intervals to generate a histogram.
Labels:

Data Structures and Algorithms with Object-Oriented Design Patterns in C++

By Bruno R. Preiss
This book was motivated by my experience in teaching the course E&CE 250: Algorithms and Data Structures in the Computer Engineering program at the University of Waterloo. I have observed that the advent of object-oriented methods and the emergence of object-oriented design patterns has lead to a profound change in the pedagogy of data structures and algorithms. The successful application of these techniques gives rise to a kind of cognitive unification: Ideas that are disparate and apparently unrelated seem to come together when the appropriate design patterns and abstractions are used.
This paradigm shift is both evolutionary and revolutionary. On the one hand, the knowledge base grows incrementally as programmers and researchers invent new algorithms and data structures. On the other hand, the proper use of object-oriented techniques requires a fundamental change in the way the programs are designed and implemented. Programmers who are well schooled in the procedural ways often find the leap to objects to be a difficult one.
Labels:

Data Structures and Algorithms with Object-Oriented Design Patterns in C#

By Bruno R. Preiss
Object-Oriented Design
Traditional approaches to the design of software have been either data oriented or process oriented. Data-oriented methodologies emphasize the representation of information and the relationships between the parts of the whole. The actions which operate on the data are of less significance. On the other hand, process-oriented design methodologies emphasize the actions performed by a software artifact; the data are of lesser importance.
It is now commonly held that object-oriented methodologies are more effective for managing the complexity which arises in the design of large and complex software artifacts than either data-oriented or process-oriented methodologies. This is because data and processes are given equal importance. Objects are used to combine data with the procedures that operate on that data. The main advantage of using objects is that they provide both abstraction and encapsulation.
Click to Read More
Labels:

Combinatorial Algorithms

By Jeff Erickson

This pdf book contains senior-level algorithms for computer engineering students. They are
  • Notes on solving recurrences
  • Introduction
  • Divide and conquer
  • Dynamic programming
  • Randomization: Nuts and bolts
  • Randomized treaps
  • Randomized mincut
  • Uniform and universal hashing
  • Skip lists
  • Amortized analysis
  • Scapegoat trees and splay trees
  • Union-find
  • Fibonacci heaps
  • Graph algorithms
  • Representing and searching graphs
  • Single-source shortest paths
  • All-pairs shortest paths
  • Minimum spanning trees
  • Seminumerical algorithms
  • Fast Fourier transforms
  • Number-theoretic algorithms
  • String matching
  • String matching: Rabin-Karp
  • String matching: Knuth-Morris-Pratt
  • Computational Geometry
  • Convex hulls
  • Plane sweep algorithms
  • Polygon triangulation
  • Lower bounds
  • Information theory
  • Adversary arguments
  • Reductions and transformations
  • NP-hard, NP-easy, and NP-complete problems

Click to Read More/Download

Labels:

Art of Programming Contest - C Programming Tutorials | Data Structures | Algorithms

Compiled by Ahmed Shamsul Arefin

Review Note

A Computer programming contest is a pleasurable event for the budding programmers, but only a few books are available as a training manual for programming competitions. This book is designed to serve as a textbook for an algorithm course focusing on programming as well as a programming course focusing on algorithms. The book is specially designed to train students to participate in competitions such as the ACM International Collegiate Programming Contest.
The book covers several important topics related to the development of programming skills such as, fundamental concepts of contest, game plan for a contest, essential data structures for contest, Input/output techniques, brute force method, mathematics, sorting, searching, greedy algorithms, dynamic programming, graphs, computational geometry, Valladolid Online Judge problem category, selected ACM programming problems, common codes/routines for programming, Standard Template Library (STL), PC2 contest administration and team guide.The book also lists some important websites/books for ACM/ICPC Programmers.
I believe that the book will be book will be of immense use for young programmers interested in taking part in programming competitions.
Dr. M. Lutfar Rahman
Professor, Department of Computer Science and Engineering (CSE)
University of Dhaka.
Bangladesh.
Click to Read More/Download
Labels:

The FXT library: Fast transforms and low level algorithms

Here you find
  • the FXT package
  • the "Algorithms for programmers" text (the fxtbook)
  • the amorphous FFT bucket moved to the fftpage

The FXT library

Latest FXT version: fxt-2007.01.13.tgz (approx. 950kB), distributed under the GPL.

Here are a some (well, more than 200) demos.

Much of the low level bit-magic code is shown on the bit wizardry page.

Read the short description in description.txt, the Linux Software Map (LSM) file fxt.lsm

Generated doc-oids:

  • aux0-doc.txt auxiliary routines
  • aux1-doc.txt auxiliary routines for 1-dim arrays
  • aux2-doc.txt auxiliary routines for 2-dim arrays
  • bits-doc.txt bit wizardry
  • bpol-doc.txt binary polynomials and arithmetic over GF(2**n)
  • comb-doc.txt combinatorics (combinations, partitions etc.)
  • convolution-doc.txt convolution
  • mult-doc.txt multiplication of large numbers
  • correlation-doc.txt correlation
  • dctdst-doc.txt cosine and sine transforms
  • ds-doc.txt data structures (FIFO, heap etc.)
  • fft-doc.txt fast Fourier transforms
  • realfft-doc.txt real valued FFTs
  • fht-doc.txt fast Hartley transforms
  • walsh-doc.txt Walsh transforms
  • haar-doc.txt Haar transforms
  • mod-doc.txt modular arithmetics and number theory
  • ntt.h-doc.txt number theoretic transforms
  • perm-doc.txt permutations
  • sort-doc.txt sorting and searching
  • data-doc.txt tables of mathematical data. The tables can also be accessed via the mathdata page. generated index of all docs

Click to Read More/Download

Labels:

Algorithms

by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani
Prologue

Look around you. Computers and networks are everywhere, enabling an intricate web of complex human activities: education, commerce, entertainment, research, manufacturing, health management, human communication, even war. Of the two main technological underpinnings of this amazing proliferation, one is obvious: the breathtaking pace with which advances in microelectronics and chip design have been bringing us faster and faster hardware.

This book tells the story of the other intellectual enterprise that is crucially fueling the computer revolution:

Books and algorithms
Two ideas changed the world. In 1448 in the German city of Mainz a goldsmith named Johann Gutenberg discovered a way to print books by putting together movable metallic pieces. Literacy spread, the Dark Ages ended, the human intellect was liberated, science and technology triumphed, the Industrial Revolution happened. Many historians say we owe all this to typography. Imagine a world in which only an elite could read these lines! But others insist that the key development was not typography, but algorithms....

Click to Read More/Download

Labels:

Java Data Structures (2nd edition)

© 1996-2001, Particle
Welcome to Java Data Structures (2nd edition). This document was created with an intent to show people how easy Java really is, and to clear up a few things I've missed in the previous release of the document.............
In contrast to what most people think about Java, it being a language with no pointers, data structures are quite easy to implement. In this section, I'll demonstrate few basic data structures. By learning how easy they are to implement in Java, you'll be able to write any implementation yourself.
I also think that this document is a pretty good introduction to Data Structures in general. All these concepts can be applied in any programming language............
Labels:

Data Structures

By Peter M Williams
These notes provide an introduction to some of the most commonly occurring data structures. The language used is Java. The aim is not the greatest generality. The DataStructures package developed here is not as extensive as the Collections framework, first released with Java 1.2. For portable applications, you should use the Collections framework where possible.
The DataStructures package, however, includes graphs which are not currently in the Collections framework; and the greater simplicity of the DataStructures package makes it more suitable as a basis for learning about fundamental principles of data structures and algorithms.
Labels:

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

By Bruno R. Preiss
The primary goal of this book is to promote object-oriented design using Java and to illustrate the use of the emerging object-oriented design patterns. Experienced object-oriented programmers find that certain ways of doing things work best and that these ways occur over and over again. The book shows how these patterns are used to create good software designs. In particular, the following design patterns are used throughout the text: singleton, container, enumeration, adapter and visitor.
Virtually all of the data structures are presented in the context of a single, unified, polymorphic class hierarchy. This framework clearly shows the relationships between data structures and it illustrates how polymorphism and inheritance can be used effectively. In addition, algorithmic abstraction is used extensively when presenting classes of algorithms. By using algorithmic abstraction, it is possible to describe a generic algorithm without having to worry about the details of a particular concrete realization of that algorithm.
A secondary goal of the book is to present mathematical tools just in time. Analysis techniques and proofs are presented as needed and in the proper context. In the past when the topics in this book were taught at the graduate level, an author could rely on students having the needed background in mathematics. However, because the book is targeted for second- and third-year students, it is necessary to fill in the background as needed. To the extent possible without compromising correctness, the presentation fosters intuitive understanding of the concepts rather than mathematical rigor.
Labels:
Subscribe to: Posts (Atom)

Followers