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.
he A* (pronounced A-star) algorithm can be complicated for beginners. While there are many articles on the web that explain A*, most are written for people who understand the basics already. This article is for the true beginner. This article does not try to be the definitive work on the subject. Instead it describes the fundamentals and prepares you to go out and read all of those other materials and understand what they are talking about. Finally, this article is not program-specific. You should be able to adapt what's here to any computer language. As you might expect, however, I have included a link to a sample program at the end of this article. The sample package contains two versions: one in C++ and one in Blitz Basic.
yuri gurevich Can any algorithm, never mind how abstract, be modeled by a generalized machine very closely and faithfully? ... If we stick to one abstract level (abstracting from low-level details and being oblivious to a possible higher-level picture) and if the states of the algorithm reflect all the pertinent information, then a particular small instruction set suffices in all cases. adapted from Yuri Gurevich, "Sequential Abstract State Machines Capture Sequential Algorithms"
Zipper is a purely functional data structure used in functional programming to solve some problems in a way that uses notions like “context” and “hole”. It is related to the generalization of the notion of “derivative” (for types). The zipper was described by Gerard Huet in 1997. It has some conceptual similarity to the gap buffer technique sometimes used with arrays. Zippers are multidimensional in the sense that they can be used as lists or trees by placing additional restrictions upon them. Such derived data structures are usually referred to by saying a tree with zipper or a list with zipper to give the image that the structure is a tree or a list, with a zip slider attach to it as an afterthought.
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.
Keeping two or more copies of the same document synchronized with each other in real-time is a complex challenge. This paper describes the differential synchronization algorithm. Differential synchronization offers scalability, fault-tolerance, and responsive collaborative editing across an unreliable network. 1 Conventional Strategies The three most common approaches to synchronization are ownership, event passing and three-way merges. These methods are conceptually simple, but all have drawbacks. link to googletalk video and mobWrite sw