discrete math final exam

what makes something a Euler path

exactly two vertices w/ an odd degree

what makes something a Euler circuit

all even degrees

how to write an adjacency matrix?

put a 1 if theyre connected and a 0 if they arent.

how to find population distribution after X amount of time

multiple initial population matrix by transition matrix to the power of X

how to find the check digit for a zip code

add up all the numbers, then add the number that will make the total divisible by 10

how to find the check digit for a 10-digit ISBN number

multiply the numbers by 10,9,8,7, etc and then add the number that will make the total divisible by 11.

how to find the check digit for a 13-digit ISBN number

multiply the first 12 numbers by 1,3,1,3, etc, and add the number that will make the total divisible by 10.

saddle point

when the minimax and maximin are the same number

maximin

the max of the row mins

minimax

the min of the column maxes

definition of a bipartite graph

every vertex can be partitioned into 2 sets in such a way that every edge has one end point in one set and the other endpoint in the other set.

connected graph

every pair of vertices is connected

how to find plurality winner of an election

choice that recieves most first place votes

how to find boarda count winner

assign points based on place and just multiply. whoever has most points wins.

how to find condorcet winner

a choice that could obtain a majority over every other choice in a runoff. example B wins over A 18 to 8. B wins over C 20 to 6. B wins over D 19 to 7.

runoff

used when majority winner required but there isn’t one. eliminate all choices except the 2 with the more 1st place votes than others.

ideal ratio

ratio of total pop to # of seats

class quota

number of seats each class should recieve. pop. of that class divided by the ideal ratio.

jefferson’s plan

reduce the ideal ratio until one of the classes reaches the next whole number. the class to the nearest whole # next “wins”

ex: sophs - 10.31 juniors - 5 seniors -4

becomes sophs - 11 juniors - 5 senios - 4

jeffersons adjusted ratio

the ratio to divide each class size by to increase the quote to the next whole number. class size/ truncated quote + 1

jefferson adjusted

take each class and divide it by the class quota but jefferson adjusted ratio version.

webster model

based on the arithmetic mean of the 2 #s that the quota is between. rounds up if the quota is greater than or equal to 0.5

hill model

based on geometric mean of the two numbers that the quote is b/t. rounds up if the quota is greater than or equal to the geometric mean.

what is a hamiltonian path

a path that uses each vertex of a graph exactly once

what is a hamiltonian circuit

a hamiltonian path that ends at the starting vertex.

what is a connected graph

every pair of vertices can be joined by a path

dijkstra’s algorithm

label the starting vertex S, examine all edges that are adj to S, darken the edge w/ the shortest length & circle the vertex at the other endpoint.

what is a “cycle” in a graph?

any path that begins at the same vertex

what is a tree?

a connected graph that contains no cycles