Discrete Honors Semester 1 Exam Review Guide: Chapters 1 – 7



Multiple Choice Practice Problems CHAPTER 4 - APPORTIONMENT:

For questions 1 - 4: 4 states and 50 seats. The population of each state is provided.

|State |A |B |C |D |

|Population |3194 |9066 |4548 |8192 |

1) The standard divisor is

A) 250 B) 500

C) 5000 D) 25000

E) None of above

2) The standard quota (two decimal) for State A is

A) 6.39 B) 7.14

C) 12.78 D) 63.88

E) None of above

3) Which modified divisor works for Adam’s method?

A) 500 B) 505

C) 510 D) 515

E) None of the Above

4) Who gets the surplus in Hamilton’s method?

A) State A B) State B

C) State C D) State D

E) None of the Above

5) Under a certain apportionment method, state X has a standard quota of 48.9 and receives 47 seats in the final apportionment. This is called

A) an upper quota violation B) the Alabama paradox. C) the population paradox.

D) the new states paradox. E) a lower quota violation.

6) State Y received 100 seats under a certain apportionment method. 1 more seat was added to the legislature and then under the same apportionment method Y received 99 seats. This is called

A) an upper quota violation B) the Alabama paradox. C) the population paradox.

D) the new states paradox. E) a lower quota violation.

For questions 7 - 8: A small airline operates 5 flights (NY, BOS, DC, PHI, ATL) to major cities on the east coast. There are only 20 airplanes that the airline owns. The airplanes are apportioned among the flights on the basis of average profit per flight.

7) Which of the following best represents the key terms of an apportionment

(States; Populations; Seats) to the word problem?

A) Flights; Average Profit; Airplanes

B) Airplanes; Flights; Average Profit

C) Flights; Airplanes; Average Profit

D) Average Profit; Flights; Airplanes

E) Airplanes; Average Profit; Flights;

8) Which of following will the standard divisor represent?

A) Flights per Airplane

B) Airplanes per Flight

C) Airplanes per Average Profit

D) Flights per Average Profit

E) Average Profit per Airplane

Hon Discrete CHAPTER FOUR REVIEW: SOLUTIONS

Identify the states, populations, seats, and what would the standard divisor represents:

1. Mr. Smith is planning to give candy to students based on the numerical value of their quarter grades.

Standard Divisor = grade point per 1 piece of candy States = students

Populations = quarter grades Seats = candy

2. WSFCS has seen a rise in students and is planning to hire 100 new teachers for either elementary, middle, and high schools. WSFCS plans to apportion the teachers based on the number of students each school level.

Standard Divisor = students per 1 teacher States = Schools

Populations = Number of Students Seats = New Teachers

3. The subway has 5 main subway lines (Green, Red, Yellow, Orange, and Blue) and the city is considering a more efficient way to organize public transportation. The plan is to re-distribute the 60 subway trains to the different lines based on the amount of profit that each line is currently making the city.

Standard Divisor = Profit per 1 train States = Subway Lines

Populations = Profit Seats =Subway Trains

STANDARD PRACTICE PROBLEMS:

1) Find apportionment according to Hamilton’s, Jefferson’s, Adam’s, and Webster’s.

|State |A |B |C |200 SEATS |

|Population |4400 |8300 |10,300 | |

|Standard Quotas |38.26 |72.17 |89.57 |Standard Divisor = 115 |

|Hamilton’s |38 |72 |90 | |

|Jefferson’s |38 |72 |90 |Modified Divisor = 114.4 – 113.7 |

|Adam’s |39 |72 |89 |Modified Divisor = 115.731 - 15.789 |

|Webster’s |38 |72 |90 |Modified Divisor = 115 |

2) Find apportionment according to Hamilton’s, Jefferson’s, Adam’s, and Webster’s.

|State |A |B |C |D |E |200 SEATS |

|Population |4400 |8300 |5300 |9700 |10,300 | |

|Standard Quotas |23.16 |43.68 |27.89 |51.05 |54.21 |Standard Divisor =190 |

|Hamilton’s |23 |44 |28 |51 |54 | |

|Jefferson’s |23 |44 |28 |51 |54 |Modified Divisor = |

| | | | | | |188.6 – 187.3 |

|Adam’s |23 |44 |28 |51 |54 |Modified Divisor = |

| | | | | | |191.4 - 193 |

|Webster’s |23 |44 |28 |31 |54 |Modified Divisor = 190 |

3) Find apportionment according to Hamilton’s, Jefferson’s, Adam’s, and Webster’s.

|State |A |B |C |D |E |150 SEATS |

|Population |1700 |2300 |3100 |2700 |1900 | |

|Standard Quotas |21.79 |29.49 |39.74 |34.62 |24.36 |Standard Divisor = 78 |

|Hamilton’s |22 |29 |40 |35 |24 | |

|Jefferson’s |22 |29 |40 |35 |24 |Modified Divisor = |

| | | | | | |77.1-76.7 |

|Adam’s |22 |29 |40 |35 |24 |Modified Divisor = |

| | | | | | |79.32 - 79.41 |

|Webster’s |22 |29 |40 |35 |24 |Modified Divisor = 78 |

WORD PROBLEMS:

1) The 6 main departments at a local college need to split the 50 scholarships that the university offers to give to incoming freshmen. The admission department decides to assign scholarships to the departments based on their current number of majors which is given in the table below.

|Political Science |History |Math |Science |English |Foreign Language |

|112 |78 |45 |57 |68 |60 |

a. Identify the seats, populations, and states in this problem.

STATES = DEPARTMENTS, SEATS = SCHOLARSHIPS, POPULATIONS = Current Majors

b. What is the standard divisor? 420/50 =8.4

c. What does the standard divisor represent in this problem? (Hint: Use part a answers)

8.4 Currents Majors per 1 Scholarship to a department

d. What is the standard quota for each state?

|Political Science |History |Math |Science |English |Foreign Language |

|112/8.4 = 13.33 |78/8.4 = 9.29 |45/8.4 = 5.36 |57/8.4 = 6.79 |68/8.4 = 8.10 |60/8.4 = 7.14 |

e. What is the lower quota for each state?

|13 |9 |5 |6 |8 |7 |

f. What is the upper quota for each state?

|14 |10 |6 |7 |9 |8 |

g. What are HAMILTON’S AND JEFFERSON’S APPORTIONMENT to this problem?

HAMILTON’s Method:

|13 |9 |5 + 1 = 6 |6 + 1 = 7 |8 |7 |

Jefferson’s Method: Divisor = 7.81 – 8

|14 |9 |5 |7 |8 |7 |

2) There are 5 main interstates in a state. The state legislature plans to assign work crews to the 5 main interstates based on the average number of cars on the interstate each day. The interstates combined have an average of 231000 cars each day. The STANDARD QUOTA for each interstate is given in the table below.

|Interstate 1 |Interstate 40 |Interstate 85 |Interstate 485 |Interstate 77 |

|165.4 |220.7 |285.4 |180.9 |197.6 |

a. Identify the seats, populations, and states in this problem.

STATES = INTERSTATES, SEATS = WORK CREWS, POPULATIONS = Car Traffic

b. What is the standard divisor? 231,000/1050 = 220

c. What does the standard divisor represent in this problem? (Hint: Use part a answers)

220 Number of Cars per 1 Work Crew

d. What is the average number of cars for each interstate?

|165.4*220 = 36388 |220.7*220 =48554 |285.4*220 =62788 |180.9*220 =39798 |197.6*220 =43472 |

e. How many work crews are there in the entire state?

1050 workers = sum of standard quotas

f. What is the lower quota for each interstate?

|165 |220 |285 |180 |197 |

g. What is the upper quota for each interstate?

|166 |221 |286 |181 |198 |

h. What are WEBSTER’S AND ADAM’S APPORTIONMENT to this problem?

Websters’s Method: Divisor = Standard Divisor 220 Already works

|165 |221 |285 |181 |198 |

Adam’s Method: Divisor = 220.54 - 220.67

|165 |221 |285 |181 |198 |

Multiple Choice Practice Problems CHAPTER 5 - EULER CIRCUITS:

For questions #1 - 3 refer to Figure #1.

1) Which of the following is NOT a circuit in the graph?

A) C, C B) A, B, F, E, A

C) B, D, C, B D) F, D, C, C, B, E, F

E) None of the Above

2) Which of the following is NOT a path in the graph?

A) F, E, B, A, E, F, D B) F, B, C, C, D

C) F, E, A, B, F, D D) F, D, E, A, B, F, C, D

E) None of the Above

3) Which one of the following statements is NOT true about this graph?

A) There is a circuit starting and ending at E.

B) There are multiple edges.

C) It is a connected graph.

D) A loop exists.

E) None of the above.

For questions # 4 – 6 refer to the four graphs in Figure #2.

| | | | |

| | | | |

| | | | |

| | | | |

| | | | |

|Graph #1 |Graph #2 |Graph #3 |Graph #4 |

FIGURE #2

4) Which graph(s) have an Euler Circuit?

A) Graph #1 B) Graph #2 C) Graph #3 D) Graph #4 E) Graph #2 + #3

5) Which graph(s) have components?

A) Graph #1 B) Graph #2 C) Graph #3 D) Graph #4 E) None

6) Which graph(s) have an Euler Path?

A) Graph #1 B) Graph #2 C) Graph #4 D) Graph #1 + #4 E) Graph #2 + #4

For #7 - 9: Use Figure #3

7) Which of the following is a bridge in the graph?

A) AB B) AF C) DG D) CG E) DD

8) Which of the following is not a multiple edge?

A) AB B) CG C) GD D) CE E) NONE

9) Which is not the correct degree statement?

A) A = 3 B) C = 2 C) D = 4 D) F = 3 E) G = 6

HONORS DISCRETE REVIEW CHAPTER FIVE: SOLUTIONS

#1: In each graph:

a) Find the Edge Set

b) Identify any multiple edge

c) Identify any loops

d) Identify any bridges

e) Find the degree of each vertex

#2: If possible, draw each of the following graphs.

1) The graph has 3 bridges and 4 vertices.

2) The graph has 4 odd vertices and 2 even vertices.

3) Disconnected in which each component has a bridge.

4) Has at least 3 multiple edges, 2 loops, 5 vertices, and 10 total edges.

5) Disconnected graph with 2 even vertices and 3 odd vertices.

NOT POSSIBLE TO DRAW BECAUSE YOU CAN’T HAVE AN ODD NUMBER OF ODD VERTICES

6) Euler Path and odd vertices are not adjacent.

#3: For each of the following graphs

|Components: ABED and CF |Components: None |Components: None |

|Circuit: A, B, D, E, A |Circuit: A, D, B, A |Circuit: A, D, E, A |

|Path: Not possible |Path: A, B, F |Path: A, D, C, F |

#4: Does the Graph have an Euler Path, Euler Circuit, or Neither?

a) Determine by degree of vertices if an Euler Circuit or Path Exists a

b) If one exists, then find it from a starting vertex.

#5: For the below graph,

a) Find a circuit of length 1

II

b) Find a circuit of length 4

DFGHD

c) Find a circuit of length 5

EDFHDE

d) Find a circuit of length 6

EDFGHDE

e) Find a path of length 3

BACD

f) Find a path of length 8

IIHGFDCAB

g) Find a path of length 11

CBACDEDFGHDE

Multiple Choice Practice Problems CHAPTER 6 - HAMILTON CIRCUITS:

1) The number of edges in K25 is

A) 24 B) 25 C) 276 D) 300 E) 325

2) The number of Hamilton Circuits in K16 is

A) 15 B) 120 C) 15! D) 16! E) 17!

3) If a complete graph has degree 8 for each vertex, then how many edges are in the graph?

A) 36 B) 8! C) 9! D) 8 E) 9

4) A complete graph has 465 edges. How many vertices does the graph have?

A) 29 B) 30 C) 31 D) 107,880 E) 108,345

5) A complete graph has 40,320 distinct Hamilton’s circuits. How many vertices are there?

A) 6 B) 7 C) 8 D) 9 E) 10

6) The graph in Figure #1 …

A) has no Hamilton circuit.

B) has a single Hamilton circuit (and its mirror-image circuit).

C) has multiple Hamilton circuits, none contain the edge BD.

D) has multiple Hamilton circuits, all contain the edge BE.

E) none of the above

For questions 7 - 9 refer figure #2:

7) The Nearest Neighbor Algorithm applied to the graph finds the solution:

A) D, C, A, B, E, D

B) D, E, A, B, C, D

C) D, A, B, E, C, D

D) D, B, E, C, A, D

E) none of the above

8) The Cheapest Link Algorithm applied to the graph finds the solution:

A) D, C, A, B, E, D

B) D, E, A, B, C, D

C) D, A, B, E, C, D

D) D, B, E, C, A, D

E) none of the above

9) How many different Hamilton circuits would we have to find to use the Brute Force Algorithm starting at D?

A) 4

B) 5

C) 10

D) 24

E) 120

HONORS DISCRETE CHAPTER SIX REVIEW: SOLUTIONS

#1: For each of the following situations: Be able to find how many vertices, edges, degree of vertex, and number of distinct circuits exist in the complete graph.

1) 12 vertices

Edges: 66

Degree: 11

Distinct Circuits: 11!

2) degree of each vertex is 5

Vertices: 6

Edges: 15

Distinct Circuits: 5!

3) 18 vertices

Edges: 123

Degree: 17

Distinct Circuits: 17!

4) 21edges

Vertices: 7

Degree: 6

Distinct Circuits: 6!

5) Distinct Hamilton circuits = 720

Vertices: 7

Edges: 21

Degree: 6

6) 4 vertices

Edges: 6

Degree: 3

Distinct Circuits: 3!

7) 78 edges

Vertices: 13

Degree: 12

Distinct Circuits: 12!

#2: Determine if the graph has a Hamilton Path and/or circuit. If so, find one.

|H. Circuit: A, B, F, C, E, D, A |H. Circuit: A, C, B, F, E, D, A |H. Circuit: Not Possible |

|H. Path: A, B, F, C, E, D |H. Path: A, C, B, F, E, D |H. Path: E, D, A, C, B, F |

#3:For the weighted complete graphs/tables below: find the shortest Hamilton circuit for

|#1 |A |B |C |D |E |F |

|B |$9 | |$5 |$15 |$8 |$12 |

|C |$13 |$5 | |$18 |$11 |$17 |

|D |$7 |$15 |$18 | |$3 |$5 |

|E |$4 |$8 |$11 |$3 | |$2 |

|F |$6 |$12 |$17 |$5 |$2 | |

|#2 |A |B |C |D |E |

|B |19 | |26 |13 |21 |

|C |27 |26 | |35 |31 |

|D |33 |13 |35 | |18 |

|E |25 |21 |31 |18 | |

GRAPH #3:

GRAPH #4:

-----------------------

FIGURE #1

A

B

C

D

E

F

A

B

C

D

E

F

G

FIGURE #3

Edge Set: AB, AD, AE, BC, BD, BE, CD, DE

Multiple Edges: None

Loops: None

Bridges: None

A =3

B = 4

Graph #1

C= 2

E = 3

D = 4

Graph #2

E = 2

I = 3

D = 2

F = 2

A = 3

H = 4

C = 2

B = 3

G = 3

Graph #3

A = 3

C = 3

B = 4

D = 2

E = 2

Edge Set: AI, AI, AB, BI, BC, CH, HH, HG, GD, GE, DF, EF

Multiple Edges: AI

Loops: HH Bridges: BC, CH, HG

Edge Set:AA, AB, BC, BC, BE, CD, DE

Multiple Edges: BC

Loops: AA Bridges: AB

A

B

C

D

E

F

A

B

C

D

E

F

A

B

C

D

E

F

Graph #3

Graph #2

Graph #1

Graph #5: EC

Graph #6: EC

Graph #7: EP

Graph #4: Neither

Graph #3: EC

Graph #2: EC

Graph #1: EP

A

B

C

D

E

F

G

H

I

C

B

A

G

D

E

F

FIGURE #1

A

B

C

D

E

1

10

6

3

5

18

23

13

28

8

FIGURE #2

A

B

C

D

E

F

A

B

C

D

E

F

A

B

C

D

E

F

Graph #3

Graph #2

Graph #1

|Table #1 |

|Nearest Neighbor: A, E, F, D, B, C, A = 44 |

|Repetitive Nearest Neighbor: |

|A, E, F, D, B, C, A = 44 |

|B, C, E, F, D, A, B = 39*** |

|C, B, E, F, D, A, C = 40 |

|D, E, F, A, B, C, D = 43 |

|E, F, D, A, B, C, E = 39*** |

|F, E, D, A, B, C, F = 43 |

| |

|Solutions: A, B, C, E, F, D, A |

|A, D, F, E, C, B, A |

|Cheapest Link: A, B, C, D, E, F, A = 43 |

|Brute Force: 5! = 120 circuits |

|Table #2 |

|Nearest Neighbor: A, B, D, E, C, A = 108 |

|Repetitive Nearest Neighbor: |

|A, B, D, E, C, A = 108*** |

|B, D, E, A, C, B = 109 |

|C, B, D, E, A ,C = 109 |

|D, B, A, E, C, D = 123 |

|E, D, B, A, C, E = 108*** |

|Solutions: A, C, E, D, B, A |

|A, B, D, E, C, A |

|Cheapest Link: A, B, D, E, C, A = 108 |

|Brute Force: 4! = 24 circuits |

|Graph #3 |

|Nearest Neighbor: A, B, D, C, E, A = 280.9 |

|Repetitive Nearest Neighbor: |

|A, B, D, C, E, A = 280.9 |

|B, E, C, D, A, B = 275.1 *** |

|C, D, A, B, E, C = 275.1*** |

|D, C, E, B, A, D = 275.1 *** |

|E, B, A, D , C, E = 275.1 *** |

| |

|Solutions: A, B, E, C, D, A |

|A, D, C, E, B, A |

|Cheapest Link: A, B, E, C, D, A =275.1 |

|Brute Force: 4! = 24 circuits |

A

B

C

D

E

60.3

55.1

57.7

59.5

53.9

61.2

54.8

55.4

53.6

58.7

|Graph #4 |

|Nearest Neighbor: A, F, B, E, C, D, A = 90 |

|Repetitive Nearest Neighbor: |

|A, F, B, E, C, D, A = 90 |

|B, F, A, E, C, D, B = 85 |

|C, E, A, F, B, D, C = 85 |

|D, E, C, A, F, B, D = 78 *** E, C, A, F, B, D, E = 83 |

|F, A, E, C, B, D, F = 91 |

| |

|Solutions: A, F, B, D, E, C, A |

|A, C, E, D, B, F, A |

|Cheapest Link: A, E, C, D, B, F, A = 85 |

|Brute Force: 5! = 120 circuits |

A

B

C

F

E

D

10

23

21

25

13

14

20

11

16

9

18

12

19

17

15

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download