You are given two bags, each containing some number NumPerBag of flares. You know there are NumBad flares in one of the bags but not which bag. The other bag has all good flares. Each time you test a flare, you use it up.
Dennis Shasha
Advertisement
Upstart Puzzles: Strategic Friendship
Consider the following game (first posed to my close friend Dr. Ecco) played among several entities. Each entity Ei has a certain force Fi and a certain wealth Wi.
Upstart Puzzles: Take Your Seats
A popular logic game involves figuring out an arrangement of people sitting around a circular table based on hints about, say, their relationships. Here, we aim to determine the smallest number of hints sufficient to specify an arrangement unambiguously.
Upstart Puzzles: Proving Without Teaching/Teaching Without Proving
Peter Winkler's mathematically elegant, often whimsical puzzles have been a joy to read and wrestle with. My columns now embark on a different path. Each will come in two parts: one quite doable, the other an "upstart," or insolent variant. Here we go.
An Interview with Michael Rabin
Michael O. Rabin, co-recipient of the 1976 ACM A.M. Turing Award, discusses his innovative algorithmic work with Dennis Shasha.
Using a relational system on Wall Street: the good, the bad, the ugly, and the ideal
Developers of a Wall Street financial application were able to exploit a relational DBMS to advantage for some data management tasks (the good). For others, the relational system was not helpful (the bad), or could be pressed into service only by means of major or minor contortions (the ugly). The authors identify database constructs that would have simplified developing the application (the ideal).
Shape the Future of Computing
ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.
Get Involved