### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Discrete Math for CS ECS 020

UCD

GPA 3.75

### View Full Document

## 33

## 0

## Popular in Course

## Popular in Engineering Computer Science

This 4 page Class Notes was uploaded by Ashleigh Dare on Tuesday September 8, 2015. The Class Notes belongs to ECS 020 at University of California - Davis taught by Staff in Fall. Since its upload, it has received 33 views. For similar materials see /class/191701/ecs-020-university-of-california-davis in Engineering Computer Science at University of California - Davis.

## Reviews for Discrete Math for CS

### 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: 09/08/15

Lecture 11 572009 Announcements Ps6 out Due Tuesday Midterm back Tues May 12 Common functions see 34 in book mostly review I assume log exponent oor ceiling mod Skip 35 36 Recursively De ned Functions A recursive function is defined by referring to itself We saw this in defining Tn the minimum number of moves to shift n disks in the Tower of Hanoi problem Tn 1 n1 Tn 2 Tn l 1 for ngtl Domain codomain range N N a subset of N 2quotn l nl 2 Two key properties that make this type of definition work nonrecursive definitions for small base values and each time we refer to the function on the right side the argument is smaller than on the left side Book does n f0 1 fn n fnl n gt0 I ll do fibinacci function Def 32 in book FOF1 1 Fn Fn l Fn 2 for n gt1 F2 F2 1F22 Fl FO 1 1 2 F3 F31 F32 F2 F1 21 or expand F2 Give tree and better way to compute Function Fib0n If n0 OR nl Returnl39 Else ReturnFib0n l Fib0n2 Fibo is a recursive function Comments should make sure n not negative and declare n to be an integer Give tree of recursive calls Argue number of calls at least 2An2 Altemative A an array of size n AO e 139 Al e139 Fori 6 2tonDO Ai e Ai2 Ail39 Statement labeled is executed n2 times and we assume takes at most some constant about of time c time to look up or assign to an array so total time is at most 2c nl c n c c Note that the above is a function of n call it Tn known as a linear function if n is twice as large then time Tn is twice as much Function Growth rates 39 we skipped 37 and 38 will return to them later We want to be able to compare functions and want to ignore less important terms and constants Lets us compare how different programs perform for example in the example for Fibonacci the second program with Tn n c will significantly outperform the recursive one with 2An calls even if c is very large eventually and typically for moderate n Notation Big O and later 9 Big Theta and 9 big Omega We say x3 E 02 X Kind of like saying x3 le 2 X quotfor large x and if you don t care about constantsquot Def Def 34 from Schaum s Og f R gt R such that exists Ngt0Cgt0 st fn lt C gn for all ngtN You can actually forget about the and just imagine that f is nonnegative valued replace f by in case it s not Example nX lOOn E OnX YES 10 n2 E On2 YES lOn2 lOOn log N in On2 YES n log n in On2 YES n2 log in On log n NO As a practical matter it is pretty easy to get the right big 0 class for a function I throw away all constants multiplying terms or added to them eg le5 becomes X Note that you can t throw away constants that are exponents eg n2 can t throw away the 2 2 among terms added together throw away all but the fastest growing term apply to examples above How to prove things like this Suppose want to show 10 n logn 50n l E On log n must find a large enough C N such that 10 nlogn 50nl lt C nlog n for all n gt N What C N would you like would you like How about 10 nlogn 50n1 lt 61 nlog n Check true if 50n1 lt 51 nlogn Now 50n lt 50n log n if nge 3 So the above is true if 1 lt nlog n But for n gt 3 this is certainly true Doing it in the forward direction 1ltnlogn 10nlogn50n1lt10nlogn50nlognnlogn lt61nlogn when ngt3 n vs 2An n E O2An NO 2An E On Yes n nen sqrt21t n 1 O1n 1n n approx n 1n n n n lgn n nlgn n 2 nquot3 2An 10 4 10 40 100 10A3 1024 100 7 100 700 1000 10A6 10A30 1000 10 1000 10A4 10A6 10A9 10A300 g f R gt R eXists cCN such that 0 gm lt fn lt C gm Intuitively Ofn is all functions of growth rate fn or less fn is all functions of the same growth rate as fn

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

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I 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!"

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