Lately I've been puzzling on the intersection between computing/ algorithms and mathematics. This lead me to look at: Donald Knuth's Selected Papers on Computer Science http://tinyurl.com/5zraag
In it he has several great essays, one of which is: Mathematics and Computer Science: Coping with Finiteness In it he has a section Counting the Paths on a Grid. Here are some scanned images of figures he uses: http://backspaces.net/temp/GridPath1.png http://backspaces.net/temp/GridPath2.png And better yet, here's a netlogo model: http://backspaces.net/temp/GridPath/ 2 Questions/Puzzles I'd like to share with you: 1 - The probability for each path is calculated by looking at the possible choices at each point in the path. If you see a "3" at a node, for example, the probability assigned to the next move is 1/3. The total probability for a given path is the product of the individual ones. Question: how can I show that this forms a true probability space? .. i.e. the sum of the probabilities for all possible paths is 1.0. 2 - (Mainly for geeks) My solution for the model is to use a floodfill after each move to find the possible next moves. For such a small space (11x11), this is not computationally intensive, but seems a bit heavy handed. Question: is there an algorithm that uses a simpler approach? -- Owen ============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College lectures, archives, unsubscribe, maps at http://www.friam.org
