These programs all appear in my book:
The Algorithm Design Manual (2nd Edition)
by Steven Skiena, Springer-Verlag, New York 2008.
See my website http://www.algorist.com for additional information.
This book can be ordered from
Amazon.com.
The programs from the new third edition are available here.
The programs are made available under the following copyright notice:
Copyright 2003, 2008 by Steven S. Skiena; all rights reserved.
Permission is granted for use in non-commerical applications
provided this copyright notice remains intact and unchanged.
What follows are a list of all the files in this directory with a
brief description of what they are.
A single tar file with all the programs is also available.
- Makefile --- instructions on how to compile all of our programs
- README --- this file; a description of all programs in distribution
- annealing.c --- a fairly generic implementation of simulated annealing
- annealing.h --- header file for simulated annealing
- backtrack.c --- a generic implementation of backtracking
- backtrack.h --- header file for generic backtracking
- bfs-demo.c --- driver program demonstrating breadth-first search
- bfs-dfs.c --- a generic implementation of graph traversal
- biconnected.c --- Identify articulation vertices in a graph
- binomial.c --- compute the binomial coefficients using dynamic programming
- bipartite.c --- Two color a bipartite graph
- bool.h --- header file for boolean datatype
- component-graphs/ --- a directory with test files for connected components
- connected.c --- compute connected components of a graph
- datafiles/ --- a directory with test files for all the programs, see test-script
- dfs-demo.c --- driver program demonstrating depth-first search
- dijkstra.c --- compute shortest paths in weighted graphs
- distance.c --- compute Euclidian distances
- editbrute.c --- compute string edit distance *without* dynamic programming
- editdistance.c --- a generic implementation of string comparison via dp
- editdistance.h --- header file for string comparison
- fib.c --- Compute the binomial coefficients using dynamic programming
- findcycle.c --- identify a cycle in a graph, if one exists
- floyd.c --- compute all-pairs shortest paths in weighted graphs
- gcd.c --- compute the greatest common divisor of two integers
- graph.c --- a generic adjacency list-in-array graph data type
- graph.h --- header file for graph data type
- item.h --- Header file for linked implementation
- kruskal.c --- Compute minimum spanning trees of graphs via Kruskal's algorithm.
- lcs.c --- longest common subsequence of two strings
- list-demo.c --- Driver for a linked list-based container implementation.
- list.h --- Header file for linked implementation
- matrix.c --- Multiply two matrices.
- mwt.c --- Compute the minimum weight triangulation of convex polygons
- netflow.c --- network flow implementation -- augmenting path algorithm
- original/ --- a directory with the original versions from Programming Challenges
- partition.c --- Optimally balance partitions using dynamic programming
- paths.c --- Enumerate the paths in a graph via backtracking
- permutations.c --- construct all permutations via backtracking
- prim.c --- compute minimum spanning trees of graphs via Prim's algorithm
- priority_queue.c --- Implementation of a heap / priority queue abstract data type.
- priority_queue.h --- Header file for queue implementation
- queue.c --- implementation of a FIFO queue abstract data type
- queue.h --- header file for queue implementation
- set_union.c --- Implementation of a heap / priority queue abstract data type.
- set_union.h --- Header file for union-find data structure implementation
- sorting.c --- implementations of primary sorting algorithms
- stack.c --- Implementation of a LIFO stack abstract data type.
- stack.h --- Header file for queue implementation
- stringedit.c --- compute the optimal alignment matching two strings
- strong.c --- Identify strongly connected components in a graph
- subsets.c --- construct all subsets via backtracking
- substringedit.c --- approximately match one string as a substring of another
- sudoku.c --- A backtracking program to solve Seduku
- sudoku-examples/ --- a directory with test files for sudoku
- test-script* --- run tests on each of the programs created by Makefile
- topsort1.c --- Topologically sort a directed acyclic graph by DFS numbering (DAG)
- topsort.c --- topologically sort a directed acyclic graph
- tree-demo.c --- Driver for a binary search tree container implementation.
- tree.h --- Header file for binary search tree implementation
- tsp.c --- Heuristics for solving TSP
- tsp.h --- Header file for tsp
- tsp-examples/ --- a directory with test files for the traveling salesmen
- wgraph.c --- a generic weighted graph data type
- wgraph.h --- header file for weighted graph type
Also included are some programs from my other book, Programming Challenges
- 10055.c --- program demonstrating standard IO in C
- 10055.cc --- program demonstrating standard IO in C++
- 10055.java --- program demonstrating standard IO in Java
- 10055.pascal --- program demonstrating standard IO in Pascal
- 8-queens.c --- solve the eight queens problem using backtracking
- bignum.c --- implementation of large integer arithmetic
- cgtest.c --- driver program for computational geometry routines
- convex-hull.c --- compute convex hulls of points in the plane
- elevator.c --- elevator stop optimization via dynamic programming
- geometry.c --- basic geometric primitives and data types
- geometry.h --- header file for geometric data types
- geotest.c --- driver program for geometry routines
- name.c --- corporate name changing program -- string example
- order.c --- demonstrate traversal orders on a grid
- plates.c --- compute the number of circles in two different packings
- polly.c --- rank the desirability of suitors -- sorting example
- primes.c --- compute the prime factorization of an integer
- random.c --- compute random numbers within given ranges
- sentinel.c --- example search program using sentinels
- superman.c --- compute Superman's flight path -- geometry example
- triangulate.c --- triangulate a polygon via ear-clipping, and compute area
- war.c --- simulation of the children's card game War