Only starred problems need to be turned in. Homework will usually be assigned on Thursday and will be due by the end of class the following Thursday. No late homework will be accepted. The two lowest homework scores will be dropped. Homework must be stapled and clearly labelled with your name. Students are encouraged to collaborate on homework assignements. Collaboration means working together to frame problems, devise approaches, and compare results. The final work, however, must be the work of the individual student, indicating that you alone prepared the work and understand the material. This means you must write up solutions independently.


If you believe there is a mistake on any grading, you have two weeks from when the item is handed back to bring it to my attention.
Number Due Problems Solutions
19/5Section 1.1, Problems 1, *2a, *4, *28
1: Suppose interstate highways join the six towns A,B,C,D,E,F as follows: I-77 goes from B through A to E; I-82 goes from C through D, then through B to F; I-85 goes from D through A to F; I-90 goes from C through E to F; and I-91 goes from D to E.
a: Draw a graph of the network with vertices for towns and edges for segments of interstates linking neighboring towns.
b: What is the minimum number of edges whose removal prevents travel between some pair of towns?
c: Is it possible to take a trip starting from town C that goes to every town without using any interstate highway for more than one edge? 2a: Suppose four teams, the Aces, the Birds, the Cats, and the Dogs, play each other once. The Aces beat all three opponents except the Birds. The Birds lots to all opponents except the Aces. The Dogs beat the Cats. Represent the results of these games with a directed graph
4: Suppose there are 6 people---John, Mary, Rose, Steve, Ted, and Wendy---who pass rumors among themselves. Each day John talks with Mary and Wendy; Mary talks with John, Rose, and Steve; Rose talks with Mary, Steve, and Ted; Steve talks with Mary, Rose, Ted, and Wendy; Ted talks with Rose, Steve, and Wendy; and Wendy talks with John, Steve, and Ted. Whatever people hear one day they pass on to others the next day.
a: Model this rumor-passing situation with a graph.
b: How many days does it take to pass a rumor from John to Steve? Who will tell it to Steve?
c: Is there any way that if two people stopped talking to each other, it would take three days to pass a rumor from one person to all the others?
28: A game for two players starts with an empty pile. Players take turns putting one, two, or three pennies in the pile. The winner is the player who brings the value of the pile up to 16 cents.
a: Make a directed graph modeling this game.
b: Show that the second player has a winning strategy by finding a set of four "good" pile values, including 16 cents, such that the second player can always move to one of the "good" piles.
29/12Section 1.2, Problems 3*, 5 (perhaps not all of them), 6*, 8*, 11
Section 1.3, Problems 2*, 4*, 9, 12*
39/19Section 1.4, Problems 3 (perhaps not all of them), 4*, 7, 8*, 12*, 14*, 18*
Section A1, Problems 1, 2*, 7, 8*
Section 2.1, Problems 1, 2*
49/26Section 2.2, Problems 3, 4a-d*, 4e-p, 8*, 13, 16*, 23
Section 2.3, Problems 1 (some of them), 2*, 3, 4*
510/3Section 2.3, 9, 10*
Section 2.4, Problems 1, 2*, 9, 16*
610/24Section 5.1, Problems 5, 6*, 13, 14*
Section 5.2, Problems 5, 11, 12*, 30*, 41, 42*, 53, 54*, 61, 70*
A group of n people are given the option of attending a movie. Each person decides whether or not to go independently of the others. How many possible groups of people who attend the movie are there? By counting this quantity in two different ways, give a nice expression for the value of
You do not need to simplify your answers.
710/31Section 5.3, Problems 5, 6*, 7, 10*, 19, 22*, 23, 24*
Section 5.4, Problems 1, 2*, 12*, 13, 20*, 27, 28*, 52*, 57, 58*
Section 5.5, Problem 9*
You do not need to simplify your answers
811/7Section 5.5, Problem 15*
Section 6.1, Problems 3, 4*, 13, 14*, 20*, 21
Section 6.2, Problems 1, 2*, 5, 6*, 7, 8*, 17, 18*
Section 6.3, Problems 1, 2*, 15, 16*
911/14Section 7.1, Problems 1, 4*, 8*, 11, 22*, 23
Section 7.3, Problems 1, 2*, 3, 6*, 7, 8*
Section 7.5, Problems 1, 2a*, 3
1012/5Section 8.1, Problems 1, 2*, 35, 36*
Section 8.2, Problems 3, 6*, 13, 18*