### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Discrete Math Notes for the week of March 22nd – 24th, 2016 CS 2305

UTD

GPA 3.5

### View Full Document

## About this Document

## 46

## 0

## Popular in Discrete Math for Computing I

## Popular in ComputerScienence

This 4 page Class Notes was uploaded by Aaron Maynard on Thursday March 24, 2016. The Class Notes belongs to CS 2305 at a university taught by Timothy Farage in Spring 2016. Since its upload, it has received 46 views.

## Reviews for Discrete Math Notes for the week of March 22nd – 24th, 2016

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

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.

### 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 used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

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