Write a Program
- Write a computer program to list all the subsets of a set (input by the
user) in the order described in this problem.
Hamiltonian Paths
A Hamiltonian path, named for the mathematician William
Rowan Hamilton (1805 - 1865), is one that visits every vertex in a graph
exactly once. A Hamiltonian
cycle also visits every vertex exactly once
but has the additional property that the first vertex and the last vertex in
the path are adjacent (so you could follow an edge and start again at the
beginning).
- For the graphs created by the subsets problem, how many Hamiltonian
paths are there? How many total paths are there? Is there always a
Hamiltonian cycle?
- Is there a Hamiltonian cycle on a soccer ball?
- In a round-robin tournament, each team plays every other team exactly
once. Rankings are decided by looking at the win/loss record of each team.
Suppose that n teams play p round-robin tournaments with no tie games.
Prove that there is an order of the teams t1, t2, ..., tn so that ti beat ti+1
for i = 1, 2, ..., (n - 1).
A New Binary Number System
The subsets problem is connected to
a real problem in computer science. Computers keep track of information
using binary numbers made up of 0’s and 1’s. These 0’s and 1’s are really
“switches” with on and off (or high- and low-voltage) positions. When a
computer counts in binary numbers, sometimes only one of the switches
has to change position. For example, in going from 100 to 101, only the
last digit is different. However, sometimes many switches have to change
position. For example, going from 111 to 1000 requires all four digits to
switch.
These switch changes can’t really happen simultaneously--the digits will flip at
slightly different times. For example, you could picture the change from 111 to 1000
happening this way: 111 
1111 1110 1100 1000. Not until the final digit
changes is the number correct. This is inefficient and could cause errors if the data is
read “mid-flip.”
A more efficient (and safer) version of the binary number system would solve this
problem.
- Come up with a new binary number system--a way to code numbers with
just 0’s and 1’s so that in moving from one number to the next, you only
need to change one digit. Note: The bits may not have their customary
place value.
- Write a computer program to do arithmetic in your new binary number
system, or to convert between your binary number system and the decimal
system.
