Brainscape's Knowledge GenomeTM

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


See full index

3. Math for CS > Exam 2 > Flashcards

Exam 2 Flashcards

1
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
2
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
3
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
4
Q

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

A

9999/9 - 999/9

all divisible by 9 - lower than 1000 divisible by 9

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

How many positive integers between 1000 and 9999 are even

A

9999/2 - 999/2

all even - even below 1000

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
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
7
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
8
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
9
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
10
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
11
Q

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

A

2^100 - 101

all possible - 100 1 elements sets and 1 empty set

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
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
13
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
14
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
15
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
16
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
17
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
18
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
19
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
20
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
21
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
22
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
23
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
24
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
25
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
26
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
27
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
28
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
29
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
30
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
31
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
32
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
33
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
34
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
35
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
36
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
37
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
38
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
39
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
40
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)

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

{(2,2),(2,3),(2,4),(3,2),(3,3),(3,4)}

reflexive, symmetric, antisymmetric, transitive?

A

transitive

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

{(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)}

reflexive, symmetric, antisymmetric, transitive?

A

reflexive, transitive, symmetric

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

{(1,1),(2,2),(3,3),(4,4)

reflexive, symmetric, antisymmetric, transitive?

A

reflexive, symmetric, antisymmetric, transitive

44
Q

a is taller than b

reflexive, symmetric, antisymmetric, transitive?

A

transitive, antisymmetric

45
Q

a and b were born on the same day

reflexive, symmetric, antisymmetric, transitive?

A

reflexive, symmetric, transitive

46
Q

a has the same first name as b

reflexive, symmetric, antisymmetric, transitive?

A

reflexive, symmetric, transitive

47
Q

a and b have a common grandparent

reflexive, symmetric, antisymmetric, transitive?

A

reflexive, symmetric

48
Q

x + y = 0

reflexive, symmetric, antisymmetric, transitive?

A

symmetric

49
Q

x = +-y

reflexive, symmetric, antisymmetric, transitive?

A

reflexive, symmetric, transitive

50
Q

x=1

reflexive, symmetric, antisymmetric, transitive?

A

antisymmetric, Transitive

51
Q

xy >=0

A

reflexive, symmetric

52
Q

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

A

answer?

53
Q 
R1 a>b
R2 a>=b
R3 a<b><=b
R5 a=b
R6 a!=b

R1 o R1</b>

A

R1

54
Q 
R1 a>b
R2 a>=b
R3 a<b><=b
R5 a=b
R6 a!=b

R1 o R2</b>

A

R1

55
Q 
R1 a>b
R2 a>=b
R3 a<b><=b
R5 a=b
R6 a!=b

R1 o R3</b>

A

?

56
Q 
R1 a>b
R2 a>=b
R3 a<b><=b
R5 a=b
R6 a!=b

R1 o R4</b>

A

R^2

57
Q 
R1 = a divides b
R2 = a is a multiple of b

R1 u R2

A

a divides b or b divides a

58
Q 
R1 = a divides b
R2 = a is a multiple of b

R1 n R2

A

a = b or a=-b

59
Q

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

A

R and S are reflexive on A

so for all x in A, (x,x) is in R and S.

60
Q

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

A

R and S are reflexive on A

so for all x in A, (x,x) is in R and S.

61
Q

Equivalence, if not what properties do they lack?

a and b are the same age

A

yes

62
Q

Equivalence, if not what properties do they lack?

a and b have the same parents

A

yes

63
Q

Equivalence, if not what properties do they lack?

a and b share a common parent

A

no

missing transitive

64
Q

Equivalence, if not what properties do they lack?

a and b have met

A

no

missing transitive

65
Q

Equivalence, if not what properties do they lack?

a and b speak a common language

A

no

missing transitive

66
Q

Equivalence, if not what properties do they lack?

f(1)=g(1)

A

equivalence????

67
Q

Equivalence, if not what properties do they lack?

f(x)-g(x)=1

A

not reflexive, symmetric or transitive

68
Q

Equivalence, if not what properties do they lack?

f(x)-g(x) = C

A

equivalence????

69
Q

Equivalence, if not what properties do they lack?

f(0)=g(1) and f(1)=g(0)

A

not transitive or reflexive

70
Q

f A->B

Domain?

A

A

71
Q

f A->B

codomain

A

B

72
Q

f A->B

image

A

f(a)=b

b is image

73
Q

f A->B

preimage

A

f(a)=b

a is preimage

74
Q

f maps A to B

A

f is a function that connects A to B

75
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

76
Q

(f1+f2)(x)

A

f1(x) + f2(x)

77
Q

(f1f2)(x)

A

f1(x)*f2(x)

78
Q

one-to-one function

A

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

79
Q

onto

A

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

80
Q

surjective

A

a function that is onto

81
Q

one-to-one correspondence or bijection

A

if f is one-to-one and onto

82
Q

(f o g)(x)

A

f(g(x))

83
Q

floor function

A

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

84
Q

roof function

A

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

85
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

86
Q

Combinatorial proof:

k(n choose k) = n((n-1) choose (k-1))

A

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

87
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 k
RHS:Choose subset then choose the remaining for larger set

88
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)

89
Q

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

A

C(20,1)

90
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

91
Q

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

A

C(n+r-1,r)

92
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) -20

all permutations minus 20 where they are all the same type

93
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)

94
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)

95
Q

C(x,y)

A

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

96
Q

Def Tree:

A

A connected, undirected graph with no simple circuits

97
Q

an undirected graph is a tree iff

A

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

98
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

99
Q

Def m-ary tree

A

if every internal vertex has no more than m children

100
Q

def Full m-ary Tree

A

if every internal vertex has exactly m children

101
Q

internal vertex

A

a vertex that has children

102
Q

A tree with n vertices has how many edges

A

n-1

103
Q

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

A

mi+1 vertices

104
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

105
Q

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

A

mi+1

106
Q

How many ways are there to arrange the letters in THANKSGIVING

A

12!/((2!)(2!)(2!))

divided by 2! for doubles of letters

107
Q

How many different ways to spell THANKSGIVING start with T

A

11!/(2!)(2!)

3. Math for CS (4 decks)

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