### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Discrete Math for Computing 1 | Week Before Spring Break CS 2305

UTD

GPA 3.5

### View Full Document

## About this Document

## 48

## 2

## Popular in Discrete Math for Computing I

## Popular in ComputerScienence

This 7 page Bundle was uploaded by Aaron Maynard on Thursday March 10, 2016. The Bundle belongs to CS 2305 at a university taught by Timothy Farage in Spring 2016. Since its upload, it has received 48 views.

## Reviews for Discrete Math for Computing 1 | Week Before Spring Break

### 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/10/16

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.

### 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

#### "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!"

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "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!"

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