Discrete Math for CS
Discrete Math for CS ECS 020
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
Report this Material
What is Karma?
Karma is the currency of StudySoup.
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