MTH110 Math Perspectives-Summer Session

TEXT: 

For All Practical Purposes, COMAP, 8th edition

OBJECTIVE:

The objective of this course is to introduce you to the ways in which mathematics impinges upon your daily lives.  You will be introduced to quantitative concepts and skills which will enable you to interpret and 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.

GOALS:

LAB SOLUTIONS:

ADDITIONAL MATERIAL:

EXAM REVIEWS:

HOMEWORK ASSIGNMENTS:

  1. Graphs, Euler Tours, Hamiltonian Tours, Minimum Cost Path: Chapter 1, Exercises 1, 5, 7, 11, 15, 23, 31, 35, 41, 45, 51; Chapter 2, Exercises 1, 3, 5a, 15, 17a,b, 19, 25, 27, 37, 41, 42a,b (answer given in class), 44, 46, 53, 57. Also, do the following problems:
    1. Find an Euler Circuit (starting at A) for the graph shown in Figure 1.10, pg. 10.
    2. Find an Euler Path for the graph in Figure 1.15a, pg. 14.   To answer this question, label the vertices with the letters A, B, C, etc. and then list the letters in the order that they lie on the path.
    3. In the graph shown below, color in the odd-valence vertices. Draw in dashed edges to show an optimal Eulerization of this graph
    4. 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.
    5. Read Exercise 24 and then answer the following question: If Jill always insists on wearing her green boots whenever she wears her green scarf, how many outfits might her friends see her in? HINT: Determine how many outfits she has when she wears a green scarf and how many outfits she has when she doesn't wear a green scarf. Then add these two values together to get your answer.
    6. Using the method of trees and starting at vertex A, determine the number of Hamilton Circuits in the graph below. Show your work.
    7. Find the minimum cost spanning trees for graphs (a) and (b) shown in problem 64 using Kruskal's algorithm and then Prim's algorithms (starting at X8 and B in the two graphs).  For both answers, list the edges in the order which they are added to the minimum cost spanning tree.

  2. Scheduling: Chapter 2, Exercise 71; Chapter 3, 5, 7, 14, 16(a,b,f), 19, 21, 22(a,b,e), 31, 37, 39, 41. Also, do the following problem:
    1. 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 70 in Chapter 2 (pg. 63) for a) 2 processors and b) 3 processors. For each, specify which measure is a more accurate estimate of the true optimal time.
    2. 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) two processors, b) three processors and c) four processors. Which, if any, of these three schedules can you be sure is optimal?

    3. Determine the critical path lengths for the vertices in the order-requirement digraph used in Problem B and create a priority list using those values. Repeat part a) of Problem B with this new list.

  3. Bin Packing, Graph Coloring: Chapter 3, 47, 49, 51, 55, 61, 69, 71, 73. Also, do the following problem:
    1. Assume we have to cut 30 pipes of the following lengths: 13, 15, 20, 12, 18, 20, 24, 4, 2, 9, 2, 22, 22, 28, 18, 2, 27, 9, 11, 27, 5, 5, 28, 8, 30, 23, 11, 7, 21, and 30. 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, worst fit, best fit, next-fit decreasing, first-fit decreasing, worst-fit decreasing and best-fit decreasing.

  4. Linear Programming: Chapter 4, Exercises 3, 11, 15, 21 (just show your algebra here to find the intersection point; you do not need to graph the equations), 23, 26, 33, 35, 37, 39, 45, 47.

  5. Please note the following:
    1. Always show your work when determining any corner point.
    2. For problems 33 through 39 be sure to list the profit formula and constraint equations, and to label all of the corner points of the feasible region.
    3. For problems 45 and 47, you need only list the profit formula and constraint equations (you cannot graph the feasible region nor easily apply the corner point principle for these problems).

  6. Assignment Problem:  Do the following problems:
    1. Solve the assignment problem for the following three matrices:
    2. 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 solution.

  7. Voting Systems: Chapter 9, Exercises 11, 13, 15, 17, 29, 35; Chapter 10, Exercise 12. Also, do the following problems:
    1. Determine if there are any Condorcet Winners in Exercises 10, 12, 14 and 16.
    2. Read the description of the Coombs procedure in Exercise 15, and apply it to the preference lists in Exercises 10, 12, 14 and 16.
    3. Apply the Plurality Runoff method to the preference lists in Exercises 10, 12, 14 and 16.
    4. Assume we use the preference lists in Exercise 10 in Chapter 9 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?
    5. 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: plurality, plurality runoff, Borda count, Hare and sequential pairwise with the agenda AEDBC.

  1. Weighted Voting Systems: Chapter 11, Exercises 3, 5, 9, 14, 15, and 17.  Also do the following problems:
    1. Determine the Shapley-Shubik indices for the weighted voting systems in Exercise 14.
    2. 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 BPI’s for this weighted voting system.  Which states would you say are the biggest winners in this system?  Which are the biggest losers?
    3. Suppose we wanted to create a 5-person basketball team using members of the class.  Determine the number of ways we could do this if
      1. we pick a particular person for each position (point guard, center, etc);
      2. we just pick five people who can play any of the positions.
    4. 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).
      1. Determine the number of possible 5 cards Euchre hands.
      2. Determine the number of possible full houses in a 5-card hand.
      3. Determine the number of possible flushes in a 5-card hand.
    5. 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? (To answer this last question, you should determine the power that 3 has for each quota).
    6. Repeat Problem F using the Shapley-Shubik Power Index.
    7. 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.
  1. Fair Division - Indivisible Objects: Chapter 13, Exercises 1, 3, 9, 11, 17, 19. Also, do the following problems:
    1. Solve problem 6 in the Skills Check section (pg. 426) completely (i.e., show the steps and the final results for a complete division of the items listed).
    2. Solve problem 8 in the Skills Check section (pg. 426) completely (i.e., show the steps and the final results for a complete division of the items listed).
    3. Four co-workers -Tessa, Alex, Abby and Sarah - 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. Anna values the foot massager at $24 and the mousepad at $10; Maggie values them at $36 and $12; Hennessey values them at $24 and $18; and Cassie values them at $28 and $8. Determine who gets which item, and how much money each co-worker either makes or spends.

  2.  Fair Division - Divisible Objects: Chapter 13, Exercise 27. Also, do the following problems:
    1. Use the last diminisher method to divide the cake shown in Exercise 27, assuming the order of cutting is Player 2, Player 3, then Player 1. Determine if any of the players is envious of another. (NOTE: for consistency, assume that the pieces are always cut from the left side of the cake).
    2. Read the description of the lone-chooser method in Exercise 29, then apply it to the cake shown in Exercise 27, 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.

  3. Apportionment: Chapter 14, Exercises 9, 11, 13, 15, 17, 21 and 23. Also, do the following problem:
    1. 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.
    2. 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:
      State
      Old Census
      New Census
      A
      6390
      6395
      B
      5890
      5890
      C
      2920
      3015
      D
      1389 1389
      Totals
      16589 16689
      Apportion the house using both the old and new census.  Explain how this is an example of the population paradox described on pages 440-441.
    3. 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 50 units 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 51 units and 52 units. (Can you figure out why the Three Bears scenario was used for this problem?)