For All Practical Purposes, COMAP, 9th
The objective of this course is to introduce you
to the ways
in which mathematics impinges upon your daily lives. You will be
to quantitative concepts and skills which will enable you to interpret
reason with quantitative information. In addition you will be
able to see
how mathematics can be used to model many different types of real-world
situations, from presidential elections to garbage collection.
- learn the
mathematical principals behind the decision making processes within
groups (social choice).
- learn the
mathematics underlying various types of optimization problem
- learn how
mathematics can aid in the allocation of resources in a equitable way
- Homework 1 Chapter 1, Exercises 4, 12a,b, 18,28, 34 (just do Fig 1.17a), 38 (you need only list a sequence of vertices for each graph), 40, 42, 46, 52, 56, 60. Also, do the following problems:
- Find an Euler Circuit (starting at
A) for the graph shown in Figure 1.10, pg. 12.
- In the graph shown below, color in the odd-valence vertices. Draw in
dashed edges to show an optimal Eulerization of this graph. Specify the minimum number of repeated edges that would be used when solving the Chinese Postman Problem with this graph.
- A complete n-graph is a
graph with n vertices where each vertex is connected to every other
vertex. The figure below shows complete graphs for n = 3, 4 and 5.
Which of these graphs have Euler Circuits? What conditions on n will guarantee that a
complete n-graph will or will not have an Euler Circuit? Explain your answer.
DUE: Jan. 26
- Homework 2: Chapter 2, Exercises 4 (list the vertices for each circuit
that exists), 10 (just do part (a) for both graphs), 18b (just answer the question above the 3x4 grid), 20, 34, 36a,
40 (show your work using the method of trees), 46a,b, 48, 50 (change the value of the edge from C to E from 23 to 2), 56, 60. For Exercises 46, 48 and 50 be sure to specify both the Hamilton circuits and the cost of those circuits. Also, do
the following problems:
- For each of the graphs in Exercise 15, add one edge so that a Hamiltonian Circuit exists on the graph and list the circuit.
- In Exercise 34, suppose the cuostomer will order pie, but never with either of three meat entrees. How many meals can she order now? HINT: Determine how many meals she can order when she picks a meat entree and how many meals she can order with a different entree. Then add these two values together to get your answer.
- Using the method of trees and starting at vertex A, determine the number of Hamilton Circuits in the graph below. Show your work.
- Use Kruskal's algorithm to determine a minimum cost spanning tree for the graph shown in Exercise 50 (use the same edge modification described above). Show the final tree, the minimum cost and the order that the edges were added to the tree.
- Repeat the above problem, but now use Prim's algorithm starting at vertex B.
DUE: Feb. 2
- Homework 3: Chapter 3,
6, 10a, 14, 18(a,b,f), 22(a,b,c), 24(a,b), 26(a,b,e). Also,
do the following problem:
- Using the order requirement digraph in Exercise 6, determine a schedule for three processors using the priority list T1, T2, ..., T7. Is the resulting schedule optimal?
- We discussed two measures of optimality for the list scheduling problem:
the length of the critical path, and the total time of all tasks divided by the number
of processors. Apply these measures to the order-requirement digraphs in Exercise
75 in Chapter 2 (pg. 71 ) for a) 2 processors and b) 3 processors. For each, specify which measure is
a more accurate estimate of the true optimal time.
- Use the list processing algorithm and the order-requirement digraph shown below to schedule the tasks
with the priority list T1, T2, ..., T10 using a) 2 processors, b)
3 processors and c) 4 processors. Which, if any, of these three
schedules can you be sure is optimal?
- Determine the critical path lengths for the vertices in the order-requirement digraph used in Problem C and create a priority list using those values. Repeat part a) of Problem C with this new list.
- Consider the order requirement digraph shown below which is a modification of one we looked at in class. It turns out that it is
impossible to construct an optimal schedule for two processors unless we allow processors to be voluntarily
idle! Determine what the optimal time would be for two processors and construct an optimal schedule where we allow one or more of the processors to be voluntarily idle.
DUE: Feb. 9
- Homework 4: Chapter 3, 36, 42(a,b,c), 46, 52, 54, 58, 66(c,d).
Also, do the following problem:
Assume we have to cut 30 pipes of the
following lengths: 22, 1, 24, 26, 27, 14, 8, 27, 7, 17, 16,
11, 16, 23, 11, 21, 27, 29, 14, 3, 8, 14, 12, 16, 26,
6, 15, 30, 11, and 29. If pipes only come in lengths
of 40 determine how many pipes would be needed if we used each
of the following algorithms: next fit, first fit, best
fit, next-fit decreasing, first-fit decreasing, and best-fit decreasing.
The two measures for optimality in scheduling problems - critical path length and total task time divided by the number of processors - still applies to independent task scheduling. Find a set of 3 independent tasks which can NOT be scheduled in the optimal time indicated by either of these two measures.
For all problems no credit
will be given for a simple numerical answer (min number
of bins, min time to schedule a set of tasks, etc.); you must
show your work (for example, show how the bins are filled,
or how the tasks are scheduled).
DUE: Feb. 16
- Homework 5: Chapter 3, 74(a,b), 76, 78 (be sure to show the graph you used to solve this problem), 80, 86. For Exercise 86 you'll need to read about the Four Color Theorem on page 96 in the text. Also, use only graphs (a), (c), (d) and (h) for this problem and try to find the minimum number of colors necessary. Finally, do the following problems:
- Solve the assignment problem for the following three matrices. Be sure to show all the steps involved.
- Another method to solve the assignment problem is to use the
following "greedy" approach: Find the smallest
value in the matrix and include that in the assignment, crossing out
all other numbers in that value's row and column.
You then apply the same procedure to the remaining uncrossed-out
values, and so on. Use this method on matrix 1) above
and show that this method is not guaranteed to find the optimal
DUE: Mar. 7
- Homework 6: Chapter 9
Exercises 14, 16, 18, 20, 32, 42(a,b); Chapter 10, Exercise 12, 16. Also, do the following problems (NOTE: all reference to Exercises below refer to exercises in Chapter 9):
- Determine if there are any Condorcet
Winners in Exercises 14, 16, 18 and 20.
- Read the description of the Coombs
procedure in Exercise 21, and apply it to the preference lists in
Exercises 14, 16, 18 and 20.
- Apply the Plurality Runoff method to
the preference lists in Exercises 14, 16, 18 and 20.
- Assume we use the preference lists
in Exercise 14 and are using approval voting. Who wins if
everyone votes for their top two favorite candidates? Who wins if
everyone votes for their top three favorite candidates?
- Assume we have an election with 5 candidates and 11 voters with the preference lists shown below. Determine the winner if the following methods are used: a) plurality, b) plurality runoff, c) Borda count, d) Hare, e) sequential pairwise with the agenda DEACB, and f) approval voting where every voter voted for their top three candidates.
DUE: Mar. 23
- Weighted Voting Systems:
Exercises 4, 14, and 18 . For Exercise 14 just determine the BPI for the given weighted voting system. Also do the following problems (be sure to show your work for all of these problems):
- The current # of representatives for
the New England states are as follows: Connecticut - 5, Maine - 2, Massachusetts - 9, New Hampshire - 2, Rhode Island - 2, and Vermont - 1. Suppose
they all got together to vote on new-englandy
type matters, and decided that the quota to pass any measure would be
18 (we assume all voters from any state always vote together). Determine the BPIs for this weighted voting
system. Which states would you say are the
biggest winners in this system? Which are
the biggest losers?
- Calculate the Shapley-Shubik power indices for the weighted voting system in Exercise 7 but instead of using the given quota of 51 use a quote of 54. Repeat with a quota of 70 and with a quota of 75.
- Determine the Shapley-Shubik power indices
for the weighted voting systems in Exercise 14 .
- Suppose we wanted to create a
5-person basketball team using members of our class (which currently totals to 18 students). Determine the
number of ways we could do this if
Notice that in part a. the order that we pick people matters while in part b. order does not matter.
- we pick a particular person for
each position (point guard, center, etc);
- we just pick five people who can play any of the
- Euchre is a card game played with a
deck of 24 cards divided into 4 suits (clubs, diamonds, hearts and
spades) each containing 6 cards (the A, K, Q, J, 10 and 9).
- Determine the number of possible 5
cards Euchre hands.
- Determine the number of possible
full houses in a 5-card hand.
- Determine the number of possible
flushes in a 5-card hand.
- Use the techniques discussed in
class to determine the Banzhaf power indices for the following weighted
voting system: [9: 3, 2, 2, 2, 2, 2, 2].
Repeat with a quota of 10 and 11. For
which of these quotas does the voter with weight 3 have the most power?
- Determine the Banzhaf power indices
for the following weighted voting system: [16: 5, 5, 5, 4, 4, 4, 4]. Repeat with a quota of 17.
DUE: Apr. 10
- Fair Division : Chapter 13,
Exercises 2, 4, 10, 14, 18, 20, 30 and 32. Also, do the following problems:
- Solve problem 10 in the Skills Check section (pg. 475) completely (i.e., show the steps and the final results for a complete division of the items listed).
- Solve problem 14 in the Skills Check section (pg. 475) completely (i.e., show the steps and the final results for a complete division of the items listed).
- Read the description of the lone-chooser method in Exercise 33, then apply it to the cake shown in Exercise 31, where Player 1 is Bob, Player 2 is Carol and Player 3 is Ted, and Bob divides the cake initially. Determine if any of the three are envious after the cake has been divided up.
- Four co-workers - Tessa, Noelle, Natalie and Lizzie - have
decided to use the Knaster Inheritance method to decide who gets two
highly prized items at
the office: an electric foot massager and a mousepad with a picture of
Elvis on it. Tessa values the foot massager at
$24 and the mousepad at $10; Noelle values them at $36 and $12;
Natalie values them at $24 and $18; and Lizzie values them
at $28 and $8. Determine who gets which item, and how much money each
co-worker either makes or spends.
- Suppose Tess, Noelle, Natalie and Lizzie decided to hold a Vickrey auction for each of the items listed in Problem D (Vickrey auctions are described in Section 13.8 of our text). Assuming they all bid honestly (i.e., bid what they thought the items were worth) determine who would win each item and how much they would pay.
- Ruby and Opal have six bags of precious gems that they need to divide between them. They decide to use the Adjusted Winner procedure and have distributed their 100 points as follows:
If there are 100 of each gem, specify the number of each gem that Ruby and Opal get.
Suppose that instead of using the Adjusted Winner procedure in the precious problem, Ruby and Opal decide to take turns, with Ruby going first. Determine which gems each gets if neither knows the others preferences. Repeat the procedure assuming they now know each other's preferences (based on the values they would have used in the Adjusted Winner procedure). Who was able to take advantage of knowing the other's preferences?
DUE: Apr. 28
- Apportionment: Chapter 14, Exercises 8, 10, 18, 20 and 30. Also, do the following problems:
- Five people have pooled their financial resources to start a small company. The amount of money put in by each person is $56,000, $41,000, $25,000, $15,000 and $4,000. In order to decide on company policies they decide to create a weighted voting system by dividing 100 votes between them based on the amount that they originally contributed. Determine how the 100 votes should be divided using the Hamilton, Jefferson and Webster methods.
A country has four states, A, B, C and D. Its house of
representatives has 100 members, apportioned by the Hamilton
method. A new census is taken, and the house is
reapportioned. Here are the data:
Apportion the house using both the old and new census. Explain
how this is an example of the population paradox described on pages 495-497 in the textbook.
- The ThreeBears Corporation has four stock holders: Mama Bear, who owns 971 shares;
Papa Bear, who owns 807 shares; Baby Bear, who owns 510 shares; and Goldilocks, who
owns 315 shares. At the end of year they have 79 bowls of porridge as dividends to
be distributed to the four stock holders. Use the Webster method to come up with
a fair apportionment of the porridge. Repeat this procedure for 80 bowls and 81 bowls.
(Can you figure out why the Three Bears scenario was used for this problem?)
Do Exercise 15 in the book but instead of the Hamilton method, use the Jefferson method, the Webster method and the Hill Huntington method on each of the house sizes.
DUE: May 4