Discrete Math Final Exam Review

The following represent the types of MULTIPLE CHOICE questions that will be on your exam.

In questions 1-6, use the following preference schedule:

First ChoiceBDCAA

Second ChoiceCADDC

Third ChoiceACACD

Fourth ChoiceDBBBB

Number of votes151812316

  1. Who is the plurality winner?
  2. Who is the winner using the Borda Count Method?
  3. Who is the winner using the Sequential Pairwise Voting if the agenda is A, B, C, D?
  4. In the Hare system of voting, which candidate would you eliminate first?
  5. Who is the winner using the Hare system of voting?
  6. Using the Condorcet Method, who is the winner?

In questions 7-11, consider the following: In a group of 4 voters, A has 5 votes, B has 3 votes, C has 1 vote and D has 1 vote. In order for a bill to pass, it must receive ______votes.

  1. How many coalitions are possible?
  2. How many winning coalitions are possible?
  3. What is the power index for each voter?
  4. Name any dummies or dictators in this situation.

Four brothers (Abe, Ben, Cal, and Don) have inherited a house, a car, a yacht, a painting and $275,000 from an aunt that has recently passed away. They have each submitted their bids for the items (in the chart below).

Abe / Ben / Cal / Don
House / $300,000 / $215,000 / $195,000 / $175,000
Car / $29,000 / $24,500 / $25,000 / $27,500
Yacht / $120,000 / $139,000 / $129,000 / $125,000
Painting / $5,000 / $7,000 / $6,000 / $8,000
  1. Find the fair share for each child.
  2. Who received each item?
  3. What is each child’s Initial Cash?
  4. What is the Amount of Additional Cash for each of the brothers?
  5. What is the value of the Final Settlementfor each? (Include all cash and item(s).
  6. In a recurrence relation, . Given that, what is C8?
  7. Write a resource constraint for this situation: a lawn service company has 30 hours of worker time available. Mowing a lawn (x) takes 4 hours and trimming (y) takes 1.5 hours. The profit from mowing is $25 and the profit from trimming is $10.
  8. Write a profit formula for this mixture problem: Kim and Lynn produce tables and chairs. Each piece is assembled, sanded, and stained. A table requires two hours to assemble, three hours to sand, and three hours to stain. A chair requires four hours to assemble, two hours to sand, and three hours to stain. The profit earned on each table is $20 and on each chair is $42. Together Kim and Lynn spend at most 16 hours assembling, 10 hours sanding, and 13 hours staining.

Use the following Birth and Survival Rates:

Age (yrs) / 0-2 / 2-4 / 4-6 / 6-8 / 8-10 / 10-12
Birthrate / 0 / .4 / .9 / .8 / .5 / .1
Survival / .5 / .7 / .8 / .6 / .4 / 0

The Initial Population is .

  1. How many 2-4 year olds are there in this group after 3 cycles?
  2. What is the total population after 2 cycles?
  3. The Leslie Matrix for this population is what size?
  4. What is the growth rate of this population from cycle 1 to cycle 2?
  5. In a Leslie Matrix, what is placed on the super diagonal?

True/False

  1. The chromatic number of a graph is the minimum number of labels used to identify the vertices so that no two adjacent vertices have the same label.
  2. The total number of edges of a graph is equal to the sum of the degrees of the vertices.

Use the following graph:

Task / Time / Prerequisite
Start / 0 / None
A / 5 / None
B / 3 / A
C / 8 / A
D / 2 / B,C
E / 9 / B,C
F / 4 / B,C
G / 4 / B
H / 2 / G
I / 2 / D,E,F
J / 5 / I
Finish / H, J
  1. What is the Earliest Start Time for task I?
  2. What is the Minimum Project Time?
  3. What is the Critical Path?
  4. What is the Latest Start Time for task F?

Be able to determine whether the graphs are planar.

Be able to determine whether graphs are trees.

consider the following situation: A district has added a new school for grades 10-12. However, students who are zoned for the new school who are in the 11th or 12th grade may elect to remain at the former school. As a result, the new school consists of mostly sophomores. The student council has 10 seats to distribute among the classes. Below is a breakdown of student populations.

Class / Sophomore / Junior / Senior
Number of Students / 865 / 375 / 150
  1. What is the Ideal Ratio?

31. Assign seats using the Hamilton Method; the Hill Method, the JeffersonMethod.

use the following graph to answer the questions:

32. Name an Euler Circuit.

33. Name a Hamiltonian Path.

34. What is the chromatic number of the graph?

35. Find the Shortest Route of the following graph from A to I.

36. Using Kruskal’s Method, find the Minimum Spanning Tree.

37. Using Prim’s Method, find the Minimum Spanning Tree.

NON-MULTIPLE CHOICE

You will have problems related to each of the following topics:

Fair Division

Recurrence relation

Apportionment

Weighted voting

Northwest Corner Rule

Investing and Borrowing

Leslie Matrix

Linear Programming

Game Theory

Data Representation and Analysis