MTH110 Math Perspectives

Spring 2017

TEXT: 

For All Practical Purposes, COMAP, 9th 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. 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:
    1. Find an Euler Circuit (starting at A) for the graph shown in Figure 1.10, pg. 12.
    2. 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.
    3. 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

  2. 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:
    1. For each of the graphs in Exercise 15, add one edge so that a Hamiltonian Circuit exists on the graph and list the circuit.
    2. 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.
    3. Using the method of trees and starting at vertex A, determine the number of Hamilton Circuits in the graph below. Show your work.
    4. 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.
    5. Repeat the above problem, but now use Prim's algorithm starting at vertex B.

    DUE: Feb. 2

  3. 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:
    1. 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?
    2. 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.
    3. 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?

    4. 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.
    5. 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

  4. Homework 4: Chapter 3, 36, 42(a,b,c), 46, 52, 54, 58, 66(c,d). Also, do the following problem:
    1. 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.
    2. 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

  5. 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:
    1. Solve the assignment problem for the following three matrices. Be sure to show all the steps involved.
    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.

    DUE: Mar. 7

  6. 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):
    1. Determine if there are any Condorcet Winners in Exercises 14, 16, 18 and 20.
    2. Read the description of the Coombs procedure in Exercise 21, and apply it to the preference lists in Exercises 14, 16, 18 and 20.
    3. Apply the Plurality Runoff method to the preference lists in Exercises 14, 16, 18 and 20.
    4. 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?
    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: 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

  7. Weighted Voting Systems: Chapter 11, 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):
    1. 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?
    2. 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.
    3. Determine the Shapley-Shubik power indices for the weighted voting systems in Exercise 14 .
    4. 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
      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.
      Notice that in part a. the order that we pick people matters while in part b. order does not matter.
    5. 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.
    6. 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?
    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.

    DUE: Apr. 10

  8. Fair Division : Chapter 13, Exercises 2, 4, 10, 14, 18, 20, 30 and 32. Also, do the following problems:
    1. 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).
    2. 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).
    3. 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.
    4. 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.
    5. 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.
    6. 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:
       AmethystsDiamondsEmeraldsGarnetsSapphiresTopaz
      Ruby75023371
      Opal640301203
      If there are 100 of each gem, specify the number of each gem that Ruby and Opal get.
    7. 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


  9. Apportionment: Chapter 14, Exercises 8, 10, 18, 20 and 30. Also, do the following problems:
    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 495-497 in the textbook.
    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 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?)
    4. 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