Sasha's combinatorics questions, note esp. 5.5-70.
Questions from the 2006 Final Exam: 2, 1, 12, 13.
Study! Bring problems and questions to class.
Combinatorics review problems[PDF] and blackboard pics ( 1, 2, 3, 4 ) of their solutions.
Try redoing the combinatorics problems assigned earlier in the term, and bring any questions or problems that arise to class Wednesday.
Example: Redo 3.3-25 which we did earlier graphically, using the simplex method. Pics: 1, 2.
4.3: 9, 13.
Taking up the quiz: the problem, the blackboard pic.
Taking up the starship problem from the assignment: blackboard pic and the overheads. 1 is the first attempt but the tree gets too large (108 paths, see calculation in blackboard pic), so 2 try not pursuing branches once the time taken is already >17, then 3 notice that some states reoccur and decide to pursue only the quickest way of achieving each state, which 4 leads to noticing that there aren't all that many states, so the graph (as opposed to tree) is managable and the problem can be solved via the Shortest Route algorithm.
Simplex method minimization by example: Problem 4.3-3 Pic (see the yellow box on page 182 for a summary of the steps).
Notes:
Example: 4.4-20 pic
Notes:
Assignment tip: The first good approach most people take is to send the lightest item off the starship with each heavier item, and then to bring the lightest item back, in order to minimize the return travel time. To do better you will need to send the two largest items off together so the weight of the heaviest container can "mask" the weight of the second heaviest one.
Example: 4.2-18. Pic. (Note that in the pic we were exploring the system and had changed the space required per B system from what the book specified to 8 cubic feet).
Blackboard pics: 3.3-29, 3.2-31.
The Simplex method is involved but straightforward (i.e. mechanical):
Notes:
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.
4.2: 17, 21, 23.
Examples: 3.3-27, 3.3-25.
Example: Finishing the second example from the LP Problems Overhead
Example: Reducing the apparent dimensionality of a problem 3.3-23
3.3: 27, 29.
Graphical solution of linear programming problems:
Examples: Completed the first and began the second problem from the LP Problems Overhead
3.2 - 1, 3, 5, 9, and 17.
Handouts: Selections from three finite math textbooks. Remember: Green pages have the best descriptions of MST, Shortest route and Critical Path done in the table (but they draw their critical path graphs oddly). Pink pages are from an earlier edition of the text and are good on graph colouring, and Euler problems, but don't provide a useful algorithm for solving Critical Path problems (but does draw the graph correctly). Buff (pale yellow) pages provide solved problems.
Pivoting about an entry in a matrix:
ASCII-graphic of a generic solution matrix (that has a unique solution):
- -
| 1 0 0 0 ... c1 |
| 0 1 0 0 ... c2 |
| 0 0 1 0 ... c3 |
| ... ... .. |
| 0 0 0 ... 1 cn |
- -
Examples: One created in-class (See Pic 2 above). 2.2-10, 2.2-14.
Possible results of attempting to solve a system of equations:
Example of problem formulation and solution: 2.2-27.
Method 2: Gaussian elimination.
Method 3: Substitution.
Example: What it looks like when there is no solution: 0=18.
Graphical interpretation of solutions: The intersection of two straight lines (in 2-D, or of three planes in 3-D). When there is no solution it is because the lines are parallel and do not intersect.
Gaussian elimination to solve a system of three equations in three unknowns.
Doing Gaussian elimination in a matrix by pivoting.
2.1: 25, 29, 31, 45, 47, 49.
2.2: 1, 3, 5, 11, 13, 15. In 2.2 use Gaussian elimination in-the-matrix.
Updated! Supplementary notes on doing the shortest route algorithm in-the-matrix.
Review of critical path method.
Matrix multiplication
The result of AB will have as many rows as A and as many columns as B.
To multiply A and B, the number of rows in B must equal the number of columns in A.
If you write the matrices with B above and to the right of A, the result matrix will be to the right of A and below B and each entry in the result matrix is the sum of the products of the elements in the row to its left and the column above it.
Connectedness and Reachability
A matrix is connected if a path exists from every vertex to every other vertex, i.e. if every vertex can be reached from every other. This can be tricky to assess visually, especially if the graph is directed.
The adjacency matrix, A, for a graph has 1s where two vertices are connected by an edge, and 0 otherwise.
The entries in An give the number of paths of length n from one vertex to another.
The longest a path could need to be to get from one vertex to another is N-1 where N is the number of vertices in the graph (because you couldn't have to go through every other vertex more than once).
The Reachability matrix is the sum A + A1 + A2 + ... + AN-1. If it has any 0 entries off the main diagonal then the matrix is not connected.
Hamiltonian Circuits
No easy test for the existence of a Hamiltonian circuit.
Finding the Hamiltonian circuit of minimal weight (popularly known as the travelling salesman problem) efficiently is a famous unsolved problem.
Brute force is an ineffective method because if the graph is complete (i.e. every vertex is directly connected to every other), the complexity increase as the factorial of the number of nodes.Solving systems of linear equations.
Method 1: Solving by equating.
Do most of the problems from Graph Theory problems 1.
Algorithm ("in the table")
The tasks with 0 slack time make up the critical path.
Blackboard pics: 1, 2, 3, 4, 5.
Review Shortest route on a graph.
Shortest Route (in a matrix) See the blackboard pic for the algorithm.
Supplementary notes on doing the shortest route algorithm in-the-matrix.
Review to compare: MST in a matrix.
Graph Colouring. Problem: What is the smallest number of colours that can be used to colour the vertices of a graph such that no two connected vertices share the same colour?
Graph Equivalence What is necessary for two graphs to be equivalent?
Jargon: acyclic, tree, span, algorithm, heuristic.
Examining an adjacency matrix: How many nodes? How many edges? Directed or undirected? Isolated nodes?
Review: Minimal spanning tree algorithm 1) on graph, 2) in tree.
Implications of edges having two ends
Shortest Route (on the graph)
Goal: Find the path of least weight from a source node to a destination node.
Algorithm:
Some Graph Theory problems 1. We haven't seen how to do 5. in class yet, but you can see the example linked above, or wait until Monday.
Jargon: edges, vertices, nodes, circuit, path, degree.
Euler and the bridges of Konigsberg problem.
Minimal Spanning Tree
Goal: Find tree of minimal weight that connects all vertices in a graph.
Algorithm:
Matrix representation of graphs.
Entries show weights of edges connecting vertices.
For undirected graph the matrix will be symmetric about the main diagonal.
Loops will show up as entries on the main diagonal.
Can you draw a graph in which three vertices have odd degree? If not, why not? (Recall that the degree of a vertex is the number of edges that land on it.)
(Hamiltonian circuits) Similar to the snow plow problem we can imagine a school bus problem. Where the snow plow needs to traverse every road (edge) and doesn't worry about passing through intersections (vertices) more than once, a school bus wants to visit every bus stop (vertex) once, but doesn't need to drive all the roads (edges) in the city. Is there a simple test for whether a graph has a circuit of this type?
Bayesian problems from the overheads
Bayes' theorem examples.
Comparing three alternative representations for working with conditional probabilities and Bayes theorem:
Multi-way (as opposed to 2-way) Bayesian problems.
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.
6.6: 5, 11, 13, 15.
6.7: 3, 5, 7, 11, 19.
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.
6.5 ~ 3, 5, 9, 13, 15, 17, 22, 27, 35, 42, 47, 49, 58.
(Election theory)
Example probability problems.
(Election theory)
(Take up Assignment 1)
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.
Example probability problems.
Probability of an event is the chance that it will occur
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
Probabilities range from 0 (probability of an event outside the universe) up to 1 (the probability of any event at all occurring).
Pr(U) = 1.0, Pr(U') = 0.0
Set-based interpretation of probabilities
Inclusion-exclusion principle applies to probabilities as it did to sets: Pr(A ∪ B) = Pr(A) + Pr(B) -Pr(A ∩ B)
The probability of an event not happening is 1 - the probability that it does happen, and vice versa: Pr(E') = 1 - Pr(E) and Pr(E) = 1 - Pr(E')
Probabilities of mutually exclusive outcomes are added, i.e. "the probability of this or this or this"
Examples: Problems 1-4 from the overheads.
For interest, via this CBC story comes the news that a couple in the US just won a $200,000,000 million Powerball lottery. The record US lottery jackpot is $365,000,000.
6.4 ~ 8, 10, 11, 12, 13, 15, 17, 19, 22, 25, 27, 30, 39.
Discussion of voting systems: Plurality, Runoff/Majority, Borda, Condorcet.
Problems:
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.
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) (or equivalently 7 of 11 movements to be northward ones).
Note that mathematics relies on a relatively small number of solution techniques, but is very creative at finding ways to apply them. So for example we were able to translate the street grid problem into one equivalent to the footbal problem.
5.6 ~ 4, 13, 15, 17, 20, 24, 29, 31, 33, 39.
Working backwards from combinations to set size: 5.4-28.
A subtle formulation: 5.4-26
Standard problems: 5.5-32, 43, 40, 47-49.
Dealing with "at least", "more than" and their ilk: Counting the membership of multiple sets. 5.6-10, 16.
In combinatorics we saw four types of problems:
The trick with combinatorics is to get good at identifying which type a particular problem is.
A peek ahead: 5.6-34.
5.4 ~ 2, 5, 7, 9, 15, 17, 22, 27, 29, 31, 40, 53, 55, 59.
5.5 ~ 21, 25, 29, 31, 33, 37, 41, 53, 57.
Tutorial: More on sketching Venn diagrams.
Example: First those fun-loving MIT students:
A random sampling of 98 students at MIT revealed that: 62 had taken Calculus, Finite Mathematics and Programming, 19 had not taken Calculus, 80 had taken Programming and Finite Mathematics, none had only taken Programming, but 82 had taken Programming in conjunction with another course, 3 had only taken Calculus, and 73 had taken Calculus and Finite Mathematics.
a) How many students had taken only Finite Mathematics?
b) How many had not taken any of Calculus, Finite Mathematics, and Programming?
c) How many had taken Calculus or Programming?
d) How many had not taken Programming, but had taken Finite Mathematics?
Then the newspaper excerpt on handgun deaths:
The number of murder victims in this country [U.S.A.] during the years 1987 and 1988 totalled 36,128 (roughly the same as the number of U.S. battle deaths during the 13 years of the Korean War). Of this total 18,269 were victims during 1988. Handguns were the weapons of choice in dispatching 16,085 of the victims during these two years, while 9,991 of the victims during 1988 met their death with some weapon other than a handgun.
"The increase in handgun death is particular disheartening", said
Shading Venn diagrams. How to handle Intersection (shade in opposite directions) and Union (shade in one direction).
The cardinality of sets: n( A ∪ B) = n( A ) + n( B ) - n( A ∩ B )
Beware double counting.
Using set-based techniques to analyze numeric data.
An example:
A survey of 110 lung cancer patients showed that 70 were cigarette smokers, 60 lived in urban areas, and 35 had hazardous occupations. Forty of the smokers lived in urban areas, 15 had hazardous occupations, and 5 were in both categories. Ten of the patients with hazardous occupations neither lived in an urban area, nor smoked.
a) How many of the patients living in urban areas had hazardous occupations?
b) How many of those living in the urban areas neither smoked nor had hazardous occupations?
c) How many patients neither smoked, nor lived in an urban area, nor had a hazardous occupation?
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.
Try using Euler diagrams to analyze the following arguments.
I've also posted some logic review problems and the solutions to them to give you some further practice analyzing arguments.
Try and formulate an English statement to describe this input-output table:
i1 i2 | output -------+------- 0 0 | 1 0 1 | 0 1 0 | 0 1 1 | 1
Try and translate your statement into a symbolic expression.
Try and draw a circuit to match the statement.
