Texas A&M University-Corpus Christi / Dept. of Computing and
Mathematical Sciences
MATH 2305 §002 -- Discrete Mathematics I -- Spring
2003
Test 2 Review
| Section | Topic | Examples | Comment |
| 3.1 | Describe sets by a list of elements and by a characterizing property | 3.1:4 |
|
| Prove that one set is a subset of another | 3.1:11,12,13,29 | Relationships between sets, with notation | |
| Find the power of a set | 3.1:21-25 | Number of subsets of a set. | |
| Check that the required properties for a binary or unary operation are satisfied. | Not to be tested | Binary and unary operations |
|
| Form new sets by binary operations. | 3.1:37-49 | Operations on sets--union, intersection, complement, set difference, cartesian product | |
| Prove set identities | 3.1:51-64 |
|
|
| Demonstrate denumerability | Not to be tested |
|
|
| Use the Cantor diagonalization argument to prove that certain sets are uncountable. | Not to be tested |
|
|
| 3.2 | Use the multiplication principle for counting the number of objects in a finite set | 3.2:1,2,7,9,11 | The multiplication principle is used to count the number of possible outcomes for a sequence of events, each of which has a fixed number of outcomes. You must be able to write down the sequence of events, and for each event, the number of outcomes. |
| Use the addition principle for counting the number of objects in a finite set | The addition principle is used to count the number of possible outcomes for disjoint events. You must be able to write down each of the disjoint events and count the number of outcomes in those events. | ||
| Use decision trees for counting the number of objects in a finite set | 3.2:69-71 | Decision trees are used for sequences of events where the number of outcomes depends on the previous outcomes. | |
| Use the above methods in combination | 3.2:18,37,63,67 | Look to how you can break an event into separate events or a sequence of events where one of the principles might apply. | |
| 3.3 | Use the principle of inclusion and exclusion to find the number of elements in the union of sets. | 3.3:1-12 |
The union of sets is the union of intersections of subcollections of the sets. Knowing all but one of these, you can find the unknown one. |
| Use the pigeonhole principle | 3.3:13-21 | The pigeonhole principle works best when you can clearly identify the pigeonholes (or bins) and pigeons (items) that will go in them. Sometimes identifying the pigeonholes and pigeons requires a lot of work. | |
| 3.4 | Find the number of permutations... | 3.4:2,3,6,7 | This is just a formal summary of the multiplication principle in a specific case. Remember, order matters in a permutation. Telling example: choosing officers from the set of members in a club. |
| Find the number of combinations.... | 3.4:16,17 | The number of combinations is always smaller than the number of permutations. Remember, order DOES NOT matter in a combination. Telling example: choosing committee members from the set of members in a club. | |
| Use permutations and combinations...with the multiplication principle and addition principles. | 3.4:18,19,42,59 | This 'technique' is an art that is best done by carefully analyzing how the selecting and arranging will take place. Identify where order matters and where it doesn't. Identify where choices are taken in turn or exclusively. | |
| Count permutations of objects that are not all distinct. | 3.4:5,63 | Using the multiplication principle: #ways to choose elements* #ways to put in order = # permutations, the #ways to put k identical objects in order is k!. So divide the #permutations of objects as distinct by k! to find the permutations with k identical indistinct objects. | |
| Find the combination of r out of n distinct objects with repetition. | 3.4:71,73 | With r objects (r = total # of gemstones) and n distinct types of objects (n = types are diamonds, rubies and emeralds), there are n-1 divisions (vertical bars) between the different types. Making slots to be filled with the r objects (asterisks) and n-1 divisions leaves a total of r+n-1 slots to be filled by r asterisks and n-1 bars. There are C(r+n-1,r) = C(r+n-1,n-1) ways to put in the asterisks or the bars. | |
| 3.5 | Compute probability when all outcomes are equally likely | 3.5:1-5 | If there are n equally likely outcomes, the probability of an event containing k outcomes is k/n. |
| Compute the probability of an event using a probability distribution | 3.5:40 | If each outcome x_i has a probability p(x_i), the probability of an event is the sum of the probabilities of the outcomes in that event. | |
| Compute conditional probabilities | 3.5:51 | Use the formula in the book, or use the prior event to restrict the sample space. | |
| Determine whether two events are independent. | 3.5:51 | Events A and B are independent if P(A|B) = P(A). That means, that it the probability of A happening is the same regardless whether B happens or not. Examples: The rolls of dice are independent. Whether or not a cold front passes each of two consecutive days are not independent. | |
| Compute expected value using a random variable. | 3.5:52-54 | Use a table to organized the outcomes (x), the values of the random variable (f(x), or X(x)), the probabilities (p(x)) and the expected values of individual outcomes (x*f(x), or x*X(x)). Summing the probability column gives 1; summing the expected value column gives E(X). | |
| Events are subsets of the sample space--the set of all possible outcomes | 3.5:1-5 | ||
| Compound events can be described in terms of other (simple) events using unions, intersections, complements and conditions. | 3.5:13-20 | Two cards are drawn from a pack. Let A be the event that the first card has value 3, and B be the event that the suit of the second card is a club.
|
|
| The probability of compound events can be calculated from the probabilities of the simple events. | 3.5:13-20 |
|
|
| Observations about probability are based on sets and counting their elements. | 3.5:40 | See Table 3.3 |