About the Book

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

• By Language
  • C
  • C++
  • C#
  • Java
  • FORTRAN
  • Python
  • Mathematica
  • Pascal
  • ADA
  • Lisp
  • Binary
• By Problem
  • 1.1 Data Structures
    • Dictionaries
    • Priority Queues
    • Suffix Trees and Arrays
    • Graph Data Structures
    • Set Data Structures
    • Kd-Trees
  • 1.2 Numerical Problems
    • Solving Linear Equations
    • Bandwidth Reduction
    • Matrix Multiplication
    • Determinants and Permanents
    • Constrained and Unconstrained Optimization
    • Linear Programming
    • Random Number Generation
    • Factoring and Primality Testing
    • Arbitrary Precision Arithmetic
    • Knapsack Problem
    • Discrete Fourier Transform
  • 1.3 Combinatorial Problems
    • Sorting
    • Searching
    • Median and Selection
    • Generating Permutations
    • Generating Subsets
    • Generating Partitions
    • Generating Graphs
    • Calendrical Calculations
    • Job Scheduling
    • Satisfiability
  • 1.4 Graph Problems -- polynomial-time problems
    • Connected Components
    • Topological Sorting
    • Minimum Spanning Tree
    • Shortest Path
    • Transitive Closure and Reduction
    • Matching
    • Eulerian Cycle / Chinese Postman
    • Edge and Vertex Connectivity
    • Network Flow
    • Drawing Graphs Nicely
    • Drawing Trees
    • Planarity Detection and Embedding
  • 1.5 Graph Problems -- hard problems
    • Clique
    • Independent Set
    • Vertex Cover
    • Traveling Salesman Problem
    • Hamiltonian Cycle
    • Graph Partition
    • Vertex Coloring
    • Edge Coloring
    • Graph Isomorphism
    • Steiner Tree
    • Feedback Edge/Vertex Set
  • 1.6 Computational Geometry
    • Robust Geometric Primitives
    • Convex Hull
    • Triangulation
    • Voronoi Diagrams
    • Nearest Neighbor Search
    • Range Search
    • Point Location
    • Intersection Detection
    • Bin Packing
    • Medial-Axis Transformation
    • Polygon Partitioning
    • Simplifying Polygons
    • Shape Similarity
    • Motion Planning
    • Maintaining Line Arrangements
    • Minkowski Sum
  • 1.7 Set and String Problems
    • Set Cover
    • Set Packing
    • String Matching
    • Approximate String Matching
    • Text Compression
    • Cryptography
    • Finite State Machine Minimization
    • Longest Common Substring
    • Shortest Common Superstring
• Algorithm Links
  • Algorithm Lectures
  • Algorithm Design Manual Information
  • CSE 373 Course page
  • NIST Dictory of Algorithms and Data Structures
  • World of Mathematics
  • Programming Challenges
  • Graduate Study Opportuinties

XTANGO is implemented on top of UNIX and the X11 Window System. It can be run on either color or black-and-white monitors. XTANGO is available for use via anonymous ftp from ftp.cc.gatech.edu in directory pub/people/stasko.

Included with the XTANGO distribution is a large collection of animations. Several of which are quite fun to watch. My favorites include:

• AVL trees (avl)

• Binomial heaps (binoheap)

• Boyer-Moore string matching (boyer)

• Bin Packing (bpack)

• Bubble sort (bsort)

• Convex Hull (conhull)

• Fast Fourier Transform (fft)

• Fibonacci heaps (fiboheap)

• Heapsort (heap)

• Knight's tour (knight)

• K-selection (ksel)

• Eight Queens (queens)

• Quicksort (quicksort)

• Radix sort (radix)

• Treaps (treap)

The basic process of animation consists of implementing the algorithm in C (another language can be used, but it must just produce a trace file which is read by a C program driver) and then deciding on the important events to be portrayed during the execution of the algorithm. These events then activate animation routines implemented in a separate file using the XTANGO animation package to create and manipulate objects (circles, squares, lines, and so on). Transitions on objects include movement, color change, resizing, and filling, as well as others. For example, the animation for binary search consists of a series of rectangles, each representaing one of the elements being searched. A bouncing circle hits the current dividing element, which changes color. The ball then bounces to the next dividing element and continues to do this until the desired element has been found. To learn more about XTANGO, see the September 1990 issue of IEEE Computer which has an article about the TANGO system, a ancestor of XTANGO.

POLKA is a general purpose animation system that is particularly well-suited to building animations of programs, algorithms and computations, especially parallel computations. POLKA supports color, real-time, 2 & 1/2 dimensional, smooth animations. The focus of the system is on a balance of power and ease-of-use. POLKA provides its own high-level abstractions to make the creation of animations easier and faster than with many other systems. Programmers need not be graphics experts to develop their own animations. POLKA also includes a hot new interactive front-end called SAMBA that can be used to generate animations from any type of program that can generate ASCII.

POLKA is implemented in C++ on top of UNIX and the X11 Window System, and it requires the Motif or Athena widget set. (Because it supports Athena widgets, if you're running Linux, you should be able to get Polka to build there.) It can be run on either color (much better) or black-and-white monitors. POLKA is available for use via anonymous ftp from ftp.cc.gatech.edu under pub/people/stasko.