A GNU-FDL book on algorithmic graph theory by David Joyner, Minh Van Nguyen, and Nathann Cohen. This is an introductory book on algorithmic graph theory. Theory and algorithms are illustrated using the Sage open source mathematics software.
In many problems that require extensive searching, the solution can be described as satisfying two competing constraints, where satisfying each independently does not pose a challenge. As an alternative to tree-based and stochastic searching, for these problems we propose using an iterated map built from the projections to the two constraint sets. Algorithms of this kind have been the method of choice in a large variety of signal-processing applications; we show here that the scope of these algorithms is surprisingly broad, with applications as diverse as protein folding and Sudoku.Our survey of applications shows the difference map algorithm often achieves results comparable to much more sophisticated, special purpose algorithms. Efficient implementations of constraint projections usually are easier than designing the linear program solver at the heart of many optimization algorithms.
Solving the nice puzzle below, I found it easier to define a stream coinductively than to define a function from natural numbers inductively. You’re standing in front of a 100 story building with two identical bowling balls. You’ve been tasked with testing the bowling balls’ resilience. The building has a stairwell with a window at each story from which you can (conveniently) drop bowling balls. To test the bowling balls you need to find the first floor at which they break. It might be the 100th floor or it might be the 50th floor, but if it breaks somewhere in the middle you know it will break at every floor above. Devise an algorithm which guarantees you’ll find the first floor at which one of your bowling balls will break. You’re graded on your algorithm’s worst-case running time. “Running time” here means the number of times we drop a ball.
This is code implements the example given in pages 11-15 of An Introduction to the Kalman Filter by Greg Welch and Gary Bishop, University of North Carolina at Chapel Hill, Department of Computer Science.
Delny is a Python package which can be used to make a Delaunay triangulation from a set of n-dimensional points. It is effectively a Python interface to libqhull, the C library of the Qhull program, but (currently) restricted to Delaunay triangulation. It was first developed to use in a mesh generator developed as dissertation at the University of Southampton with Hans Fangohr as supervisor. This very specific application area was the reason for the limited functionality of the libqhull wrapper, which in turn is likely the reason that there is useable code available.
The goal of the CGAL Open Source Project is to provide easy access to efficient and reliable geometric algorithms in the form of a C++ library. CGAL is used in various areas needing geometric computation, such as: computer graphics, scientific visualization, computer aided design and modeling, geographic information systems, molecular biology, medical imaging, robotics and motion planning, mesh generation, numerical methods... More on the projects using CGAL web page.