Discrete Mathematics.
Assessment 2
Top of Form
Bottom of Form
Content
· Counting, Combinations, and Permutations
·
· Details
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.
By successfully completing this assessment, you will demonstrate your proficiency in the following course competencies and assessment criteria:
· Competency 2: Apply the methodologies of discrete math.
· Convert numbers to different representations.
· Compute combinations and/or permutation.
· Compute discrete probability.
· Combine discrete probability.
· Competency 4: Apply discrete math methods and tools to solve problems encountered in a work setting.
· Apply number theory to encryption.
Competency Map
Check Your ProgressUse this online tool to track your performance and progress through your course.
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
Click the links provided to view the following resources:
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.
Course Library Guide
A Capella University library guide has been created specifically for your use in this course. You are encouraged to refer to the resources in the MAT-FP2051 – Discrete Mathematics Library Guide to help direct your research.
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, 1510 is 15 in decimal (base 10), 00112 is 3 in binary (base 2), and 1A16 is 26 in hexadecimal (base 16).
7. What is the decimal representation of 100011012 ?
7. What is the decimal representation of FFC616 ?
7. What is the binary representation of 17C616 ?
7. What is the hexadecimal representation of 111110002 ?
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.
7. 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.
7. 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.
7. 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.
1. Choose an example of p and q and compute their product z. Justify your selection.
2. 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.
a. 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.
b. 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.
c. Given the above, what is the probability that the hacker will successfully guess p and/or q?
d. Assume the hacker selects five numbers to test.
i. What is the probability that all five attempts will fail? Show your work.
ii. What is the probability that one of the five attempts will succeed? Show your work.
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}. 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.