Excursions in Mathematics
Rough Schedule
Fall, 2004
This is only a rough schedule. We may spend more or less time on some topics. Problems are assigned after we cover the corresponding material, and are due the following class day. There may be some additional problems assigned.

CHAPTER 1: VOTING

Day One. Read all of Chapter 1 quickly to get an overview, and then go back and read pages 3-9 carefully. Pay special attention to the distinction between a method and a criterion.

Problems: 1, 4, 10, 12, 19.

Day Two. Chapter 1, pages 9-20.

Problems: 27, 31, 34, 36, 37.

Day Three. Chapter 1, pages 20-26.

Note the distinction between extended methods and recursive methods. The word ``recursive'' indicates a repetition of a process. (To ``recur'' is to ``occur again,'' sometimes over and over.)

Problems: 40, 42, 51, 56.

CHAPTER 2: WEIGHTED VOTING SYSTEMS

Day One. Read all of Chapter 2 quickly to get an overview, and then go back and read pages 51-54 carefully.

Problems: 6-9, 49, 50. In 50, assume that the players are listed in descending order of weight.

Day Two. Pages 54-63. The Banzhaff power index.

Problems: 11, 12, 14, 18.

Day Three. Pages 63-70. The Shapley-Shubik power index.

Problems: 24, 25, 27, 29, 42, 56, 58. If these take you a long time, then you're doing them the hard way. Try to find the easier way.

Test No. 1 (Chapters 1 and 2)

CHAPTER 3: FAIR DIVISION

Day One. Read all of Chapter 3 quickly to get an overview. Then go back and read pages 87-97 carefully. These cover the preliminaries and the lone divider method.

Problems: 3, 5, 7, 9, 15, 20, 21, 23, 54.

Day Two. Chapter 3, pages 100-107. On this day we will work on the last diminisher method and start on the method of sealed bids. We will omit the lone chooser method, but you should at least read about it quickly.

Problems: 33, 35, 36.

Day Three. Chapter 3, pages 107-110. Methods for discrete problems (in contrast to continuous problems): The method of sealed bids and the method of markers.

Problems: 39, 41, 42, 47-51, 62, 64.

CHAPTER 4: APPORTIONMENT

Day One. Read all of Chapter 4 quickly to get an overview, and then go back and read up through page 143 carefully. This covers the preliminary ideas, and then Hamilton's method, without yet starting on the paradoxes that plague it.

Problems: 1, 3, 6, 7, 9, 12. Keep copies of your answers; these will be helpful on the next assignment.

Day Two. Chapter 4, pages 144-152. This covers the paradoxes that plague Hamilton's method, and it covers the methods of Jefferson and John Quincy Adams (which suffer from problems of their own).

Problems: 13, 14, 17, 19, 23, 25, 30.

Day Three. Chapter 4, pages 152-159. This covers the method of Daniel Webster, the impossibility theorem of Balinski and Young, and the history of apportionment in the United States. There are also two appendices. You should certainly read Appendix 2 (page 174). Read Appendix 1 (pages 171-173) if you want to--it explains the method (slightly different from Webster's method) that is now actually used to apportion the United States House of Representatives.

Problems: 33, 35, 38, 47.

Test No. 2 (Chapters 3 and 4)

CHAPTER 5: EULER CIRCUITS

Day One. Read all of Chapter 5 quickly to get an overview, and then go back and read pages 179-186 carefully. Starting with the famous problem of the seven bridges of Königsberg, this covers the basic ideas of graph theory.

Problems: 1-9 odd.

Day Two. Chapter 5, pages 186-192. This covers the concepts and vocabulary of graph theory. It also covers Euler's theorems on the existence of Euler circuits and Euler paths.

Problems: 11, 13, 15, 23, 25, 63.

Day Three. Chapter 5, pages 192-201. This covers Fleury's algorithm, and also the process of ``Eulerizing'' a graph.

Problems: 30-44 even.

CHAPTER 6: TRAVELING SALESMAN PROBLEM

Day One. Read all of Chapter 6 quickly to get an overview, and then go back and read pages 221-230 carefully. This covers Hamilton circuits and Hamilton paths, weighted graphs, and complete graphs (weighted and unweighted). It also describes the famous traveling-salesman problem. If you find an efficient, optimal solution to this problem, then you have essentially solved the famous ``P versus NP'' Problem, and you will win \$1,000,000. For more details, see

Problems: 2, 4, 6, 7, 9, 11, 17, 19.

Day Two. Chapter 6, pages 231-239. This covers three algorithms for the traveling-salesman problem on a complete weighted graph, namely, the brute-force algorithm, the nearest-neighbor algorithm, and the repetitive nearest-neighbor algorithm.

Problems: 23, 25, 26, 29a, 32, 61.

Day Three. Chapter 6, pages 239-245. This covers the cheapest-link algorithm.

Problems: 38, 41, 62, 70.

Test No. 3 (Chapters 5 and 6)

CHAPTER 10: GROWTH

Day One. First read pages 393-411 of Chapter 10 quickly to get an overview. (You may skip Example 1 if you want to.) We will not study the last part of the chapter, on logistic growth. Then go back and read pages 393-395 (preliminaries) and pages 397-402 (linear growth) carefully. Especially note the recursive description (page 398; this is our transition rule), the explicit description (page 398), the graphing (page 400), and the summation formula (page 402).

Problems: 1, 3, 5, 9, 11, 14, 17. These are all due on Day Three, not Day Two. But you must attempt them all for Day Two.

Day Two. We will continue our study of linear growth (arithMETic sequences). In particular, we will examine difficulties you faced when you tried to do the problems assigned last time.

Day Three. Chapter 10, pages 403-411 (exponential growth). Especially note the recursive description (this is our transition rule), the explicit description, the graphing (all on page 405), the compounding rules (involving money) (pages 407-408), and the summation formula (page 409).

Problems: 19, 23, 25, 33, 35, 53 (alas!), 59, 61.

Day Four. We will continue our study of exponential growth (geometric sequences).

INFINITY AND IMPOSSIBILITY

We have seen statements (specifically, the theorems of Arrow and of Balinski and Young) alleging that it was impossible to do something or other. Should you believe such statements just because they're made by someone in authority? Of course not! The reason to believe a theorem is that someone has proved it. However, you probably haven't seen proofs before, and the proofs of the theorems above are too complicated for this course.

I want you to see an example of a historically important impossibility theorem whose proof is easy enough for you to understand. Once you have understood it, you will have a better idea of what it means for something to be proved, and what it means for something to be impossible. This is worth writing home about.

Problems: To be handed out. This subject is not covered in our textbook.

Test No. 4 (Chapter 10 and beyond)

CHAPTER 13: COLLECTING STATISTICAL DATA

Day One. Read How to Lie With Statistics, which is one of the best books ever. And it's short! Read all of Chapter 13 in Tannenbaum quickly to get an overview, and then go back and read pages 517-526 carefully. Pay special attention to the terms in boldface type and to the three case studies. (You might find the overview on page 535 helpful.)

Problems: 9-12, 13-16, 47.

Day Two. Chapter 13, pages 526-530.

Problems: 17-20, 24, 49, 50.

Day Three. Read pages 530-535. As you are reading, try to understand clearly how this part of the chapter differs from the earlier parts.

Problems: 33-36, 41-44.

CHAPTER 14: DESCRIPTIVE STATISTICS

Day One. Chapter 14 is a bit long, and contains many concepts. Even so, it is probably best to read all of the chapter quickly to get an overview of it. Then go back and carefully study this day's specific reading assignment, pages 549-558. This deals with graphical representations of data.

Problems: 1-4, 13, 14, 17, 19-22.

Day Two. Read pages 558-567. Here we study a few ``numerical summaries of data.'' The idea is to find just a few numbers to summarize a large data set so that we can understand the data without being overwhelmed by too many numbers. In particular, we will see the ``three M's'': mean, median, and mode. (The textbook mentions mode only in the exercises.)

Problems: 24, 34, 38, 45, 47, 51, 67, 69. Start looking at 71, 73, and 77, even though they won't be assigned until next time.

Day Three. Chapter 14, pages 567-571. We reserve this whole day for one concept (and, if necessary, for a little catch-up). That one concept is ``measures of spread.'' The reason for devoting a whole class session to it is so that we can make sure that everyone understands its meaning (which is important).

Problems: 56 (note that these data sets all have the same average; how do they differ?), 71, 73, 74, 77.

Test No. 5 on Chapters 13 and 14.