Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

3. Math for CS > Final > Flashcards

Final Flashcards

1
Q

Inverse of p->q

A

!p ->!q

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

contrapositive of p->q

A

!q->!p

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

converse of p->q

A

q->p

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

!ExP(x) ->?

A

Ax!P(x)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

!AxP(x) ->?

A

Ex!P(x)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

!AxP(x) with negation inside

A

Ex!P(x)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Proof by contraposition

A

p->q = !q->!p then prove this to be true

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

perfect square x

A

for some int a; x=a^2

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Proof by contradiction

A

assume false then find a case that makes it true

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

def: rational number

A

number can be stated in terms of a/b where a and b are integers and a and b are written in the lowest common term

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

def: irrational number

A

number can not be stated in terms of a/b where a and be are integeres

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

prove if n=ab then (a <= sqr(n))

A 
proof by contradiction
a>sqr(n) and b>sqr(n)
a>sqr(n) > 0         b > sqr(n) > 0
s > x > 0              t > y > 0
st>xy
ab>n contradiction
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

if n^2 is odd prove n is odd

A

suppose n is even
n=2k ; n^2 = 4k^2
2*(2k^2) so is even
proof by contraposition

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

prove sqr(2) is irrational by contradiction

A 
suppose sqr(2) is rational
sqr(2) = a/b
2 = a^2/b^2
2b^2 = a^2 so a is even
a=2c
2b^2 = 4c^2
b^2=2c^2 so b is even
then a and b share common factor b CONTRADICTION
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

prove sum of rational and irrational is irrational

A

contradiction:
x=r;y=i;z=r
x+y=z; y=z-x; x = z +(-x)
a/b + c/d = ad+cb/bd which is rational

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

prove product of 2 rational is rational

A

a/b * b/c = ab/bc which is rational

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

prove product of 2 irrational is irrational

A

sqr(2) * sqr(2) = 2 contradiction

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

if a < b prove average of a and b is > a

A

b = a + x
average = (a + a + x)/2
2a/2 + x/2 = a+x/2
x/2 > 0 so true

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

prove if x is rational x/2 is ratinal

A

x=a/b

2a/b is rational

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

prove if x is rational then 3x-1 is rational

A

x=a/b
3a/b -1
3a/b -b/b
3a-b/b is rational

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q 
Identify the following sets
N:
Z:
Z+:
Q:
R:
R+:
C:
A 
N: 0,1,2,3
Z:integers
Z+: positive integers
Q:rational numbers
R:real numbers
R+:real positive number
C:complex numbers
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

def subset

A

every element of A is in B

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

def strict subset

A

every element of A is in B but there exists an element in B which is not in A

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

def: power set

A

all subsets of given set

{0,1} = {{o},{0},{1},{0,1}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

def Cartesian Product

A

A x B = {(a,b) | a∈A ^ b∈B}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

def: union of sets

A

a set that contains elements in A or B or both

A u B = {x| x∈A v x∈b}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

def intersection of sets

A

set contains elements in both A and B

A n B = {x| x∈A ^ x∈B}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

def: disjoint sets

A

intersection of sets is empty

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

def: complement set

A

ā = { x∈U | x !∈ a}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

def: difference of A and B

A

A-B = {x | x∈A ^ x!∈B}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

prove (A n B) is a subset (<=) A

A

A n B -> x∈A ^ x ∈ B -> x ∈ A

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

prove A-B subset of A

A

(A-B)-> x∈A ^ x !∈B -> x∈A

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

prove A n (B-A) = 0

A 
A n (B-A) = A n (B ^ !A) 
A n B n !A = A n !A = 0
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

prove A u (B-A) = A u B

A

Au(B-A) = A u (B ^ !A

A u B u(A ^ !A) = A u B

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

does A=B if A u C=B u C

A

no if A={1,2} ;B = {3} ;C={1,2,3}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

does A=B if A n C = B n C

A

no, what if A and C have different members both not in C

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
37
Q

does A=B if
1. Auc = Buc
and
2. AnC=BnC

A

yes
1. implies A and B don’t have members different outside of wahts in C
2. implies A and B dont have different numbers besides whats outside of C
Thus they must be the same

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
38
Q

How many different three letter initials with none of the leters repeated can people have

A

26x25x24

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
39
Q

How many bit strings of length n where n is a positive integer start and end with 1s

A

2^(n-2) + 1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
40
Q

How many strings are there of four lowercase letters that have the letter x in them

A

26^4 -25^4(all strings possible - all strings without the letter x

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
41
Q

How many positive integers between 1000 and 9999 are divisible by 9

A

9999/9 - 999/9all divisible by 9 - lower than 1000 divisible by 9

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
42
Q

How many positive integers between 1000 and 9999 are even

A

9999/2 - 999/2all even - even below 1000

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
43
Q

How many positive integers between 1000 and 9999 have distinct digits

A

9x9x8x7(1-9)x(0-8)x8x7

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
44
Q

How many positive integers between 1000 and 9999 are not divisible by 3

A

(9999-999) - (9999/3 - 999/3)all integers - integers divisible by 3

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
45
Q

How many positive integers between 1000 and 9999 are divisible by 5 or 7

A

(9999/5-999/5) + (9999/7+999/7) -(9999/35 - 999/35)all divisible by 5 + all divisible by 7 - all divisible by both

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
46
Q

How many positive integers between 1000 and 9999 are divisible by 5 but not by 7

A

(9999/5-999/5) -(9999/35 - 999/35)all divisible by 5 - all divisible by 5 and 7

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
47
Q

How many positive integers between 1000 and 9999 are divisible by 5 and 7

A

(9999/35 - 999/35)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
48
Q

How many subsets of a set with 100 elements have more than one element

A

2^100 - 101all possible - 100 1 elements sets and 1 empty set

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
49
Q

A palindrome is a string whos reversal is identical to the string, how many bit strings of length n are palindromes

A

(2^n/2)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
50
Q

In how many ways can a photographer at a wedding arrange 6 people in a row from a group of 10 people, where the bride an d groom are among these 10 people if the bride must be in the picture

A

6(9x8x7x6x5)(1x9x8x7x6x5) + (9x1x8x7x6x5) + (9x8x1x7x6x5) + (9x8x7x1x6x5) + 9x8x7x6x1x5) + (9x8x7x6x5x1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
51
Q

In how many ways can a photographer at a wedding arrange 6 people in a row from a group of 10 people, where the bride an d groom are among these 10 people if the bride is not next to the groom

A

(5x6)(8x7x6x5)first place 4 that are not bride and groom, then place bride in 1 of 5 places then the groom in 1 of 6 places

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
52
Q

In how many ways can a photographer at a wedding arrange 6 people in a row from a group of 10 people, where the bride an d groom are among these 10 people if exactly one of the bride and the groom is in the picture

A

(8x7x6x5x4)x(2x6)Pick the other 5 people out of 8 then pick bride or groom then put it in one of the 6 possible places

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
53
Q

How many bit strings of length 10 contain either 5 consecutive 0s or 5 consecutive 1s

A

6(2^6)6 possible locations for the string of 5, then possible choices for 5 other bits and if the string is 1 or 0

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
54
Q

Show that among any group of five integers there are two with the same remainder when divided by 4

A

Since there are only 4 outcomes when divided by 4 {0,1,2,3} and there are 5 numbers, it must be the case via the pigeonhole principle that two have the same remainder

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
55
Q

Show that any group of d+1 integers there are two with exactly the same remainder when they are divided by d

A

The possible remainders when divided by d are {0,1,2,…,d-1} which are d in total. since we check d+1 options it must be the case that two have the same remainder via the pigeonhole principle

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
56
Q

Given a set of 5 distinct integer coordinates on the xy plane, show that the midpoint of the line joining at least one pair of these points has an integer coordinate

A

There are only 4 types of points that can occur {(even, odd),(even,even),(odd,odd),(odd,even)}. As we can see that the mid pint on any two of the same would be integers. Via the pigeonhole principle it must be the case that we have a midpoint that lies on integers

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
57
Q

if there are 101 people of different heights standing in line it is possible to find 11 people that are in order of increasing or decreasing

A

theorem: every sequence of n^2+1 distinct real numbers contains a sub sequence of n+1 that is either strictly increasing or decreasing

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
58
Q

How many bit strings of length 12 contain exactly three 1s

A

C(12,3)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
59
Q

How many bit strings of length 12 contain at most three 1s

A

C(12,0) + C(12,1) + C(12,2) + C(12,3)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
60
Q

How many bit strings of length 12 contain at least 3 1s

A

2^12 - (C(12,1) + C(12,2) + C(12,0))

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
61
Q

How many bit strings of length 12 contain an equal number of 0s and 1s

A

C(12,6)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
62
Q

Coin flipped eight times, how many possible outcomes in total

A

2^8

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
63
Q

Coin flipped eight times, how many possible outcomes contain three heads

A

C(8,3)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
64
Q

Coin flipped eight times, how many possible outcomes contain at least three heads

A

2^8 - (C(8,0) + C(8,1) + C(8,2))total - - 0 head -1 head - 2 head

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
65
Q

Coin flipped eight times, how many possible outcomes contain the same number of heads and tails

A

C(8,4)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
66
Q

How many bit strings of length 10 have exactly three 0s

A

C(10,3)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
67
Q

How many bit strings of length 10 have more 0s than 1s

A

C(10,6) + C(10,7) + C(10,8) + C(10,9) + C(10,10)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
68
Q

How many bit strings of length 10 have at least seven 1s

A

C(10,7) + C(10,8) + C(10,9) + C(10,10)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
69
Q

How many bit strings of length 10 have at least three 1s

A

C(10,3) + C(10,4) + C(10,5) + C(10,6) + C(10,7) + C(10,8) + C(10,9) + C(10,10)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
70
Q

How many permutations of the letters ABCDEFGH contain the string ED?

A

7!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
71
Q

How many permutations of the letters ABCDEFGH contain the string CDE?

A

6!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
72
Q

How many permutations of the letters ABCDEFGH contain the string BA and FGH?

A

5!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
73
Q

How many permutations of the letters ABCDEFGH contain the string AB, DE and GH?

A

5!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
74
Q

How many permutations of the letters ABCDEFGH contain the string CAB and BED?

A

4!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
75
Q

How many permutations of the letters ABCDEFGH contain the string BCA and ABF?

A

none since the b would never line up

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
76
Q

How many ways to order 10 women and six men

A

10! x C(11,6) x 6!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
77
Q

Ways to form a committee of 6 with 15 women and 10 men with more women then men

A

C(15,6) + C(15,5)C(10,1) + C(15,4)C(10,2)

78
Q

{(2,2),(2,3),(2,4),(3,2),(3,3),(3,4)}reflexive, symmetric, antisymmetric, transitive?

A

transitive

79
Q

{(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)}reflexive, symmetric, antisymmetric, transitive?

A

reflexive, transitive, symmetric

80
Q

{(1,1),(2,2),(3,3),(4,4)reflexive, symmetric, antisymmetric, transitive?

A

reflexive, symmetric, antisymmetric, transitive

81
Q

a is taller than breflexive, symmetric, antisymmetric, transitive?

A

transitive, antisymmetric

82
Q

a and b were born on the same dayreflexive, symmetric, antisymmetric, transitive?

A

reflexive, symmetric, transitive

83
Q

a has the same first name as breflexive, symmetric, antisymmetric, transitive?

A

reflexive, symmetric, transitive

84
Q

a and b have a common grandparentreflexive, symmetric, antisymmetric, transitive?

A

reflexive, symmetric

85
Q

x + y = 0reflexive, symmetric, antisymmetric, transitive?

A

symmetric

86
Q

x = +-yreflexive, symmetric, antisymmetric, transitive?

A

reflexive, symmetric, transitive

87
Q

x=1reflexive, symmetric, antisymmetric, transitive?

A

antisymmetric, Transitive

88
Q

xy >=0

A

reflexive, symmetric

89
Q

Show that r=empty set on a nonempty set is symmetric and transitive, but not reflexive

A

answer?

90
Q

R1 a>bR2 a>=bR3 a<=bR5 a=bR6 a!=bR1 o R1

A

R1

91
Q

R1 a>bR2 a>=bR3 a<=bR5 a=bR6 a!=bR1 o R2

A

R1

92
Q

R1 a>bR2 a>=bR3 a<=bR5 a=bR6 a!=bR1 o R3

A

?

93
Q

R1 a>bR2 a>=bR3 a<=bR5 a=bR6 a!=bR1 o R4

A

R^2

94
Q

R1 = a divides bR2 = a is a multiple of bR1 u R2

A

a divides b or b divides a

95
Q

R1 = a divides bR2 = a is a multiple of bR1 n R2

A

a = b or a=-b

96
Q

if R and S are reflexive prove that R u S is reflexive

A

R and S are reflexive on Aso for all x in A, (x,x) is in R and S.

97
Q

if R and S are reflexive prove that R n S is reflexive

A

R and S are reflexive on Aso for all x in A, (x,x) is in R and S.

98
Q

Equivalence, if not what properties do they lack?a and b are the same age

A

yes

99
Q

Equivalence, if not what properties do they lack?a and b have the same parents

A

yes

100
Q

Equivalence, if not what properties do they lack?a and b share a common parent

A

no missing transitive

101
Q

Equivalence, if not what properties do they lack?a and b have met

A

no missing transitive

102
Q

Equivalence, if not what properties do they lack?a and b speak a common language

A

nomissing transitive

103
Q

Equivalence, if not what properties do they lack?f(1)=g(1)

A

equivalence????

104
Q

Equivalence, if not what properties do they lack?f(x)-g(x)=1

A

not reflexive, symmetric or transitive

105
Q

Equivalence, if not what properties do they lack?f(x)-g(x) = C

A

equivalence????

106
Q

Equivalence, if not what properties do they lack?f(0)=g(1) and f(1)=g(0)

A

not transitive or reflexive

107
Q

f A->BDomain?

A

A

108
Q

f A->Bcodomain

A

B

109
Q

f A->Bimage

A

f(a)=bb is image

110
Q

f A->Bpreimage

A

f(a)=ba is preimage

111
Q

f maps A to B

A

f is a function that connects A to B

112
Q

when are two functions equal

A

when they both have the same domain, codomain, and map each element in their domain to the same element in their codomain

113
Q

(f1+f2)(x)

A

f1(x) + f2(x)

114
Q

(f1f2)(x)

A

f1(x)*f2(x)

115
Q

one-to-one function

A

f(a)=f(b) ->a=b

116
Q

onto

A

for all b E B there is an element a E A f(a)=b

117
Q

surjective

A

a function that is onto

118
Q

one-to-one correspondence or bijection

A

if f is one-to-one and onto

119
Q

(f o g)(x)

A

f(g(x))

120
Q

floor function

A

assigns to a real number the largest integer that is less to or equal to it

121
Q

roof function

A

assigns to a real number the largest smallest integer that is greater than or equal to it

122
Q

Show that C(n,n/2) >= (2^n)/n

A

C(n,n/2) is the middlemost element in the binomial equation. 2^n is the sum of an entire level of the binomial equation, and when divided by n it is the average of all elements. Since the middlemost element is always larger than the average

123
Q

Combinatorial proof:k(n choose k) = n((n-1) choose (k-1))

A

LHS: choose k elements then choose 1 out of the kRHS: choose 1 element then choose the k-1 others

124
Q

(n choose r)(r choose k) = (n choose k)((n-k) choose (r-k))

A

LHS:choose set r then from r choose subset kRHS:Choose subset then choose the remaining for larger set

125
Q

variety of ways to choose a dozen donuts from 20 varieties if there are no two donuts of the same variety

A

C(20,12)

126
Q

variety of ways to choose a dozen donuts from 20 varieties if all donuts are of the same variety

A

C(20,1)

127
Q

variety of ways to choose a dozen donuts from 20 varieties if there are no restrictions

A

c(12+20-1,12)choices plus varieties -1 choose choices

128
Q

r-combinations of a set with n elements when repetition is aloud

A

C(n+r-1,r)

129
Q

variety of ways to choose a dozen donuts from 20 varieties if there are at least two varieties among the dozen donuts chosen

A

C(12+20-1,r) -20all permutations minus 20 where they are all the same type

130
Q

variety of ways to choose a dozen donuts from 20 varieties if theree must be at least six blueberry filled donuts

A

C(6+20-1,6)

131
Q

variety of ways to choose a dozen donuts from 20 varieties if theree can be no more than six blueberry filled donuts

A

C(12+20-1,12) - C(5+20-1,5)

132
Q

C(x,y)

A

x!/((y!)(x-y)!)

133
Q

Def Tree:

A

A connected, undirected graph with no simple circuits

134
Q

an undirected graph is a tree iff

A

there is a unique simple path between any two of its vertices

135
Q

Def Rooted Tree:

A

a tree in which one vertex has been designated as the root and every edge is directed away from the root

136
Q

Def m-ary tree

A

if every internal vertex has no more than m children

137
Q

def Full m-ary Tree

A

if every internal vertex has exactly m children

138
Q

internal vertex

A

a vertex that has children

139
Q

A tree with n vertices has how many edges

A

n-1

140
Q

A full m-ary tree with i internal vertices contains how many vertices

A

mi+1 vertices

141
Q

A full m-ary tree with n vertices has how many internal vertices, how many leaves

A

(n -1)/m internal vertices and n-internal vertices leaves

142
Q

A full m-ary tree with i internal vertices has how many vertices

A

mi+1

143
Q

How many ways are there to arrange the letters in THANKSGIVING

A

12!/((2!)(2!)(2!))divided by 2! for doubles of letters

144
Q

How many ways are there to arrange the letters in THANKSGIVING that start with a T

A

11!/((2!)(2!)(2!))

145
Q

How many ways are there to arrange the letters in THANKSGIVING contain the word HAT

A

10!/((2!)(2!)(2!))

146
Q

How many ways are there to arrange the letters in THANKSGIVING where the two G’s are not next to each other

A

???

147
Q

How many ways are there to arrange the letters in THANKSGIVING where the vowels are in alphabetical order

A

???

148
Q

How many different functions are there from a set of 5 elements to a set of 6

A

6^5

149
Q

How many functions from a 5 element set too a 6 element set are 1-1

A

6x5x4x3x2

150
Q

How many functions from a 5 element set to a 6 element set are onto

A

This is not possiible because a function only has 1 output so 5 functions could not output 6 answers

151
Q

How many different relations are there from a 5 element set to a 6 element set

A

2^(5*6)

2 because its either in or not in the set

152
Q

How many reflexive relations are there from a 5 element set to a 6 element set

A

5 at most

153
Q

Prove or Disprove: if the relation R1 and R2 are symmetric, then so is R1 n R2

A

AaEA AbEB if (a,b) E R1 ->(a,b) E R1 and (a,b)E R2 -> (b,a)E R2 since
so it must be the case (a,b) E R1nR2->(b,a)E R1nR2

154
Q

Prove or Disprove: if the relation R1 and R2 are transitive, then so is R1 n R2

A

AaAbAc{abc|(((a,b)E R1^(b,c)E R1)-> (a,c)E R1) ^ ((a,b)E R2^(b,c)E R2)-> (a,c)E R2) then it must be the case tha
((a,b)E R1nR2 ^(b,c)E R1nR2)-> (a,c)E R1nR2)

155
Q

Could the following degree sequences be a simple graph:

2,3,3,3,4,6

A

NO degree of 6 is impossible since no loops and only 6 vertices

156
Q

Could the following degree sequences be a simple graph:

2,4,6,8,10,12

A

NO degrees higher than amoutn of verticies

157
Q

Could the following degree sequences be a simple graph:

0,1,2,2,4,5

A

No since degree of 5 implies that 1 vertice touches all others, but one of those verticies has degree 0 so this cannot be the case

158
Q

Could the following degree sequences be a simple graph:

3,3,3,3,3,3

A

YES

159
Q

if G and H are isomorphic graphs, show that !G and !H are isomorphic

A

since both graphs have matching edges, Possible^!G=G, so they have matching nonadjacencies so they must be isomorphic

160
Q

def: self complementary

A

if G and !G are isomorphic

161
Q

Show that if G is self complementary with v vertices then v % 4 = 0 or 1

A 
Eg  = c(v,2) - Eg
2Eg = v!/((v-2)!2!
4Eg=v!/(v-2)!
4Eg=v(v-1)
???????
162
Q

Def: Adjacency Matrix

A 
[0110]
[1001]
[1001]
[0110]
graphs shoowing which vertices connect 
vertices x vertices
163
Q

Def: Adjacency List

A

list of vertices and the ones t hey connect to

ex: vertex A –> b,c,d

164
Q

Def: Incidence matrices

A

same as adjacency Matrix except Vertices x edges

165
Q

Def: Isomorphic

A

There exists a function that is 1-1 and onto that can trun one graph into the other
basically they are the same graph drawn differently

166
Q

Def: graph invarient

A

A property reserved by isomorphism of graphs

ex: same number of degrees, or vertices

167
Q

Def: Planar Graph

A

a graph that can be drawn on a plane without any edges overlapping

168
Q

A graph is nonplanar if it contains either of these 2 subgraphs

A

k(5) and k(3,3)

169
Q

Def: Eulers Formula

A

Regions = edges- vertices+2

170
Q

G is connected planar graph with e edges and vertices where v>=3 then ?

A

e <= 3y-6

171
Q

G is connected planar graph with e edges and vertices where v>=3 and no circuits then ?

A

e<=2v-4

172
Q

Suppose that a connected bipartite planar simple graph has e edges and v vertices, show that e=3

A 
since bipartite  all faces have 4 edges or g
each edge used for 2 faces
4r=e-v+2 // *2
e >= 2e -2v + 4 //-2e
-e >= -2v + 4 //*-1
e <= 2v -4
173
Q 
By removing 1 vertices and all connecting edges can you make these graphs planar
K5
K6
K3,3
K3,4
A

K5 yes
K6 no
K3,3 yes
K3,4 depends which you remove

174
Q

Show that a simple graph with a circuit that has an odd number of vertices in it cannot be colored by 2 colors

A

????

175
Q

Def: Uniform Distribution of probability

A

each possible outcome is 1/n

176
Q

Complement of probability

A

p(!E) = 1-p(E)

177
Q

p(E1 u E2)

A

p(21) + p(E2) - p(E1 n E1)

178
Q

conditional probability

p(E|F)

A

P(E n F) / p(F)

179
Q

to dependents are independent iff?

A

p(EnF)= p(E)p(F)

180
Q

Mutually independent

A

p(Ei1 n Ei2 n … n Ein = p(Ei1)p(Ei2)…p(Ein)

181
Q

Bernoulli Trial

A

An experiment with two possible outcomes

ex flipping coin

182
Q

Def Mutually independent

A

The probability of success on an given trial has no bearing on the next

183
Q

Coin is flipped 7 times where the probability of heads is 2/3, what is the probability that 4 heads come up

A

C(7,4) * (2/3)^4 * (1/3)^3

184
Q

Probability of K successes out of N trials
probability of T = p
probability of F = q

A

C(N,K) * p^k * q^n-k

185
Q

What is the probability that a fair die comes up even if rolled six times

A

(1/2)^6

186
Q

What is the probability that a positive integer not exceeding 100 selected at random is divisible by 3

A

100/3
33/100 = .33
33%

187
Q

What is the probability that a positive integer not exceeding 100 selected at random is divisible by 5 or 7

A 
100/5 =  20;
100/7  = 14;
100/35 = 2
20 + 14   - 2 = 32
32/100  = .32
188
Q

Probability that 4 people win 1st,2nd,3rd,4th respectively out of 50 people if you can only win 1 prize

A

1/501/491/48*1/47

189
Q

Probability that 4 people win 1st,2nd,3rd,4th respectivly out of 50 people if you can win multiple prizes

A

(1/50)^4

190
Q

Independent?
first coin comes up heads
second coin comes up tails

A

yes
P(E1nE2) = 1/16
P(E1)p(E2) = 1/4 * 1/4 = 1/16

191
Q

Independent?

first coin

A

???

3. Math for CS (4 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions