Cs 214 Exam 2

Front 1

countable set

Back 1

can identify a recipe to enumerate the set's items

Front 2

uncountable set

Back 2

no series of steps to enumerate all of the set's items

example: Real numbers

Front 3

addition principle

Back 3

when a choice needs to be made from any one of several cases

|AUB|=|A|+|B|

for disjoint A and B only

aka cardinality of set union

Front 4

multiplication principle

Back 4

when a series of choices needs to be made

# of possibilities: product of the input set cardinalities

Front 5

general property of set intersection cardinality

Back 5

|A^B|=|A|-|A-B|

Front 6

general property of set union

Back 6

|AUB| U |A^B| U |B-A|

Front 7

Principle of Inclusion and Exclusion (for two sets)

Back 7

|AUB|=|A| + |B| - |A^B|

Front 8

Principle of Inclusion and Exclusion (for 3 sets)

Back 8

|AUBUC|=|A|+|B|+|C|-|A^B|-|A^C|- |B^C|+ |A^B^C|

Front 9

general pattern for inclusion/exclusion

Back 9

add the singletons

subtract pairs

add triples

etc...

Front 10

Pigeonhole Principle

Back 10

If more than K objects are placed into K holes, then at least one hole has more than one objects

Front 11

Permutation

Back 11

*ordered* set of objects

formula: P(n,r) = n!/(n-r)!

where n=#of objects

r=#of selections

Front 12

Combination

Back 12

*non-ordered* set of objects

formula: C(n,r) = n!/r!(n-r)!

where n=# of objects

and r=#of selections

Front 13

Combination with replacement

Back 13

formula: Crep(n,r) = C(n+(r-1), r)

example: I rent a car from from a place with 3 cars to choose from. Later, I rent again after returning the first car so it can be rented again. How many combinations of cars are there?

C(3+(2-1),2) = C(4,2)

=4!/2!2! = 6

Front 14

Probability

Back 14

finding the chance of a particular outcome

Front 15

Sample space

Back 15

the set of all possible outcomes

Front 16

event space

Back 16

the particular outcome

Front 17

P(E) formula

Back 17

P(E) = |E|/|S|

Front 18

conditional probablility

Back 18

probability of an event happening given that some other event has already happened

notation: P(E1|E2)

formula:P(E1|E2) = P(E1^E2)/P(E1)

Front 19

Probability distribution

Back 19

collection of certain outcomes; used when not all outcomes are equally likely

Front 20

Expected Value

Back 20

average(mean)/weighted value

notation: E(x)

Defn: Sum (Value xi) P(xi)

**make table of xi and P(xi) then add

Front 21

Binomial theorem

Back 21

formula: C(n,0)a^n b^0 + C(n,1)a^(n-1) b^1....

**a's decrease from first exponent, b's increase from starting at 0

Front 22

Binary Relation

Back 22

Produces items in a subset of SXS and involve 2 tuples

Front 23

Binary Relation classifications

Back 23

1. One-to-many: at least 1 element of S appears twice

2. One-to-One: each 1st and 2nd component of tuples is only appearing once

3. Many-to-One: at least one element of the second set appears twice

4. Many-to-Many: duplication of some S and some T elements

Front 24

Symmetric (relation property)

Back 24

if x is related to y, then y is related to x

ex:

S={1,2,3,4,5,6}

p={(1,2)(2,1)}

Front 25

reflexive (relation property)

Back 25

each x must be related, and one of its relatives must be itself

ex:

S={1,2,3}

P={(1,1)(2,2)(3,3)}

Front 26

transitive (relation property)

Back 26

if x is related to y and y is related to z then x must also be related to z

ex:

S={1,2,3,4,5,6}

p={(1,1)(1,2)(2,1)(2,2)}

Front 27

anti-symmetric (relation property)

Back 27

if x is related to y and y is related to x then x=y

example:

S={1,2}

p={(1,1)}

Front 28

Extension

Back 28

a new relation that's a superset of another relation

Front 29

closure

Back 29

the smallest possible extension of a set

Front 30

set partition

Back 30

collection of subsets (of some sets) whose union with S is with:

1. each subset is non-empty

2. no overlap between subsets

Front 31

block

Back 31

one of the sets making up a partition

Front 32

equivalence relation

Back 32

binary relation that is: reflexive, symmetric and transitive

Front 33

equivalence class

Back 33

set of items that an item is related to

notation: [...]

formal definition: given some element a that is in S, [a]={b|b is an element of S and a is related to b}

**each class is a block and all classes form a partition

Front 34

Partial Ordering

Back 34

binary relation that is: reflexive, anti-symmetric and transitive

notation: (S,p)

Front 35

Predecessor

Back 35

any item in the partial ordering that gets related is a predecessor

formally if (S,p) contains x related to y then x is a predecessor of y

Front 36

Hasse diagram

Back 36

graph of a partial ordering

Front 37

vertices

Back 37

elements of S

Front 38

edges

Back 38

connections showing individual element relations

Front 39

total ordering

Back 39

type of partial ordering in which every element of S is related to each other element

Front 40

minimal element

Back 40

has no predecessors except for itself

Front 41

maximal element

Back 41

has no successors except for itself

Front 42

PERT diagram

Back 42

is a Hasse diagram rotated 90 degrees clockwise and add arrows to the edges

Front 43

critical path

Back 43

path leading to completion that encompasses the minimal time to completion

**this is NOT the LEAST time to completion

Front 44

Topological sorting

Back 44

defines a way to sequence tasks to complete an activity

context: partial ordering

algorithm:

Front 45

Function

Back 45

A function f is one that maps elements of a set S to another set T, and is a subset of SXT in which each element of S is mapped to one element of T

examples are: one-to-one and one-to-many

fan out must always be one

Front 46

domain

Back 46

the source set

Front 47

co-domain

Back 47

the destination set