Puzzle: Why is 1/3 ·3 = 1 on most computers nowdays? for lecture on Jan 18
On a cheap pocket calculator, an expensive calculator, in your
favorite programming language, and in your favorite spreadsheet,
determine what is the smallest integer i > 0 such that the floating
point computation 1/i ·i ¹ 1.
(If you do this in a program, try both single and double precision.)
Try to determine the machine e for your devices, which is the
smallest number such that 1+e > 1.
Puzzle: Lengthening a rail for lecture on Jan 20
Puzzle: A simple game of ``Life'' for lecture on Jan 25
Whenever you find a white square with two or more black neighbors,
color it black. When no more squares can be colored, the game is
done. (You can consider this a simplified form of Conway's "Game of
Life" with no death rule, and 4 neighbors instead of 8.)
What is the smallest value of k for which the game can end with no
white squares? Prove it. (I heard this one from Subhash Suri.)
Puzzle: Embedding a given tree on a given set of points for lecture on Feb 1
Puzzle: Untangling a polygon for lecture on Feb 3
Show that repeated application of the uncrossing operation will
produce a simple polygon on the points of P. How many uncrossings
are necessary?
Puzzle: Connections and completions? for lecture on Feb 8
Puzzle: What about the top part of the convex hull? for lecture on Feb 10
Puzzle: How many changes in a dynamic triangulation? for lecture on Feb 15
For your algorithm, what is the worst configuration you can design.
Design configurations that are as bad as
possible for your algorithms; how many changes can you get as a
function of n?
The representation of the fraction [1/3] is a repeating decimal
or binary number, and we know that a computer or calculator is going
to truncate after some number of digits or bits. Yet on almost all
computers and most calculators 1/3 ·3 is exactly 1. Why?
A one-mile-long straight rail, fixed at its ends, is lengthened
by one foot (to 5281 feet) so that it bows up in a circular arc. Find
the maximum height, d, without losing 4 or 5 significant
digits. (A classic, according to F. S. Acton)
Consider a game
board with an n ×n array of squares, k of which are black
and the rest white. Two squares are considered neighbors if they
common side. (But not if they share a single corner.)
Suppose that you are given a set P of n points in the plane, no
two of which have the same y coordinates and no three of which lie
on a common line. You are also given an abstract tree T with n
nodes, one of which is the root, and n-1 edges, all directed away
from the root. Show that you can always assign each node of T to a
point in P so that the tree can be drawn with all edges directed
downward and no edges crossing.
Suppose you are given a circular sequence of n points
P = (p0,p1,¼,pn), with p0 = pn, which can be interpretted as a
(possibly self-intersecting) polygon.
Suppose that we are asked to
untangle it by using the following uncrossing operation: Find any
two (non-adjacent) segments that intersect, say e and f. Remove
e and f, and reconnect the polyline so that it remains a single
loop. This removes the crossing between e and f, although it may
introduce other crossings.
Three questions on connections and completions:
If we ``lift'' a set of points p_1,p_2,...,p_n in the plane to the
paraboloid by sending (xi,yi) to (xi,yi, xi2+yi2), then
take the lower part of the convex hull and project back down to the
plane, we get the Delaunay triangulation. What if we take the upper
part of the hull?
There are open questions about how many times you need to change the
triangulation as it moves, whether it be a Delaunay or a lazy
triangulation. (See problem set #3.)
The answer in the worst case is known only to be
somewhere between W(n2) and O(n3). Many people have tried
to prove O(n2) for the Delaunay; it might be easier to prove for a
lazy triangulation.
File translated from
TEX
by
TTH,
version 2.60.
On 3 Feb 2000, 05:15.