List of Figures


Competition-We Can’t All Be Winners.

Figure 1-1: The thief T starts where indicated. He is nine blocks from the northern, eastern, southern, and western borders, though only the first two are shown.

Design-Imagination Rules

Figure 1-2: How can Indy use his whip to navigate from the bottom of the corridor to the top without hitting the barriers or the sides? Assume he can approach the bottom from any angle. The dot represents a pole.
Figure 1-3: Indy connects briefly to the pole (the dark circle) to rotate to a line parallel to the walls of the corridor.
Figure 1-4: Indy wants to go from the bottom to the top without hitting the barriers or the walls. Indy may enter the bottom at any angle. Can Indy do it with the two poles indicated as black circles?
Figure 1-5: What is the minimum number of poles Indy will need to skate over all the Xs?
Figure 1-6: A four-node network in which there is a one- or two-link path from any node to any other even if a node is deleted.
Figure 1-7: A six-node network in which there is a one- or two-link path from any node to any other even if a node is deleted.
Figure 1-8: Two possible ways of cutting the original pie (above) into three pieces of equal size. The bottom left shows two parallel cuts. The bottom right shows two perpendicular cuts.

Chance-Getting On the Right Side of Luck

Figure 1-9: The goal is to go from the S to the E, always staying on black squares. Don’t fall off the board.

Inference-What are You Thinking?

Figure 1-10: You are to travel this maze from entrance to exit by keeping your left hand on the wall and walking forward. Will you make it?

Optimization-Doing More with Less

Figure 1-11: Somewhere between Start and End in this road network is an eight-block tunnel some bad guys have built.
Figure 1-12: Bob’s preferences in life. Note that he has no preferences for certain qualities, e.g., he has not said whether he prefers Alice to be cultured or to be a windsurfer.
Figure 1-13: Alice’s preferences in life. Note that she has no preference about whether Bob is rich or a biker.
Figure 1-14: The northern half of the city T wants to escape from. The police are represented by dashed arrows and the thief by solid arrows. T leaves after 22 block steps.
Figure 1-15: Indy uses the first pole both to straighten out and then eventually to curve in.
Figure 1-16: This is the route Indy should take starting from the bottom to win at Treasure Skater. The numbers indicate the order in which Indy visits the Xs. Notice that he does a sharp turn using the lower left pole and then uses that pole again to curve up to X1. He then uses the lower left pole and the lower right pole twice to swing to 2 and 3.
Figure 1-17: The difficult part of the solution is to change directions as Indy descends between X2 and X4. He has to use a distant pole.
Figure 1-18: An eight-node network in which there is a two-link path from any node to any other even if a node is deleted. Within one foursome, there is a single link from any node to any other. For a trip from a node n in one foursome to a node m in the other foursome, there are two paths of length at most two. These go through different intermediate nodes.
Figure 1-19: A twelve node, wounded distance two network using only 21 links.
Figure 1-20: Switchboard nodes are clear circles. Supervertices, each consisting of 24 nodes, are big dark circles. The basic design represents 576 links. In addition, we have shown two links (the dashed curves) between non-neighboring switchboard nodes. Altogether there are 12 such links.
Figure 1-21: Recursive perpendicular cuts satisfying the child cut rule.
Figure 1-22: Without the child cut rule, one can obtain a smaller total perimeter for five pieces.
Figure 1-23: Without the child cut rule, here is the best design I know of for nine pieces.
Figure 1-24: Without the child cut rule or the requirement that all cuts must be parallel to an original side, one can reduce the perimeter quite noticeably.
Figure 1-25: Because you know the direction of the roads as they leave an intersection, each pair on each row determines the fate of the tunnel on that row and the next.
Figure 1-26: The center column’s point probes tell whether the tunnel goes up the center line. If it misses the center, it must go either east or west. Because of the length limitation, it cannot go in both directions. Without reading the explanation, you may be able to figure out which column is taken between every pair of rows.
Figure 1-27: The groups have been ordered in ascending order based on their medians. Thus, M1 M2 M3 M4 M5. Within each group imagine low blood pressures to be at the bottom of the line segment corresponding to that group and high blood pressures near the top.
Figure 1-28: The dark rectangles represent values that are less than or equal to M3.
Figure 1-29: The dark rectangles represent values greater than or equal to M1.

The Puzzles

Figure 2-1: I is an industrial block, O is an office block, W is a warehouse block, S a shopping block, H a housing block, P a park, and X vacant. The industrial zone must be far from the housing.
Figure 2-2: Because the industry is clean, the industrial zone can be folded among the other uses, yielding a 4 by 4 square.
Figure 2-3: The larger circle has a radius of 450 meters and the smaller has a radius of 350 meters. Their centers at (0,0) and (300,400) are 500 meters apart by the Pythagorean theorem.
Figure 2-4: The larger circle has a bigger uncertainty, reflecting the 10% accuracy.
Figure 2-5: For each approximate rectangle surrounding an intersection point, put the sensor 30 meters to the right of the center of the rectangle. Thus, not only will one know which rectangle contains the treasure, but also more or less where in the rectangle. For example, if the sensor reading is greater than 42.3 meters, then the treasure trunk is in the subrectangle to the right of the portion completely covered by the circle.
Figure 2-6: Given a sensor reading of d, the sketch shows the nominal circle, the smaller error circle (dashed), and the larger error circle (dashed). The treasure must be inside the dotted rectangle.
Figure 2-7: The beginning of the dynamic programming matrix. The top row represents the number of inserts to go from an empty string to, respectively, an empty string, a string consisting of ‘T’ alone, a string consisting of ‘TG’, and so on. The left column represents the number of deletes to go to an empty string from, respectively, an empty string, a string consisting of ‘A’, a string consisting of ‘AG’, and a string consisting of ‘AGA’.
Figure 2-8: Filling in the second row corresponds to the problem of transforming ‘A’ to ‘TGGAG’. As you can see from the arrows, the best thing to do is to insert ‘TGG’ and then ‘G’ along with a zero-cost replacement of ‘A’ by ‘A’.
Figure 2-9: Filling in the third row of the dynamic programming matrix plus indications of some possible best paths, though not all of them.
Figure 2-10: The entire matrix for the warm-up. In the end, we match ‘GA’ with ‘GA’ and insert or relabel for the rest.
Figure 2-11: Fill in this matrix to solve the problem.
Figure 2-12: An optimal edit sequence to go from “TAGATGGTCT” to “TGGAGACAGTCT”. Starting from the first letter, there are many replacements. Arrows always point to the right, downward, or to the right and downward.
Figure 2-13: The salesman starts at C and ends at C. Each time he goes to the closest unvisited city. How well will Bob do?
Figure 2-14: What happens when Bob visits the nearest previously unvisited city first?
Figure 2-15: A better route for Bob.
Figure 2-16: A set of cities. Assume that cost is proportional to distance. The goal is to construct a minimum spanning tree.
Figure 2-17: The minimum spanning tree in this case. Note that we do not need to know which is the starting city.
Figure 2-18: Take the minimum spanning tree and then go up and down each edge of the tree. That gives a route no matter which city one starts from. It’s true that this route revisits cities, so can be improved. Already, though, its cost is no more than twice that of the optimal one.
Figure 2-19: Some simple heuristic improvements to the minimum spanning tree-based route that will either leave the cost the same or reduce it (assuming the triangle inequality holds).
Figure 2-20: All unmarked edges have a cost of 5. The marked edge Z to C has a cost of 60 (violating symmetry and the triangle inequality). The marked edge Z to Y has a cost of 6, as does the edge from Y to Z.
Figure 2-21: The spanning tree starting at C contains the directed edges C to Z, C to X, and C to Y. Back edges play no role. Unfortunately, the travel route using that tree must traverse the back edge having cost 60. Altogether we get a cost of 85.
Figure 2-22: A much cheaper route moves clockwise through the nodes and has a cost of only 21.
Figure 2-23: The horizontal axis represents the search space. The vertical represents the cost. A greedy approach, given a location in the search space, will perform moves that decrease cost. So the arrows always start from a higher cost and go to a lower one.
Figure 2-24: In simulated annealing and other heuristic search techniques, some moves increase the cost. You can see that with the rightmost arrow which goes from a lower cost valley to a higher cost hill. The idea is to escape local cost minima.
Figure 2-25: A search space for which simulated annealing might have a difficult time finding a solution. The optimum is at a very specific part of the search space, so a move is unlikely to find it.
Figure 2-26: Each line segment (dashed or solid) represents a road. The solid line represents an alliance. Only C4 and C5 are matched. No other city has an ally.
Figure 2-27: In this case, we have two matchings: C3 with C4, and C5 with C7. Other pairs of cities could be matched, but there cannot be more than two matching pairs in all.




Puzzles for Programmers and Pros
Puzzles for Programmers and Pros
ISBN: 0470121688
EAN: 2147483647
Year: 2007
Pages: 81
Authors: Dennis Shasha

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net