# Programs from The Algorithm Design Manual (2nd Edition)

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.

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
• 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.
• 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