Discrete Math

NCFinal Exam: Refresh your memory on …

Matrix multiplication

  • Dimension m x n * n x p is ok and will result in a matrix of dimension m x p; m x p * n x pis not ok
  • Must be SQUARE to be raised to a power

Graph Theory

  • In any graph, the sum of the degrees of the vertices = (number of edges * 2)
  • In any graph, the ODD vertices always happen in pairs (never an odd number of odd vertices)
  • In a COMPLETE graph with N vertices (KN)…
  • The degree of each vertex is
  • The sum of the degrees is
  • The number of edges is
  • The number of Hamilton Circuits or Paths is!
  • Complete graphs can be used to model problems like number of matches in a round-robin tournament, number of handshakes, number of pairwise comparisons, etc.
  • Identify which perspective you are working with:
  • Street Sweeper = Every Edge = Euler Circuits/Paths
  • Connected, with 0 odd vertices = Euler Circuit/Closed Unicursal Tracing
  • Can start anywhere and end up back at that point
  • Connected, with 2 odd vertices = Euler Path/Open Unicursal Tracing
  • The 2 odd vertices are the start & stop points
  • Pizza Guy = Traveling Salesman = Every Vertex = Hamilton Circuits
  • Nearest Neighbor = Leap Frog from required vertex
  • Repetitive Nearest Neighbor = Leap Frog from EACH vertex; Choose best one; Write circuit from required vertex
  • Cheapest Link = Jigsaw Puzzle:Sort pieces; Use vertex-only workspace; Add edges but do NOT make degree of 3 OR a circuit; When (Number of Edges Chosen) = (Number of Vertices – 1), close the Hamilton Circuit; Write circuit from required vertex
  • Cable Company = Minimum Spanning Tree
  • Trees are “barely” connected
  • Number of Edges = (Number of Vertices – 1); Redundancy = 0
  • Kruskal’s Algorithm = Jigsaw Puzzle: Sort pieces; Use vertex-only workspace; Add edges but do NOT make a circuit (CAN have degree of 3); When (Number of Edges Chosen) = (Number of Vertices – 1), you have the OPTIMAL minimum spanning tree

Measures of Location and Spread

  • Location: Mean (average), Median (50th percentile), Percentiles
  • Spread: Standard Deviation, IQR
  • Five-number Summary, Quartiles

Normal Distribution

  • Line of Symmetry at the center = Mean (μ) = Median (M)
  • Points of Inflection are 1 Standard Deviation (σ) to the left and right of the Line of Symmetry
  • PL = μ – σ and PR = μ + σ
  • Quartiles are 0.675 Standard Deviations to the left and right of the Line of Symmetry
  • Q1 = μ - 0.675*σ and Q3 = μ + 0.675*σ
  • z-values are used to Normalize the data (make the units standard)
  • z-value =
  • Negative z-values are to the left of the Line of Symmetry; Positive to the right
  • 68 – 95 – 99.7 Rule: In a Normal Distribution…
  • 68% of the data falls within 1 Standard Deviation of the Mean
  • 95% of the data falls within 2 Standard Deviations of the Mean
  • 99.7% of the data falls within 3 Standard Deviations of the Mean
  • There are virtually only 6 Standard Deviations separating the Minimum from the Maximum

Probabilities

  • Multiplication Rule: ____ x _____ x _____ etc. based on the number of choices for each position
  • CAN be used when Repeats are allowed
  • CANNOT be used if Order doesn’t matter
  • Permutations Combinations
  • CANNOT be used when Repeats are allowed
  • r = number of positions; n = number of choices
  • Permutations for when order DOES matter (count them all)
  • Combinations for when order DOES NOT matter (take out the duplicates; divide by the number of positions factorial)
  • (dividing by r! takes out the duplicates)
  • EXPERIMENTAL Probability of Event E =

(Number of Occurrences of the Event) ÷(Number of Trials in the Experiment)

  • THEORETICAL Probability of Event E =

(Number of Outcomes that “fit” the criteria of the Event) ÷ (Total Number of Outcomes)

  • Probabilities are between 0 and 1
  • Pr (Impossible Event) = 0
  • Pr (Certain Event) = 1
  • Pr (Complementary Event) = 1 – Pr (Event)
  • With INDEPENDENT Events (no overlapping):
  • Pr (A and B) = Pr (A) * Pr (B)
  • Pr (A or B) = Pr (A) + Pr (B)
  • Odds:
  • Pr (Event) = good ÷ bad
  • Odds of Event = good “to” bad
  • Odds against Event = bad “to” good
  • With Events that are NOT Mutually Exclusive (they overlap), use Venn Diagrams
  • Tree Diagrams
  • Branches from a single node all add up to 1
  • Probability of a pathway = branch * branch * branch etc along the pathway
  • Sum of all complete pathways = 1
  • Expected Value = Sum of all Outcomes * Each Outcome’s Probability
  • Represents the AVERAGE outcome (“ in the long run”)
  • Binomial Expansion: (x + y) n
  • Number of terms = n + 1
  • Coefficients from Pascal’s Triangle
  • x powers go from n down to 0; y powers go up from 0 to n
  • x power + y power = n
  • (x + y) n has all positive terms; (x – y) n has alternating terms: positive, negative, positive, etc.
  • To find the mthterm of (x + y) n
  • (n – m) = z
  • nCz * xz * y(n – z)

Apportionment

  • “Seats” are divided by “States” based on “Population” (“what”, “who”, “how”)
  • Standard Quota = Population ÷ Standard Divisor
  • Standard Divisor = Total Population ÷ Number of Seats
  • Hamilton’s Method = Method of Largest Remainder
  • JAW DUC

Election Theory

  • Majority = More than half; Plurality = Most
  • Plurality Method: Most 1st place votes wins
  • Borda Count Method: Points are earned based on preference with 1 for last, 2 for second to last, etc.; Points for each candidate are totaled; Highest wins
  • Plurality-with-Elimination Method (we called this “Eliminate Until Majority”): Eliminate the candidate with the fewest 1st choice votes; Recount; Continue until a majority candidate wins
  • Also known as Hare’s Method or Instant Runoff Voting
  • Method of Pairwise Comparisons: Compare each pair of candidates in head-to-head comparisons; Award 1 point for a win or ½ point to each for a tie; Total up points; Highest wins
  • Also known as Copeland’s Method
  • An “undefeated” candidate is called the Condorcet Candidate
  • Ranking Methods: Used to find the rankings, not just the winner
  • Extended: Do the method ONCE and then rank them (very intuitive)
  • Recursive: RE-Do the method over and over, removing the winner each time (very tedious – especially Recursive Borda Count as new point values are needed)

Voting Power

  • [q : w1, w2, w3, … wn]
  • q (the “quota”) = the Number of Votes needed to Pass a Motion
  • wn(the “weight of Player n”) = the Number of Votes Player n Controls
  • Quota should always be more than ½ the total votes and less than all of them
  • Banzhaf Power Index: Based on how often a Player is CRITICAL in a Winning Coalition
  • Shapley-Shubik Power Index: Based on how often a Player is PIVOTAL in a Sequential Coalition

Fair Division

  • Discrete Loot:
  • Method of Markers
  • Method of Sealed Bids
  • Continuous Loot:
  • Divider-Chooser Method
  • Lone Divider Method
  • Last Diminisher Method

Copies of all the reviews are available on my webpage.