Math 130 ~ Finite Mathematics

Dec 7, 2005

Exam Preparation Tutorial at 10:30 a.m. Rm 2601 (Our usual classroom)

• Bayes theorem
• Digital logic
• Simplex method for minimization problems.
• Combinatorics
• Probabilities of card hands.
• Truth tables.

I believe I have found answers (but not solutions) to the the two old final exams handed out: 2003, 2002

Dec 5, 2005

Exam Preparation Tutorial

• Formulating "normal" simplex method problems.
• Using a table to ease formulation (but watch out for "arbitrary" constraints).
• Formulating minimization problems for solution via the simplex method, and their initial manipulation.
• More probability problems (from 2002 exam).

Dec 2, 2005

Review: Venn diagrams, Conditional probability and Bayes theorem

• Venn diagrams

  "or" means shade in same direction

  "and" means shade in other direction and only keep crosshatched area

  Work from inside parentheses to outside and use multiple diagrams if necessary.

• Conditional probability: Pr( A | B )

  The condition, the B, changes the effective universe from being U to being B, so we only consider events inside B. This will (usually) change how much of A is possible.

• Bayes theorem.

  Things to remember:

  Make sure the preexisting condition is the first branch.

  The probabilities of the branches from a node must add to 1.

  Multiply probabilities along a path

  Add the probabilities of separate paths together.

Nov 30, 2005

Combinatorics Review

Notes

Nov 28, 2005

Solving minimization problems using the simplex method

The simplex method is based on three assumptions:

1. The objective function is to be minimized.
2. All variables will take non-negative values.
3. All the constraints have the form: linear expression ≤ nonnegative constant

Minimization problems usually violate assumptions 1. and 3.

We get around the violation of 1 by maximizing the negative of the objective function.

We get around violations of 3, by negating the constraint, then entering the constraints and objective function into a Simplex tableau. If any negative constants remain we pivot to remove them. The rule for choosing the pivot elements is:

1. Choose a row with a negative constant.
2. Choose a negative coefficient in this row. This will be the pivot column
3. Choose the pivot element within this column using the usual ratio test.
4. Pivot and repeat until no negative constants remain (above the objective function).

For exercise:

?

Nov 25, 2005

Simplex method example problem

?

Announcement

Addendum to Assignment 6 posted

As promised a second data set to consider has been added to the assignment.

Nov 23, 2005

Simplex method example problems

Topics

• Tutorial problem: 3.3-25.
• Example simplex problems:

  4.2-17

  4.2-16

For exercise:

4.2 - 15, 19, 21.

Nov 21, 2005

The simplex method for solving linear programming problems

Topics

• Tutorial problems: 3.2-3, 3.3-26.

  3.3-26 is important because a) in it we see how we can sometimes reduce the dimensionality of more than 2-dimensional problems to 2-dimensions (possible when the dimensions are not independent), and b) the solution lies along a boundary of the feasible region, rather than at a corner of it (3.3-26 solution page 1 and page 2).

• The Simplex method is involved but straightforward (i.e. mechanical):
  1. Formulate problem as for graphical solution, i.e. identify the objective function and the constraints.
  2. Add slack variables to each constraint inequality to make it into an equation (ignore the formal constraints that variables must be non-negative; this assumption is built into the Simplex method).
  3. Rewrite objective function so it equals zero (do it so the coefficients of the independent variables become negative).
  4. Write the equations into the simplex tableau (matrix).

     Notes:

     • Objective function is always the bottom row of the matrix.
     • Label the colums with the relevant variable names.
     • Label the rows with the names of the slack variables they contain.
  5. Pivot the tableau until all the entries in the bottom row are non-negative.
  6. Pivoting rules:
     1. The pivot column is the one with the most negative entry in the final row.
     2. The pivot entry in that column is the one for which the ratio of constant (in the last column) and coefficient is least.
• Example: Redo the sleds and toboggans problem using the Simplex method.
• Reading solutions at each step from the tableau.
• What the pivoting is doing in graphical terms.

For exercise:

3.3 - 1, 3, 5.

Nov 18, 2005

Graphical solution of linear programming problems; Pivoting matrices

Topics

• The second problem from the LP Problems Overhead.
• Do two pivots of the matrix from the quiz.

  Remember, to pivot a matrix about a pivot entry:

  1. Make the pivot entry a 1 by dividing every value in the pivot row by the pivot entry.
  2. Make each of the other values in the pivot column 0 by adding/subtracting a suitable multiple of the pivot row to/from each other row.

For exercise:

3.2 - 17, 31, 33.

Nov 16, 2005

Graphical solution of linear programming problems

1. Identify quantity to optimize (maximize/minimize).
2. Find equation for this quantity (this is called the objective function).
3. Find the constraints and express them as inequalities.
4. Find the feasible set or region by graphing the constraints and shading out the infeasible regions of the plane.
5. The optimum will occur at one of the "corners" of the feasible region (or along an edge of it), so calculate the value of the objective function at each corner and select the optimum value.

LP Problems Overhead

For exercise:

3.2 - 1, 3, 5, 9, and 13.

Nov 14, 2005

Systems of linear equations; Matrix operations

• Solving systems of linear equations:

  Unsuccessful attempt to do Problem 2.1-41.

  Example: Problem 2.2 - 30.

  Example: Problem 2.2 - 26.

• Interpreting the results of arithmetic matrix operations:

  Example: Problem 2.3 - 46.

Nov 9, 2005

Solving systems of linear equations

• Review: Pivoting a matrix to solve systems of linear equations.

  Pivoting about an entry:

  1) Divide all elements in the pivot row, by the pivot value. This makes the pivot entry 1.

  2) Add/subtract a multiple of the pivot row from each other row to make the other entries in the pivot column 0.

  To solve a system of linear equations by pivoting, pivot about each entry of the main diagonal.

• ASCII-graphic of a generic solution matrix:

   -              -
  | 1 0 0 0 ... c1 |
  | 0 1 0 0 ... c2 |
  | 0 0 1 0 ... c3 |
  | ...     ... .. |
  | 0 0 0 ... 1 cn |
   -              -
      

• Example problems: 1.4 - 68, 1.s - 35, 2.1 - 40.

For exercise:

1.4 - 69; 1.s - 17, 36; 2.1 - 35, 37; 2.3 - 21, 25, 29.

Nov 7, 2005

Solving systems of linear equations

• Meaning of =
• Operations allowed on equations.
• Graphing linear equations; y = mx + b; y = c; x = c.
• Finding the intersection of straight lines, a.k.a. solving two equations in two unknowns.
• Solving three equations in three unknowns using algebraic substitution.
• Solving three equations in three unknowns using a matrix representation and pivoting.

Nov 4, 2005

Graph Theory Review

• Review critical path by doing an example on the graph and in the table.
• Review matrix multiplication and graph connectedness by doing an example.
• Reachability matrix: matrix with entries of 1 if one vertex can be reached from another, 0 if not.
• Maximum length it could take to get from one node to another = # vertices - 1
• Preview remainder of course: Linear programming is our final topic. We'll build up to it via these topics: graphs of linear equations (1.1-1.4), solving systems of linear equations algebraically and using matrices (2.1-2.3), working with systems of linear inequalities, solving linear programming problems graphically (3.1-3.3), solving linear programming problems using matrices and the simplex method (4.1-4.5).

Nov 2, 2005

Graph Theory

Today's Topics

• Criteria for Euler circuits in directed graphs. Following the principle that to complete a circuit you have to be able to get into and then out of every vertex: For an Euler circuit the in-degree and out-degree of every node must be equal. For a path: All but two must be equal, and in the two unequal ones the difference of in-degree and out-degree must be 1.
• Matrix multiplication

  The mechanics of multiplying matrices: each entry in the product matrix is the sum of the products of the entries in the "column above it and the row to its left".

  More precisely (but less readably) the entry at row i and column j in the product matrix is the sum of the products of the entries in the ith row of A and the jth column of B.

  Requirement: For the matrices A and B to be multiplied, the number of rows in B must equal the number of columns in A.

• Interpretation of powers of adjacency matrices: If the adjacency matrix is called A then the entries in Aⁿ say how many paths of length n there are from the row vertex to the column vertex.

For exercise:

13.5 - 3, 13.

Announcement

Assignment 4 modified due date

Assignment 3 is now due Monday November 14 at 10:30 a.m.

Oct 31, 2005

Graph Theory

Today's Topics

• Critical path algorithm.
  1. Begin with a table giving the tasks, their duration times and their prerequisites.
  2. Add a column giving the Earliest Start Time for each task.
  3. Add a column giving the Earliest Finish time for each task (the latest time in this column is the earliest the project could be completed, and the tasks leading to it make up the Critical path).
  4. Add a column giving the Latest Finish Time for each task.
  5. Add a column giving the Latest Start Time for each task.
  6. Add a column giving the Slack Time for each task. The slack time is the Latest Start Time - the Earliest Start Time.

     The tasks with 0 slack time make up the critical path.

For exercise:

13.4 - 11, 13.

Oct 28, 2005

Graph Theory

Today's Topics

• Examples of uses of graphs in a wide variety of problems. View the complete collection.
• Graph colouring as a way of solving scheduling problems, e.g. 13.3 - 15.
• The four colour map theorem.

For exercise:

13.1 - 3

13.2 - 15, 19.

13.3 - 9, 12.

13.5 - 3

Announcement

Assignment 3 Extension

Assignment 3 is now due Monday October 31 at 10:30 a.m.

October 26, 2005

Graph Theory

Today's Topics:

• Jargon: loop, adjacency matrix.
• Examining an adjacency matrix: How many nodes? How many edges? Directed or undirected? Isolated nodes?
• Review MST algorithm done in-the-matrix.
• Drawing the graph given the adjacency matrix.
• Review: shortest route algorithm on-the-graph.
• Shortest route algorithm in the matrix.
• Notes on doing the shortest route algorithm in-the-matrix.

For exercise:

Some MST and Shortest Route problems.

Oct 24, 2005. Class 20.

Graph Theory

Today's Topics:

• Jargon: acyclic, tree, span, algorithm, heuristic.
• Implications of edges having two ends

  * total of degree sof all vertices in an undirected graph is always even

  * impossible to have a group of 7 people/servers in which each one knows/is-connected-to exactly 3 others

• Minimal Spanning Tree

  Goal: Find tree of minimal weight that connects all vertices in a graph.

  Algorithm:

  Start at any vertex.

  Add to the tree the lightest edge that connects to an as-yet-unconnected vertex.

  Repeat until all vertices are connected.

• Shortest Route

  Goal: Find the path of least weight from a source node to a destination node.

  Algorithm:

  Start at source node.

  Make shortest route possible to any unreached node.

  If the newly reached node is the destination node, stop (since it has just been reached by shortest route possible).

  Otherwise, repeat.

• Matrix representation of graphs.

  Entries show weights of edges connecting vertices.

  For undirected graph the matrix will be symmetric about the main diagonal.

Oct 21, 2005. Class 19.

Probability & Introduction to graph theory

Today's Topics:

• Final, non-medical example of Bayes theorem.
• Multi-way (as opposed to 2-way) Bayes' theorem problems.
• Graph theory

  Jargon: edges, vertices, nodes, circuit, path, degree.

  Euler and the bridges of Konigsberg problem.

  Euler circuit exists if all nodes have even degree.

  Euler path exists if at most 2 nodes have odd degree (and it must begin on one vertex of odd degree and end on the other).

  Euler circuit problems can be thought of as Snow plough problems.

Oct 19, 2005. Class 18.

Probability: Bayes' theorem

Today's Topics:

• Bayes' theorem examples.
• The formulaic expressions for the probabilities on each branch of a tree.

Oct 17, 2005. Class 17.

Probability: Bayes' theorem

Today's Topics:

• Bayes' thereom.

Oct 14, 2005. Class 16.

Probability

Today's Topics:

• Problems from the overheads
• Complementary events

  Probabilities of complementary events must add to 1, i.e. Pr(A) + Pr(A') = 1. This is usually used in the form Pr(A) = 1 - Pr(A'). Example: The fuse problem.

• Conditional probability

  Notation: Pr( A | B ) read "The probability of A given that B has occurred".

  Formula: Pr( A | B ) = Pr( A ∩ B )/ Pr( B )

  Examples: the math class, and the colour blind boy problems.

• Tree diagrams

  Vertices, i.e. branch points, correspond to decisions/choices.

  Sum of probabilities on branches leading from any vertex is 1.

  Probability of a path is found by multiplying all the probabilities along it.

  Paths can be interpreted as conditional and joint probabilities.

  Example: the bolt-producing machines.

For exercise:

6.5 ~ 3, 5, 9, 13, 15, 17, 22, 27, 35, 41, 47, 53.

6.6 ~ 5, 11, 15, 29.

Oct 12, 2005. Class 15.

Probability

Today's Topics:

• probability of an event
• probability of 1 of N equally likely outcomes is 1/N
• probability of 1 of a subset of n outcomes from a universe of N equally likely outcomes is n/N
• set-based interpretation of probabilities
• probabilities range from 0 (probability of an event outside the universe) up to 1 (the probability of any event at all occurring).
• inclusion-exclusion principle applies to probabilities as it did to sets: Pr(A ∪ B) = Pr(A) + Pr(B) -Pr(A ∩ B)
• probabilities of mutually exclusive outcomes are added, i.e. "the probability of this or this or this"

For exercise:

6.4 ~ 1, 7, 9, 11, 12, 13, 15, 17, 19, 22, 25, 27, 31, 39.

Announcement

Classes and tutorials

I am going to try and maintain a clearer separation of tutorials and classes.

• Classes will begin at 11 a.m.
• Tutorials will be Mondays from 10:30 -11:00, and Wednesdays from 10:30-10:45.
• Quizzes will be Wednesdays from 10:45-11:00.

If you have no questions then you do not have to attend the tutorial sessions, and may just arrive for the lecture or quiz.

Oct 8, 2005. Class 14.

Combinatorics

Today's Topics:

Took up Assignment 1. Note how little of the truth table had to be completed.

Took up Quiz 3. There will be a Venn diagram counting problem on the final exam. (See the previous final exam attached to the course outlne.)

The navigation problem of getting from one point in a grid to another, can be thought of as choosing a number of times to go west or north. So in the example, we had to choose 4 of 11 movements to be westward ones, giving C(11,4).

We rarely add together counts of ways in combinatorics, but it does come up when we need to combine the number of ways associated with mutually exclusive possibilities, e.g. the urn problem 5.6 - 4 d).

For exercise:

5.6 ~ 4, 13, 15, 17, 20, 25, 29, 31, 33, 39.

Oct 5, 2005. Class 13.

Combinatorics

Today's Topics:

Continued doing combinatorics by example using problems from the overheads.

To the types of problems from the previous class we added compound problems, where we might have to add the results of two or more ways of counting things out, e.g. SEQUOIA, or where there might multiple different types of choices, e.g. the poker hand.

As before the trick with combinatorics is to get good at identifying which type a particular problem is.

For exercise:

Continue working on the exercises assigned in the previous class.

Oct 3, 2005. Class 12.

Combinatorics

Today's Topics:

We did combinatorics by example considering problems from the overheads.

We saw four main types of problems:

• Problems where we had to arrange/order/line up n objects, e.g. "line up 5 children for a photograph". In these cases there were n! arrangements possible.
• Problems where we had to arrange r objects chosen from a group of n objects. In these cases there were P(n,r) = n!/(n-r)! possibilities.
• Problems where we did something with two possible outcomes n times, "flip a coin 6 times". In these cases there were 2ⁿ outcome sequences.
• Problems where we had to select r things from a set of n things and all we cared about was which r things we ended up with (not the order in which we selected them), e.g. "choose 3 people from a group of 5". In this case there are C(n,r) = P(n,r)/r! = n!/(r!(n-r)!) possibilities.

The trick with combinatorics is to get good at identifying which type a particular problem is.

For exercise:

5.4 ~ 2, 5, 7, 9, 15, 17, 22, 27, 29, 31, 36, 49, 51, 55.

5.5 ~ 21, 25, 29, 31, 33, 37, 41, 53, 57.

Sept 30, 2005. Class 11.

Mathematics of elections

Today's Topics:

• Took questions about the election theory reading.
• Previewed combinatorics when we considered the question of how many ballots would be needed for an n-candidate race.

For exercise:

Work on Assignments 1 and 2.

Sept 28, 2005. Class 10.

Set theory

Today's Topics:

• Lots of questions about the homework problems from Monday. Well done.
• Euler diagrams. A type of set diagram that can be helpful in analyzing arguments that use quantifiers, like "all", "some", and "none".

For exercise:

Try using Euler diagrams to analyze the following arguments.

1. All joggers are lean. All lean people are healthy. Therefore all joggers are healthy.
2. Some mathematicians are teachers. Some teachers are bald. Therefore some mathematicians are bald.
3. All mathematicians are teachers. Some teachers are bald. Therefore some mathematicians are bald.
4. All mathematicians are teachers. All teachers are bald. Therefore some mathematicians are bald.
5. Mammals are warm-blooded. Snakes are not mammals. Therefore no snakes are warm-blooded.

Sept 30, 2005. Class 11.

Election Theory; Combinatorics preview

Today's Topics:

• Mathematics of elections. Worked examples of Plurality, Run-off, Borda and Condorcet methods. Discussed real-life implications and exampels of these systems.
• Preview of combinatorics. Prompted by the question: "How many ballot forms do you need for n candidates?"
• Review of factorial notation: n! = n × (n-1) × (n-2) × ... × 2 × 1. Note 0! = 1.
• Multiplication principle: To find the total number of ways of doing a multistage operation multiply the numbers of ways of doing each stage. Examples: license plates, lining people up, listing candidates on a ballot.

For exercise:

Work on the first two assignments.

Sept 26, 2005. Class 9.

Set theory

Today's Topics:

• Set notation: { }, U, ∅, ∪, ∩, n( ).
• Venn diagrams.
• Using set-based techniques to analyze numeric data.

For exercise:

5.1 ~ 13, 27, 29, 31.

5.2 ~ 3, 5, 9, odd 13 - 43.

5.3 ~ 1, 3, 7, 13, 17, 41, 43, 45, 47, 50, 51.

Sept 24, 2005.

Digital logic Review problems

Sept 23, 2005. Class 8.

Digital logic 3

Today's Topics:

• Review

  Analyzing a circuit, i.e. figuring out its input-ouput table.

  Designing a circuit that implements a particular input-ouput table.

• Completing the full-adder: Divide and conquer. First add two of the bits. Now add the third bit to the result of the first addition. Figure out what to do with the two carry outputs.
• Representing negative numbers in digital circuits: 2's complement. (For more information about 2's complement representation start at this Wikipedia article).
• Storage and memory. How can a circuit remember a value? Solution: Configure two and-not combinations so their outputs feed into each other's inputs.

For exercise:

Try completing our circuit to add two 1-bit numbers.

Sept 21, 2005. Class 7.

Digital logic 2

Today's Topics:

• Review: binary (base 2), counting, converting to and from, addition, digital logic gates.
• 1-bit or half-adder. The carry is just (i1 and i2). The output is high as long as "one or the other but not both" of the inputs are high, i.e. (i1 or i2) and ~(i1 and i2)

For exercise:

Try completing our circuit to add three 1-bit numbers (called a full-adder).

Sept 19, 2005. Class 6.

Digital logic 1

Today's Topics:

• Counting in base 2 (binary).
• Converting from binary to decimal (remember the columns are powers of 2 now rather than 10).
• Converting from decimal to binary (like making change you start with the largest amount you can give, and all the amounts are powers of 2, i.e. 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, ...).
• Adding binary numbers.
• Digital gates: and, or, not.
• Began working on a circuit to add two 1-bit numbers. (bit = binary digit)

For exercise:

Try completing our circuit to add two 1-bit numbers.

Try question 3 from the 2003 final exam (handed out with the course description at the start of term).

Sept 15, 2005. Announcement.

Class Cancelled Friday Sept 16

My grandmother has passed away and I will be travelling to the funeral in Ontario. I will be leaving early Friday morning and, assuming there are no missed connections, will be back for Monday's class.

For exercise:

Logic review problems and solutions

Sept 14, 2005. Class 4.

Validating arguments 2 and 3

Today's Topics:

• Validating arguments 2: Write the entire argument as a single implication statement. Construct the truth table for it. If the argument is valid, the statement will be a tautology, i.e. true in all cases.
• Example. Compare the structure and validity of the two arguments: "If it is snowing, I wear my boots. It is not snowing. Therefore I am not wearing my boots." and "If it is snowing, I wear my boots. I am not wearing my boots. Therefore it is not snowing."
• Names for common argument forms. See table 1 on page 592.
• Using de Morgan's theorem to rephrase sentences.
• Example of Hypothetical Syllogism: "If you tell the truth, you will sleep well. If you sleep well, you will be healthier. Therefore, if you tell the truth you will be healthier."
• Validating arguments 3. If the conclusion can be derived from the premises using valid rules of inference then the argument is valid.
• Examples: problems 12.5 - 1, 2, 13.

For exercise:

• 12.5 - 3, 5, 7, 9. (Click the links to see my solutions).

Sept 9, 2005. Class 2.

Statements; Connectors (^, v, ~); Truth tables

Today's Topics:

• Introduction
• Graphical overview -- what we're going to cover over the next two weeks (this is "The Overhead").
• A valid argument is structurally sound, i.e. the conclusion follows from the premises.
• Simple statements
• Logical connectors and truth tables
• Compound statements
• Logical equivalence
• de Morgan's theorems

Lecture Notes

For exercise:

• Problems 1-15, 17, and 19 on page 566 of the text.
• Problems 1, 3, 5, 7, 13 and 19 on page 574 of the text.

You can check your answers to the odd-numbered problems on pages A50 and A51 in Appendix A at the back of the book. The sentences in the even-numbered problems from 2 through 14 are all statements.

Sept 7, 2005. Class 1.

Course Introduction

In today's class we went over the course description with some care, and then looked at some simple finite math problems to get us thinking mathematically:

• How can we tell if a straight-line drawing can be done without lifting pen from paper or retracing any lines?
• If a maze is drawn as a closed contour, how can we quickly determine if a given point is inside or outside the maze?
• What are the least and most number of partitions that can be created in a rectangle using straight lines?

For exercise:

• In class we found a pattern that seemed to allow us to predict the maximum number of partitions we could create with a certain number of straight lines, but we didn't have a good explanation for why that pattern worked. See if you can come up with a compelling explanation for the pattern.
• We completed a table showing the number of maximum number of partitions we could get with 0, 1, 2, 3, 4, and 5 lines. What is the maximum number we could get if we used 100 lines?
• In class we saw shapes that could be drawn without retracing a line or lifting pen from paper from any corner of the shape, ones that could be so drawn if we started at some corners, and one that could not beso drawn. Is there a simple test that we can use to tell which category a particular shape is in? If so, what is it?