New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

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

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Study Set for Test 2

by: Aaron Maynard

Study Set for Test 2 CS 2305

Marketplace > ComputerScienence > CS 2305 > Study Set for Test 2
Aaron Maynard
GPA 3.5

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

This is a huge study set bundle for the upcoming test on 3/31. It covers everything since the beginning of March.
Discrete Math for Computing I
Timothy Farage
Study Guide
Math, Calculus, Discrete math, ECS, Computer Science, stem
50 ?




Popular in Discrete Math for Computing I

Popular in ComputerScienence

This 18 page Study Guide was uploaded by Aaron Maynard on Tuesday March 29, 2016. The Study Guide belongs to CS 2305 at a university taught by Timothy Farage in Spring 2016. Since its upload, it has received 62 views.


Reviews for Study Set for Test 2


Report this Material


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: 03/29/16
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


Buy Material

Are you sure you want to buy this material for

50 Karma

Buy Material

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

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Kyle Maynard Purdue

"When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the I made $280 on my first study guide!"

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Parker Thompson 500 Startups

"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."

Become an Elite Notetaker and start selling your notes online!

Refund 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


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:

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

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.