Description
Toggle Drawer
Overview
Refresh a company’s computer network memory with respect to number representation conversions, decimal to binary and hexadecimal (and vice versa), using your ability to apply number representation and theory. Then, use discrete probability to assess the risk of a hacker foiling the company network’s RSA encryption.
The assessment focuses on number theory, discrete probability theory, counting rules, permutations, and combinations.
Context
The
Assessment 2 Context
document contains additional information about set and probability theory, permutations and combinations, and cryptography.
Resources
Suggested Resources
The following optional resources are provided to support you in completing the assessment or to provide a helpful context. For additional resources, refer to the Research Resources and Supplemental Resources in the left navigation menu of your courseroom.
Capella Resources
Assessment 2 Context
.
SHOW LESS
Capella Multimedia
Click the links provided below to view the following multimedia pieces:
The Counting Principle
|
Transcript
.
This presentation introduces the following topics:
Multiplication and addition principles.
Permutations and combinations.
Catalan numbers.
Discrete probability.
Conditional probability.
Pigeonhole principle.
Library Resources
The following e-book from the Capella University Library is linked directly in this course:
Koshy, T. (2004).
Discrete mathematics with applications
.
Burlington, MA: Elsevier Academic Press.
Chapter 6.
Bookstore Resources
The resource listed below is relevant to the topics and assessments in this course and is not required. Unless noted otherwise, this resource is available for purchase from the
Capella University Bookstore
. When searching the bookstore, be sure to look for the Course ID with the specific
–FP
(FlexPath) course designation.
Johnsonbaugh, R. (2018).
Discrete mathematics
(8th ed.). New York, NY: Pearson.
Chapter 6, “Counting Methods and the Pigeonhole Principle,” sections 6.1, 6.2, 6.3, 6.5, and 6.6, are particularly useful for your work in this assessment. Topics in these sections include permutations, combinations, discrete probabilities, and discrete probability theory.
Assessment Instructions
Assume you help to oversee your company’s computer network. As such, it is important for you to understand and be able to apply number representation and number theory, as well as other IT concepts.
Part 1: Number Representation (application to binary encoding) and Combinatorics (application to IP network addressing)
Note
: For each of the following, you must show your work for credit.
Given your responsibilities, you decide to refresh your memory with respect to number representation conversions: decimal to binary and hexadecimal (and vice versa). In the following questions, the base is denoted as a subscript. For example, 15
10
is 15 in decimal (base 10), 0011
2
is 3 in binary (base 2), and 1A
16
is 26 in hexadecimal (base 16).
What is the decimal representation of 10001101
2
?
What is the decimal representation of FFC6
16
?
What is the binary representation of 17C6
16
?
What is the hexadecimal representation of 11111000
2
?
According to the IP internet protocol, each IP address is represented as a binary string. In IPv4 (Internet protocol version 4), a 32-bit binary string is used. For example, 00000011.00000111.00000000.11111111, which is often presented in dotted decimal: 3.7.0.255.
In mathematics, the study of combinations refers to the number of ways one can select items from a group disregarding order; the study of permutations refers to the number of ways one can permute, or arrange, items into a sequence. Given that each entry in a binary string must be either a 1 or a 0, what is the total number of addresses that can be encoded using a 32-bit binary string? Is this a combination or permutation problem? Justify your answer.
In IPv6, 128 bit, binary strings are used for addressing. How many addresses can be encoded using 128 bits? Is this a combination or permutation problem? Justify your answer.
In IPv4, how many addresses contain exactly eight 1s?
Part 2: Number Theory and Discrete Probability (application to encryption)
Note
: For each of the following, you must show your work for credit. Some questions also require you to justify your answer.
Network security and encryption is also a concern of a network administrator. Many encryption schemes are based on number theory and prime numbers; for example, RSA encryption. These methods rely on the difficulty of computing and testing large prime numbers. (A prime number is a number that has no divisor except for itself and 1.)For example, in RSA encryption, one must choose two prime numbers,
p
and
q
; these numbers are private but their product,
z = pq,
is public. For this scheme to work, it is important that one cannot easily find
p
or
q
given
z
, which is why
p
and
q
are generally large numbers.
Choose an example of
p
and
q
and compute their product
z
. Justify your selection.
Assume that you wish to make a risk assessment and you wish to determine how probable it may be for a hacker to determine
p
and q from
z
. You wish to use discrete probability for this computation. For the sake of example, you choose to assess z = 502,560,410,469,881. Say that a hacker will attempt to find
p
and thus
q
by randomly selecting a potential divisor and testing to see if it divides 502,560,410,469,881. (You know that
p
= 15,485,867 and
q
= 32,452,843, but the hacker does not.) For example, the hacker may choose 1021; however, upon inspection the hacker will see that 1021 does not divide
z
.
For all questions below, please show all your work and/or justify your answers.
Given this problem, what is the sample space of the problem?
Hint:
In this context, the sample space is the set of all possible values that the hacker may select.
Given the sample space defined above, what events correspond to a successful guess by the hacker?
Hint
: An event is a subset of the sample space.
Given the above, what is the probability that the hacker will successfully guess
p
and/or
q
?
Assume the hacker selects five numbers to test.
What is the probability that all five attempts will fail? Show your work.
What is the probability that one of the five attempts will succeed? Show your work.
Counting, Combinations, and Permutations Scoring Guide
Criteria
DISTINGUISHED
Convert numbers to different representations.
Converts numbers to different number representations and analyzes the utility of these number representations within the context of computing.
Compute combinations and/or permutation.
Computes and explains combinations and/or permutation and integrates IT scenario into explanation.
Apply number theory to encryption.
Applies number theory to encryption and evaluates prime number selections within the context of encryption.
Compute discrete probability.
Analyzes computational design within context of encryption by constructing a sample space of minimal size, and computes discrete probability.
Combine discrete probability.
Combines discrete probability and assesses the result within the context of encryption.
1/24/2021
Assessment 2 Context
Print
Assessment 2 Context
First, let us think about basic discrete (non-continuous) probability using a standard deck of playing cards. We
know there are 52 cards, 13 different values from 2 to ace, and four suits (that is, clubs, spades, hearts, and
diamonds). Many probability questions can be asked about a deck of cards. For example, what is the probability
that a card you choose is a queen?
P(card = queen).
We know there are 52 cards and four queens.
P(card = queen) = 4/52.
We can extend this concept to multiple events. What is the probability of choosing two cards and both are queens?
P(card1 = queen) AND P(card2 = queen).
Notice the AND. A concept called the multiplication principle that considers the results of more than one event
occurring together.
P(card1 = queen) AND P(card2 = queen) = 4/52 * 3/51 = 12/2,652.
We used multiplication in this case and did not replace the first card after choosing it.
Similarly, the addition principle is used for independent events such as the probability of choosing a card and it
being a queen OR a king.
P(card1 = queen) OR P(card1 = king) = 4/52 + 4/52 = 8/52.
Set Theory and Probability Theory
Set theory and probability theory are interrelated. An event can be thought of as a set of possible outcomes. For
example, rolling one six-sided die is an event. This event is discrete because each outcome is a whole number (that
is, no fractions or decimals).
The sample space S = {1, 2, 3, 4, 5, 6}.
Rolling a die is an event that offers a set of six possible outcomes as noted above. This set can be named E. A
sample space S, also called the universe of values, is the set of all possible outcomes. Given both E and S, the
probability of event E occurring can be computed as follows:
P(E) = |E| / |S|
An event is the outcome or outcomes of a trail. For any event E in a given sample space, a function P, known as
the probability function, assigns a value to P( E).
Note that: 0 ≤ P( E) ≤ 1.
This tells us that the probability of any event must be between 0 and 1 (or 0% chance to 100% chance).
For example, let S be a sample space with all possible values of rolling a six-sided die:
S = {1, 2, 3, 4, 5, 6}.
Let E = {4}.
https://courserooma.capella.edu/bbcswebdav/institution/MAT-FP/MAT-FP2051/180700/Course_Files/cf_assessment_2_context.html
1/2
1/24/2021
Assessment 2 Context
P(E) = |{1}| / |{1,2,3,4,5,6}| = 1/6, which is between 0 and 1.
Permutations and Combinations
A permutation is the number of possible ways of rearranging a discrete set (no decimals or fractions) of objects.
For example, if someone gave you four pictures to hang on the wall and asked how many ways you could hang
them in a straight line, you would say:
P(4, 4) = 4! = 4 * 3 * 2 * 1 = 24 ways.
The P(4, 4) notation reads, “4 items, permute all 4 of them.” The 4! reads, “4 factorial” and is a discrete function.
The general notation of permutation is P( n, r), given n objects, how many ways can you permute r of them.
P(n,r) = n!/(n-r)!
A combination is the number of ways you can select a set of objects when the order does NOT matter. The notation
is C( n, k) and is read “n choose k”.
C(n,k) = n!/[(n- k)! k!]
Cryptography
The word cryptography comes from the word cryptic, which means hidden. Cryptography focuses on encrypted
and decrypted information that is intended only for the receiver. E-mail systems, such as Hotmail, claim to use
encryption. Cryptography uses many areas of discrete math, including modulus, prime factorization, and greatest
common divisors.
https://courserooma.capella.edu/bbcswebdav/institution/MAT-FP/MAT-FP2051/180700/Course_Files/cf_assessment_2_context.html
2/2
1/24/2021
Assessment 2 Context
Print
Assessment 2 Context
First, let us think about basic discrete (non-continuous) probability using a standard deck of playing cards. We
know there are 52 cards, 13 different values from 2 to ace, and four suits (that is, clubs, spades, hearts, and
diamonds). Many probability questions can be asked about a deck of cards. For example, what is the probability
that a card you choose is a queen?
P(card = queen).
We know there are 52 cards and four queens.
P(card = queen) = 4/52.
We can extend this concept to multiple events. What is the probability of choosing two cards and both are queens?
P(card1 = queen) AND P(card2 = queen).
Notice the AND. A concept called the multiplication principle that considers the results of more than one event
occurring together.
P(card1 = queen) AND P(card2 = queen) = 4/52 * 3/51 = 12/2,652.
We used multiplication in this case and did not replace the first card after choosing it.
Similarly, the addition principle is used for independent events such as the probability of choosing a card and it
being a queen OR a king.
P(card1 = queen) OR P(card1 = king) = 4/52 + 4/52 = 8/52.
Set Theory and Probability Theory
Set theory and probability theory are interrelated. An event can be thought of as a set of possible outcomes. For
example, rolling one six-sided die is an event. This event is discrete because each outcome is a whole number (that
is, no fractions or decimals).
The sample space S = {1, 2, 3, 4, 5, 6}.
Rolling a die is an event that offers a set of six possible outcomes as noted above. This set can be named E. A
sample space S, also called the universe of values, is the set of all possible outcomes. Given both E and S, the
probability of event E occurring can be computed as follows:
P(E) = |E| / |S|
An event is the outcome or outcomes of a trail. For any event E in a given sample space, a function P, known as
the probability function, assigns a value to P( E).
Note that: 0 ≤ P( E) ≤ 1.
This tells us that the probability of any event must be between 0 and 1 (or 0% chance to 100% chance).
For example, let S be a sample space with all possible values of rolling a six-sided die:
S = {1, 2, 3, 4, 5, 6}.
Let E = {4}.
https://courserooma.capella.edu/bbcswebdav/institution/MAT-FP/MAT-FP2051/180700/Course_Files/cf_assessment_2_context.html
1/2
1/24/2021
Assessment 2 Context
P(E) = |{1}| / |{1,2,3,4,5,6}| = 1/6, which is between 0 and 1.
Permutations and Combinations
A permutation is the number of possible ways of rearranging a discrete set (no decimals or fractions) of objects.
For example, if someone gave you four pictures to hang on the wall and asked how many ways you could hang
them in a straight line, you would say:
P(4, 4) = 4! = 4 * 3 * 2 * 1 = 24 ways.
The P(4, 4) notation reads, “4 items, permute all 4 of them.” The 4! reads, “4 factorial” and is a discrete function.
The general notation of permutation is P( n, r), given n objects, how many ways can you permute r of them.
P(n,r) = n!/(n-r)!
A combination is the number of ways you can select a set of objects when the order does NOT matter. The notation
is C( n, k) and is read “n choose k”.
C(n,k) = n!/[(n- k)! k!]
Cryptography
The word cryptography comes from the word cryptic, which means hidden. Cryptography focuses on encrypted
and decrypted information that is intended only for the receiver. E-mail systems, such as Hotmail, claim to use
encryption. Cryptography uses many areas of discrete math, including modulus, prime factorization, and greatest
common divisors.
https://courserooma.capella.edu/bbcswebdav/institution/MAT-FP/MAT-FP2051/180700/Course_Files/cf_assessment_2_context.html
2/2
1/24/2021
The Counting Principle Transcript
Capella University
The Counting Principle
The Counting Principle
Greetings everyone and welcome to the Counting Principle Sessions! In this unit, we are going to
cover the counting methods, counting principles, the pigeonhole principles, permutations,
combinations, and discrete probability.
So what are the basic principles? There are two basic principles that you will need to understand in
this unit to be able to move forward and have a good grasp. The first one is called the
“multiplication principle.” What is the multiplication principle? If an activity can be performed in k
successive steps, where step 1 can be done in n ways, step 2 can be done in n ways, step k
can be done in n ways, then the number of different ways that the activity can be performed is
n ⋅ n ⋯n .
1
2
k
1
2
k
Another very important principle that we need to talk about is called the “Addition Principle.” The
addition principle states that let X ⋅ X ⋯ X , be a collection of k pairwise disjoint sets, so they
are pairwise disjoint sets. Each of which has n elements, where 1 ≤ j ≤ k , then the union of
1
2
k
j
those sets can be expressed as X
k
=
∪ Xj
, and it has n
1
+ n2 + ⋯ + nk
elements.
j=1
Permutations
So what is a permutation?
A permutation of n distinct elements, which we can represent as x , x … x , is n ordering, that
is the keyword here, ordering of the n elements. There are n! permutations of n elements. So, let
us take an example here.
1
2
n
There are 3! = 6 permutations of 3 elements, a , b , and c . So, let us see how we can make the 6
different permutations. The first one is abc . That is an easy one. And then bac , cab , acb , bca , and
cba . Notice here that order does matter in permutation.
An r -permutation of n distinct elements is an ordering of an r -element. Subset of the n
elements, x , x … x . So forr ≤ n , the number of r -permutations of a set of n distinct objects
is P (n, r) = n (n − 1) (n − 2) ⋯ (n − r + 1) .
1
2
n
Okay. So what are combinations? Now, let X = {x , x , … , x } be a set containing distinct
elements. An r -combination of X is unordered. You see, this is a keyword here, unordered. So
combinations are always unordered. It is unordered selection of r -elements of X for r ≤ n .
1
2
n
So, the number of r combinations of X is in the binomial coefficient, C (n, r)
since
n!
(
)!
= P (n, r)
=
n!
r!(n−r)!
=
P (n,r)
r!
,
.
media.capella.edu/CourseMedia/MAT2051/unit3/transcript.html
1/5
1/24/2021
s ce
The Counting Principle Transcript
.
(n, r)
(n−r)!
Catalan Numbers
The Catalan sequence was first described in the 18th century by Euler who is interested in the
number of different ways of dividing a polygon into triangles, three sides of course. So later on,
Eugene Catalan discovered the connection and he made it in parenthesized expressions. There are
many counting problems that can be solved using the Catalan numbers. So, what are the Catalan
numbers?
C (2n,n)
Catalan numbers are defined by the formula C =
. This is for n
n = 0 , C
= 1 . Alright, so let us try to calculate the rest of them.
n
n+1
= 0, 1, 2, …
. Now for
n
For n
C4 =
C7 =
= 1
, then C
1
C (8,4)
C (14,7)
8
Finally, C
10
70
=
5
5
=
=
C (2,1)
=
2
.C
= 14
3432
8
C (20,10)
11
=
2
11
8
=
=
2
252
=
6
.C
184756
.C
= 1
C (10,5)
=
5
= 429
2
=
6
C (16,8)
9
= 16796
C (4,2)
3
= 42
=
12870
9
6
=
3
.C
6
= 2
=
= 1430
.C
=
3
C (12,6)
7
.C
9
=
=
C (6,3)
4
924
7
=
20
4
= 132
C (18,9)
10
=
= 5
.
.
48620
= 4862
10
.
.
So to summarize this, the first few terms of the Catalan numbers are: For n = 0 , C = 1 . For
n = 1 , C
= 1 . For n = 2 , C
= 2 . For n = 3 , C
= 5 . For n = 4 , C
= 14 . For n = 5 ,
C
= 42 . For n = 6 , C
= 132 . For n = 7 , C
= 429 . For n = 8 , C
= 1430 . For n = 9 ,
C
= 4862 . And for n = 10 , C
= 16796 .
n
n
n
n
n
n
n
n
n
n
n
Discrete Probability
We need address some introduction to discrete probability. So to be able to start with discrete
probability, we need to make some definitions and understand them really well.
First one is called the experiment. So, what is an experiment? An experiment is a process that
yields an outcome. Second, we need to define an event. So, an event is an outcome, or set of
outcomes, from the experiment. And a very important definition here is the sample space, and you
will see that repeated a lot. The sample space is the event of all possible outcomes of that
experiment, so all possible outcomes. That is an extremely important one in probability. Okay.
So what is the probability of an event? The probability of an event is the number of outcomes in
the event. So, P
=
number of outcomes (event)
number of outcomes (sample space)
.
If S is a finite sample space and E is an event. So S here, is a finite sample space. Let us say, all
the cards in the deck. There are 52 cards so this is the finite sample space. E is an event, let us say
all the red cards and there are 26 of them. Then E is a subset of S . Then P
(E) =
|E|
|S|
. So in this
case, here we have 26 red cards out of 52 total cards in a deck so then the probability is
= /
.
/
26
52
1
2
So, when all outcomes are equally likely and there are n possible outcomes, then each outcome
has the probability of / because they are all equally likely. But this is not always the case. When
all probabilities are not equal then some probability, possibly different numbers, must be assigned
to each outcome.
1
n
media.capella.edu/CourseMedia/MAT2051/unit3/transcript.html
2/5
1/24/2021
The Counting Principle Transcript
So, probability function P is a function from the set of all outcomes, sample space is S to the
interval [0, 1] . Zero being it will never happen, one meaning it will always happen for sure. So
P : S has to be [0, 1] . The probability of an event E ⊆S is the sum of all probabilities of every
outcome in E . So P (E) = ΣP (x) where x ∈ E . So, given any two events E and E , in a
sample space S of course, then P (E ∪ E ) = P (E ) + P (E ) − P (E ∩ E ) . Think of it this
way. Let us go back to sets and draw this.
1
1
2
1
2
1
2
2
Now notice that the intersection area is shaded twice so it is as if we are counting it twice, that is
why we need to subtract it. Therefore, we need to subtract this one time so it is not counted twice
in that intersection area.
We also have an empty set or a null set, P (Φ) = 0 . Now events E and E are mutually
exclusive if and only if E ∩ E = Φ . In this case, if the intersection is Φ , if there is no
intersection, they are disconnected sets, then P (E ∪ E ) = P (E ) + P (E ) .
1
1
2
2
1
2
1
2
Conditional Probability
Conditional Probability is the probability on the event E given that another event F has occurred.
So in symbols, we write it as P
(E|F )
. So, if P
(F ) > 0
, then P
(E|F ) =
P (E∩F )
P (F )
.
Now, we also call the two events E and F independent if P (E ∩ F ) = P (E) P (F ) . Pattern
recognition places items into classes based on the various features of the items. Now given a set of
features F , we can calculate the probability of a class C given F . So, it will be P (C |F ) .
A very important theorem in conditional probability is Bayes’ theorem. Basically, given a pair-wise
disjoint classes, C , C , … , C and a feature set F , then P (C |F ) =
where
A
1
2
n
j
B
n
A = P (F |Cj ) P (Cj )
and B
= ∑ P (F |Cj ) P (Cj )
.
i=1
Now, suppose that a sequence of n items has n
the number of orderings of S is
.
j
identical objects of type j for 1
≤ j ≤ k
. Then
n!
n1 !n2 !⋯nk !
Th bi
i l h
h f
media.capella.edu/CourseMedia/MAT2051/unit3/transcript.html
l
b
db
d
i
i
i
3/5
1/24/2021
The Counting Principle Transcript
The binomial theorem states that for any real numbers a and b , and a is non-negative integer n ,
so (a + b) = C (n, 0) a b + C (n, 1) a b + ⋯ + C (n, n − 1) a b
+ C (n, n) a b
. Now
for 1 ≤ k ≤ n , C (n + 1, k) = C (n, k) + C (n, k − 1) .
n
n
0
n−1
1
1
n−1
0
n
Pascal’s triangle is an extremely important concept to figure out the binomial coefficients.
That is how we construct the Pascal’s Triangle and that is how we figure out the binomial
coefficients.
Pigeonhole Principle
The Pigeonhole Principle. If k < n and n pigeons fly into k pigeonholes, some pigeonhole
contains at least two pigeons. We can also demonstrate this concept if we have X and Y here.
media.capella.edu/CourseMedia/MAT2051/unit3/transcript.html
4/5
1/24/2021
The Counting Principle Transcript
We have 1, 2, 3, 4, 5, being the pigeons, in set X . And we have a , b , c , being the pigeonholes,
in set Y . So let us say 1 goes to a , 2 goes to c , 3 goes to a , 4 goes to b , and 5 goes to c .
So, if X and Y are finite sets where |X| > |Y | and f
x , x ∈ X where of course x
is not equal to x .
1
2
1
: x → y
, then f (x
1)
= f (x2 )
for some
2
Now there is a third form of the Pigeonhole Principle which states if X and Y are finite sets with
|X| = n and |Y | = m , and then we have k = [
] , then there are at least k values and the k
values are a , a , … , a ∈ X such that f (a ) = f (a ) = ⋯ = f (a ) . So, for example, if
n = 5 , m = 3 , then k = [
] = [ ] = 2 .
n
m
1
2
k
1
n
5
m
3
2
k
Licensed under a Creative Commons Attribution 3.0 License
media.capella.edu/CourseMedia/MAT2051/unit3/transcript.html
5/5
Purchase answer to see full
attachment
