Final Exam (Part II), Math 116, Winter 2008

Name ______

Final Exam (Part II), Math 116, Winter 2008

1. a) For the following election with four candidates, determine who wins using the Plurality with Elimination Method.

b) Rank the candidates with the Extended Plurality Method.

c) If an election is held among 15 candidates, what is the total number of pairwise comparisons?

2. a) In the weighted voting system [q: 24, 12, 8, 4, 2], what is the smallest value that q can be?

b) What is the largest value that q can be for the voting system in part a?

c) If a committee consists of six members (A, B, C, D, E, and F), and A has veto power while B, C, D and E have one vote each. (F is a non-voting member.) And if for a motion to pass, it must have the support of A plus at least two additional voting members, which of the following weighted voting systems could represent this situation?

i)  [6: 5, 1, 1, 1, 1, 0]

ii)  [4: 2, 1, 1, 1, 1, 0]

iii)  [5: 3, 1, 1, 1, 1, 0]

iv)  [6: 3, 1, 1, 1, 1, 0]

v)  None of the above

d) In any weighted voting system with N players, what is the minimum number of coalitions possible? (Hint: Banzhaf’s)

3. A bus company operates four bus routes (A, B, C, and D) and 50 buses. The buses are apportioned among the routes on the basis of average number of daily passengers, which is given in the following table.

a) Find the standard divisor.

b) Which of the following standard divisors are likely to work for Jefferson’s method?

i) 480

ii) 500

iii)495

iv) 520

c) Find the final apportionment under Jefferson’s Method.

4. Consider the apportionment problem shown in the tables below.

a)  This problem is an example of which paradox (or none)? Clearly indicate which parts of the chart above lead you to this conclusion or otherwise justify your answer.

b)  What does Balinksi & Young’s Impossibility Theorem say?

5. a) For the graph below, eulerize the graph and clearly label an Euler circuit around the graph by numbering the edges, starting and ending at C.

b) For the complete graph K12,

i) How many edges are there in the graph?

ii) How many Hamilton circuits are there in the graph?

c)  For the following graph, determine if it satisfies Dirac’s Theorem.

6. A school teacher has the summer off and has decided to visit her relatives in five different cities. Naturally, money is tight, so she’d like to find the cheapest route. Use the Cheapest Link Algorithm and the graph below to find her route. Write your final answer starting in Columbus and give the weight of the circuit.

7. a) List the three properties of a tree.

i)

ii)

iii)

b) What is the number of vertices in a tree with 49 edges?

c) How many spanning trees does the following graph have?

8. a) Use the weighted graph below to find the minimum spanning tree using Kruskal’s Algorithm. Clearly label the tree on the graph.

b) Give the weight of the minimum spanning tree.

c) Kruskal’s Algorithm is OPTIMAL/NON-OPTIMAL, EFFICIENT/INEFFICIENT, APPROXIMANT. Circle all that applies.

9. a) If the shortest network connecting a set of points is not the minimum spanning tree, what is it called?

b) What is the number of Steiner Points in a shortest network connecting three cities?

c) What is the degree of every Steiner Point?

10. a) Find the sum of if there are exactly 100 terms in the sum.

b) How much does $874 grow to in 4 years if left in a savings account that pays 10.7% interest compounded annually?

c) How much does $575.75 grow to in five years if left in a savings account that pays 12% compounded monthly?

d) Assume there is a certain population of fish in a pond whose growth is described by the logistic equation. The growth parameter of this type of fish is r=3.0. If the starting population is given by p0 = 0.2, then after one breeding season, what is the population in the pond?

11. a) A pair of honest dice is rolled and the number on each side is noted. What is the probability of rolling a total of 2?

b) A computer password consists of any five capital letters from the ordinary English alphabet. How many different combinations are possible?

c) A Tasmanian lottery ticket consists of choosing 7 different numbers between 1 and 56. How many possible lottery tickets are there? You may report your answer in permutation or combination notation.

d) Two cards are drawn in order from a well-shuffled deck of 52 cards. What is the probability that both cards are hearts?

e) If the chances of rain tomorrow are 30%, then what are the ODDS of rain tomorrow?