### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Notes Bundle for Exam 3 CS 2305

UTD

GPA 3.5

### View Full Document

## About this Document

## 65

## 2

## Popular in Discrete Math for Computing I

## Popular in ComputerScienence

This 55 page Study Guide was uploaded by Aaron Maynard on Wednesday April 27, 2016. The Study Guide belongs to CS 2305 at a university taught by Timothy Farage in Spring 2016. Since its upload, it has received 65 views.

## Reviews for Notes Bundle for Exam 3

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 04/27/16

DiscreteMathforCompSciI SPRINGSEMESTER2016 INSTRUCTOR:DR.TimothyFarage atm150030@utdallas.edu 19 April 2016 Cryptosystem Definition: a pair of algorithms that take a key and convert plaintext to ciphertext and back. Plaintext is what you want to protect; ciphertext should appear to be random gibberish. The design and analysis of today's cryptographic algorithms is highly mathematical. Do not try to design your own algorithms. NO WAY. = PQ YCA. Ceaser EK + 2 | Cipher DK - 2 RSA Cryptosystem RSA is one of the first practical public-key cryptosystems and is widely used for secure data transmission. In such a cryptosystem, the encryption key is public and differs from the decryption key which is kept secret. 1) Public Encryption Algorithm 2) Public Decryption Algorithm 3) Public Encryption Key 4) Private Decryption Key 1 RSA Keys Steps to create an RSA key: 1) Pick two random large primes (200 - 300 digits) P 1 nd P2 2) Compute N = P 1 P2 nd Z = (P1 1) * (2 1) 3) Find a number E that is relatively prime to Z 4) Find the number D, that is the modular inverse of E; solve (E * D) MOD Z = 1. Using P1 3 and P2 11, then Z = 20, E = {1, 3, 7, 9, 11, 13, 17, 19} Say E = 7, then 7D (MOD 20) = 1, then D = 3. Our public key is N and E, N = 33 and E = 7. Our private key is D, D = 3 D and E are symmetric in a mystical way, “Almost everyone uses 65,537 for E”. Encryption Algorithm First some preliminaries; if you want to encrypt message m, then M must be less than N. M is a number. To Encrypt M (Message) : E Compute the number C = M MOD N; send C. (7) Say M = “19”, C = (19)MOD (33) C = 13 To Decrypt M (Message) : D M = C MOD N (3) M = (13)MOD 33 M = 19 2 Digital Signatures Definition: a type of electronic signature that encrypts documents with digital codes that are particularly difficult to duplicate. M = “Test 3 is on May 15th” To digitally sign M, compute C = MOD N E To take the message, M = CMOD N Math by Induction Definition: A way to establish a given statement for all natural numbers, and to prove statements about well-ordered sets. There are two ways of performing math by induction: ● Basis:prove that the statement holds for the first natural nun.er ● Inductive Step: prove that, if the statement holds for some natural numn,r then the statement holds fon+1. Basis:Show that the statement holds fon= 0. P(0) amounts to the statement: In the left-hand side of the equation, the only term is 0, and so the left-hand side is simply equal to 0. In the right-hand side of the equation, 0·(0 + 1)/2 = 0. The two sides are equal, so the statement is trun= 0. Thus it has been shown that P(0) holds. 3 Inductive st: Show thifPk) holds, then P(k+ 1) holds. This can be done as follows. Assume Pk) holds (for some unspecified k). It must then be shown(k+ 1) holds, that is: Using the induction hypothesiPk) holds, the left-hand side can be rewritten to: Algebraically: thereby showing that inP(k+ 1) holds. 4 DISCRETEMATH SPRINGSEMESTER2016 INSTRUCTOR:DR.TIMFARAGE atm150030@utdallas.edu 12-14 APRIL 2016 Pseudo - Random Number Generator Linear Congruence Method A method for generating random (pseudorandom) numbers using the linear recurrence relation: where a and c must assume certain fixed values, m is some chosen modulus, and X_0 is an initial number known as the seed. Using examples m=9, a=7, c=4, ann5: n+17xn4)mod9 xn 5 -> xn 5 Fermat's Little Theorem The theorem is sometimes also simply known as "Fermat's theorem" P-1 If P>2 is prime, and 1<B<P, then BmodP = 1; OR If P is a prime number, then for any integer A, the nu− A is an integer multiple of P. 1 Proof: Start by listing t-1 positive multiplea:of a, a,3a, .p-1a Suppose thatraandsaare the same modulp, then we havr=s(mod p), so tp-1 multiples aabove are distinct and nonzero; that is, they must be congruent to 1, 2, 3, ..p-1 in some order. Multiply all these congruences together and we find a23a..p-1a= 123..(1) (modp) or bettea (p-1) =p-1)! (mop). Divide both sidp-1) to complete the proof. Probability Primality Test A primality test: an algorithm which determines whether a given number is prime. (a)/2) if b is even and b > 0 a= a*(a)b-1)if b is odd 1 if b = 0 Miller-Rabin Primality Test If p is prime and x2 = 1 ( mod p ), then x = +1 or -1 ( mod p ). We could prove this as follows: x= 1 ( mod p ) x- 1 = 0 ( mod p ) (x-1)(x+1) = 0 ( mod p ) Solovay-Strassen Primality Test 2 DiscreteMath SPRINGSEMESTER2016 INSTRUCTOR:DR.TIMOTHYFARAGE ATM150030@UTDALLAS.EDU 05-07 April 2016 Tech Update: With the continued advances in technology and robots, will it become harder to get jobs? Android is dealing with a demand for the creation for sex-bots. All drones that are being used in the military use a human element; when will the day come when that is no longer necessary? There is a boZero Marginal Cost So, that says the pricing of various expenses such as housing, transportation etc, will become cheaper as time goes on, that the cost of basic necessities will be approaching zero. www.timfarage.coTim’s blog; there is a talk about the natural resourse tax (dividend) Farage also says to watch Batman V Superman within a week. Sieve of Eratosthenes In mathematics, the sieve of Eratosthenes (Ancienσκινονk: κό Ἐρατοσθέ νους , kóskinon Eratosthénous), one of a number of prime number sieves, is a simple, ancient algorithm for finding all prime numbers up to any given limit. 2,3,4,,6,7,8,9,10,1,12,13,14,15,1617,18,19,20… Circle the first number, then cross off the multiples; O(N^2) Prime Number Theorem 1 Deals with the distribution of prime numbers. The fraction of numbers less than the number N that are prime is about: 1/ln(N) N 1/ln(N) 20 33% 100 22% 1,000,000 7% Pick a random number between 1 and 1,000,000 and there is a 7% chance that it’s prime. About 1% of 100-digit numbers are prime (that end in 1, 3, 7, 9). 1% of 10^100 = 10^98 primes with 100 digits. There are about 10^80 particles in the entire universe. You couldn’t inscribe all the prime numbers with 100 digits if you used all the matter in the universe. So the odds of someone guessing such prime is miniscule. 2 Discreet Math for Computing Aarst Mardard Timothy Farage March 1 – 3 , 2016 Tech Update Nuclear Power United States get 20% of its electricity from nuclear power. France gets 70% of its electricity from nuclear power. When nuclear power came along, France created a reactor design and made an approval for such design. In the 1970's, three-mile island had a nuclear meltdown and the people became nervous. Shortly after the meltdown a fictional film came out about the dangerous effects of nuclear power, and delayed the process for America because the people were scared. If you can do nuclear inexpensively, it would be the best to use because it is nonpolluting, gas emitting source of power. 0% of people have been hospitalized or killed due to nuclear radiation in the US. The only nuclear meltdown to have caused illness and death was Chernobyl. At the time this was under the Soviet Union which carries little to no standard. ^^^ Bottom line: don't work in a nuclear power plant in a communist country. Functions Definition: A function F from a set B to a set C, F: B->C, is a set of ordered pairs, such that every element of B is mapped to (or paired with) exactly one element of C. Domain Codomain Discreet Math for Computing Aastn Mrdnard Timothy Farage March 1 – 3 , 2016 Let’s say B is the set of Students in the class, and C is the set of Grades. B:{set of students in class} C:{set of grades} A+ A B F Students Grades B:{4,6,7} C:{Red, Yellow, Green, Violet} F1 = {(4,[something]), (6,[something]), (7,[something])} ^^^ There are only three sets, though they can contain any combination. To solve how many functions from B->C, we take the exponential of |C| to |B|: |B|^|C| Discreet Math for Computing Aaron Maynard Timothy Farage March 1 – 3 , 2016 F:[all real numbers] -> [all real numbers] where F(x) = x^2 A function is known to be as a one-to-one, or 1-1. In linear algebra, known as objective. If ∀ x ε B ∀ x ε B[(x1!= x 2 -> (F(x )1!= F(x ))2 Every function means: for every x, there is a y. Every one-to-one function means, for each x, there is a unique y. In a one-to-one function, if F:B -> C is 1-1, then |B| <= |C| A function F:B->C is said to be onto (surjective) if for all Y there exists a Y C B such that there exists an (x,y) in a function... or y = f(x) "There are no unused values in C" "The codomain value of C is all used up" Domain Codomain if F:B->C is onto, then |B| >= |C| Example: B would be the number of students taking a course, while C would be the number of sections of such course. Discreet Math for Computing Aaron Maynard Timothy Farage March 1 – 3 , 2016 If F:B -> C is both 1-1 and onto, then F is said to be of correspondence (pairing). Domain Codomain |B| = |C| Discreet Math for Computing Aaron Maynard Timothy Farage Weeks before Spring Break Infinity 2 Lim (1/x ) = 0, as x approaches infinity. A function from B -> C is said to be a one-to-one correspondence if it is one-to- one and onto. (There is a pairing between B and C with no elements left over) Two sets B and C have the same size or cardinality if there is a one-to-one correspondence between them. N = {0, 1, 2, 3, 4, ...} T = {0, 10, 20, 30, 40, ...} T contains N, therefore T is a subset of N. Is |T| < |N| or |T| = |N|? These two sets by the same definition have the same cardinality, so |T| = |N|. Discreet Math for Computing Aaron Maynard Timothy Farage Weeks before Spring Break Integers Definition: a whole number; a number that is not a fraction. N = {0, 1, 2, 3, 4, 5, ...} Z = {-3, -2, -1, 0, 1, 2, 3, ...} Is |N| = |Z|? Fractions Q = {rational Numbers} (Those that can be written as fractions) Q + 1/1, 1/2, 1/3, 1/4, ... 2/1, 2/2, 2/3, 2/4, ... 3/1, 3/2, 3/3, 3/4, ... |Q | = |N| Discreet Math for Computing Aaron Maynard Timothy Farage Weeks before Spring Break Binary Strings Binary strings include 0, 1, 00, 01, 10, 11, 000, 001... Any set B where the cardinality of B (|B|) = the cardinality of N (|N|), is said to be countably infinite. (COUNTABLE) or (LISTABLE) This means that they can be listed using a pattern so that any number of the set is in the list. |B| > |N|, the cardinality of real numbers is greater than the cardinality of natural numbers. They are unlistable, or uncountably infinite. If the |B| > |N|, then B in uncountably infinite. Reals consist of rational numbers UNION irrational numbers. If the Reals are uncountable, and the rational numbers are countable, then the irrationals must be countable. |R| = |Q| = |R x R| = |R x R x R|, (|R x R|) is the set of points in a plane, (|R x R x R|) are is the set of points in space. If B is an infinite set, the P(B) is such that |P(B)| >|B|. This means that there are an infinite number of sets greater than any given set, and cannot be put into a one-to- one correspondence. Discreet Math for Computing Aaron Maynard Timothy Farage Weeks before Spring Break Java Programs J = {Java Program} Every Java program is finite, however there is no limit to how long it can be. You can list Java programs by order of size, or by number of characters. CLASS A{} is nine characters, and would be the shortest Java Program CLASS B{} CLASS C{} CLASS ... Java programs are a listable infinite. |R| > |J| means that some real numbers are not computable, meaning you cannot write a program that can compute certain numbers. VOID display_PI (int num.digits) { ... } Just because a number is cannot be computed, doesn't mean that the number is irrational. VOID display_X (int num.digits) { ... } This would be a program that could encounter an error. A(subscript)N = {N/2 if N is even, 3N + 1 is N is odd} This is a Collate Conjecture. A(subscript)6 = 3 A(subscript)3 = 10 A(subscript)10 = 5 so on to 16... 8... 4... Then repeats 4, 2, 1, 4, 2, 1, ... Then begins an iteration. Discreet Math for Computing Aaron Maynard Timothy Farage Weeks before Spring Break Hailstone Numbers Definition: Sequences of integers generated in the Collatz Conjecture. For example, for a starting number of 7, the sequence is 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, .... Such sequences are called hailstone sequences because the values typically rise and fall, somewhat analogously to a hailstone inside a cloud. While a hailstone eventually becomes so heavy that it falls to ground, every starting positive integer ever tested has produced a hailstone sequence that eventually drops down to the number 1 and then "bounces" into the small loop 4, 2, 1, .... There is no proof that every number will eventually get to one. "The proof of this is beyond our current mathematical abilities" - Leonard Hofstetter Look Alike Also note that any problem that has no algorithm to solve it is called undecidable or incomputable. This comes under the title of complexity theory, or computability theory. Discreet Math for Computing Aaron Maynard Timothy Farage Weeks before Spring Break Number Theory Deals with the natural numbers or possible numbers Modular arithmetic Pseudo random number generator Cryptography Say B divides C, B|C, if B is a factor of C: C = K * B where K is an integer. 4|12 12 = K * 4 True 5|12 12 = K * 5 False If B|C and B|D then B|(C+D) 2|6 2|8 2|14 Proof: B|C given C = K *1B B|D D = K * B 2 C + D = K 1 B + K * 2 C + B = (K 1 K )2* B (C+B) | B Discreet Math for Computing Aaron Maynard Timothy Farage Weeks before Spring Break MOD operator Definition: (MOD, Modulus, “%”) is the remainder of the numerator over the denominator. 15 MOD 7 = 1 Symbol for MOD in Java, C, C++ is "%". int K = 15%7; K = 1 int K = 15/7; K = 2 0 <= (B MOD M) < M The MOD of the product is the product of the MOD’s. B * C MOD M = (B MOD M) * (C MOD M) MOD M 6,000,000 MOD 9 = 6 * 10 * 10 … 10 MOD 9 = (6 MOD 9) * (10 MOD 9) MOD 9 = 6 * 1 MOD 9 = 6 MOD 9 = 6 Say the time is 18 hours. What time will it be in 100 hours? Solution: (100 MOD 24) + 18 4 + 18 MOD 24 = 22 MOD 24 = 22 Say you have 200 eggs. There are 12 eggs in a carton. 200 DIV 12 = 16 200 MOD 12 = 8 Number Theory (Prime) Definition: the branch of mathematics that deals with the properties and relationships of numbers, especially the positive integers. Let X be an even number >= 4. Then X can be expressed as the sum of two primes. This has never been proven. Discrete Math for Computing Andon Mathard Timothy Farage March 22 – 24 , 2016 Question of the Day If you had the option to live forever with your body in a frozen state of 30 years of age, would you take this option? Certain Important Problems There is no algorithm to solve certain important problems. An algorithm is a finite sequence of well-defined instructions for solving a problem. Halting Problems Is True (string, math, proposition) Suppose we have a problem that can be solved with an algorithm, how fast can we solve it? There are many different sorting methods: Slower sorting methods: Bubble Sort Selection Sort Insertion Sort Faster sorting methods: Quick Sort Merge Sort “I wrote a perfect game playing program” To do this you must write what is called a “game tree”. John von Neumann and Oskar Morgenstern created game theory, and consequently this tree. Discrete Math for Computing Aaron Maynard Timothy Farage March 22 – 24 , 2016 In chess, there is an estimated 10600possible chess games; there are only an estimated 10 particles in the entire universe. By this logic, there is not enough matter in the universe to show each game tree. This is why chess playing programs are not perfect. There is also the speed of a process to consider, even if you successfully created the perfect chess playing program, it would take forever to play. Finding the Lowest Value in an Unsorted Array int find_longest(double D[], int N) // Array D is filled with numbers, and there are N of them. For this example we // will be using student GPA’s { int index = D; for (int i = 1, i < N, i++) { if (D[i] > D[index]) index = i; } return index; } This program has the possibility of executing 2 + 3N L.O.C. Discrete Math for Computing Aaron Maynard Timothy Farage March 22 – 24 , 2016 Time Complexity Let us say we have a function f(n) Then say that f(n) is equal to O(n ) if some constant c exists such that cn > f(n) for large values of n (for some k, n > k). We would look at the highest order term, because we only are concerned about the large n. We don’t care about the number up front because we care about the growth of the function, because it is a cubic function. To say O(n ) is to say that it 3 will grow or dominate n . It tells you that the time grown in the cube of the data. Some Important Time Complexities O(n!) – Factorial Time Complexity o Displaying Permutations O(2 ) – Exponential Time Complexity o Traveling Sherman O(n ) – Cubic Time Complexity o Matrix Multiplication O(n ) – Quadratic Time Complexity o Usual Multiplication O(n log(n)) – “n log(n) o Quick / Merge Sort O(n) – Linear Time Complexity o Finding Max Element in an Unsorted Array O(log(n)) – Logarithmic Time Complexity o Binary Search O(1) – Constant Time Complexity o Average the first three elements of an array Discrete Math for Computing Andon Mthnard Timothy Farage March 22 – 24 , 2016 Base Conversions Representative decimal, binary, and hexadecimal. ^^^ There will be six problems on the test about these conversions. To convert 40 to binary (which is base 2) divide 40 by 2, and use the remainders. 40/2=0 20/2=0 10/2=0 5/2 =1 2/2 =0 1/2 =1 0 =0 The answer to this would be 101000. Discrete Math for Computing Aaron Mathard Timothy Farage March 29 , 2016 Question On The Test? Does Farage have over 1,000,000 views on the forum? ~1,003,000 Two positive integers are said to be relatively prime if their GCD (GCF) is 1. Is 12 relatively prime to 35? YES Euclid’s Greatest Common Factor Algorithm What is the greatest common factor (GCF) of 91 and 287? Take the smaller number and divide it by the greater number. How many times does 91 go into 287? The answer is 3, with a remainder of 14. Take the remainder “14” as the next divider and use the dividend as the old divisor. 1) How many times to 14 go into 97? 6 R 7 2) How many times does 7 go into 14? 2 R 0 Using this method, we can conclude that 7 is the GCF of 91 and 287. What is the greatest common factor (GCF) of 347 and 563? 1) How many times does 347 go into 536? 1 R 216 2) How many times does 216 go into 347? 1 R 131 3) How many times does 131 go into 216? 1 R 85 4) How many times does 85 go into 131? 1 R 46 5) How many times does 46 go into 85? 1 R 39 Discrete Math for Computing Aaron Mathard Timothy Farage March 29 , 2016 6) How many times does 39 go into 46? 1 R 7 7) How many times does 7 go into 39? 4 R 0 8) How many times does 4 go into 7? 1 R 3 9) How many times does 3 go into 4? 1 R 1 Using this method, we can conclude that 1 is the GCF of 347 and 563. This algorithm is O(log(N)). The previous problem is the worst case scenario. In number theory, this method can be considered fast because it takes a little amount of time. * On the test, every step will need to be written down. To write the problem as an algorithm: 287 = 3*91+14 91 = 6*14+7 14 = 2*7 Say there is some number R that divides into both 91 and 287. If number R is divisible by 91 and 287, it must also be dividable by the remainder 14. If R divides into 287, then 287/R must be an integer, same goes with 91. If this were false, then the statement would be a fraction plus an integer; a fraction plus an integer does not equal an integer. Discrete Math for Computing Aaron Maynard th Timothy Farage March 29 , 2016 Modular Exponentiation This algorithm is used throughout the world: 100 5 MOD 7 (divide by 7 and get the remainder) 5 MOD 7 = 5 2 5 MOD 7 = 25 MOD 7 = 4 B MOD 7 = (B MOD 7) MOD 72 4 2 2 2 5 MOD 7 = (5 MOD 7) MOD 7 = 4 MOD 7 = 2 5 MOD 7 = (5 MOD 7) MOD 7 = 2 MOD 7 = 4 16 8 2 2 5 MOD 7 = (5 MOD 7) MOD 7 = 4 MOD 7 = 2 5 MOD 7 = 2 MOD 7 = 4 64 2 5 MOD 7 = 4 MOD 7 = 2 If your exponent is going to be over your goal, STOP. These exponents are powers of two, with can always add up to the number you want (in this case, 100). 100 = (64 + 32 + 4) 5 + 5 + 5 = 5 100 (2)(4)(2) MOD 7 5100MOD 7 | 16 MOD 7 = 2 This algorithm is O(log2(exponent) 200 6 MOD 11 … 100 Using the exact same method as done for 5 MOD 7 … 128 2 6 MOD 11 = 9 MOD 11 = 4 (4)(9)(4) MOD 11 6200MOD 11 | 144 MOD 11 = 1

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I made $350 in just two days after posting my first study guide."

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.