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


by: Mr. Molly Kessler


Mr. Molly Kessler
GPA 3.62

G. Baumgartner

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

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

G. Baumgartner
Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 63 page Class Notes was uploaded by Mr. Molly Kessler on Tuesday October 13, 2015. The Class Notes belongs to CSC 4101 at Louisiana State University taught by G. Baumgartner in Fall. Since its upload, it has received 22 views. For similar materials see /class/222856/csc-4101-louisiana-state-university in ComputerScienence at Louisiana State University.

Similar to CSC 4101 at LSU

Popular in ComputerScienence




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: 10/13/15
Induc rion and Recursion 6562259 DiscreTe S rr39uc rur39es Konstantin Busch LSU Induc rion Induc rion is a very useful proof Technique In compu rer science induc rion is used To prove proper ries of olgori rhms Induc rion and recursion are closely relo red Recursion is a description meThod for algorithms Induc rion is a proof me rhod sui roble for recursive olgori rhms Konstantin Busch LSU 2 Use induc rion To prove Tho r a proposition Pn is True Induc rive Bosis Pr39ove Tho r P1 is True Induc rive Hypothesis Assume Pk is ve for39 any posi rive in reger39 k Induc rive S rep Pr39ove Tho r Pk 1 is True Konstantin Busch LSU Induc rive Hypothesis Assume Pk is ve for any posi rive im eger39 k Induc rive S rep Pr39ove Tha r Pk 1 is True In o rher words in induc rive s rep we prove Pk gt Pk 1 for every posiTive in reger39 k Konstantin Busch LSU Induc rive basis Inductive S I39ep 101 Pk gt Pk 1 True True Pr39oposi rion Two for39 all posi rive im egers Pl gt P2 gt P3 gt P4 gt Konstantin Busch LSU Induc rion as a rule of inference P1 A VkPk gt Pk 1 gt VnPn Konstantin Busch LSU Theorem 1972 123mn n1 Proof Induc rive Basis PG 1 Induc rive Hypo rhesis assume Tho r i r holds Pk 12km Induc rive S rep We will prove k 1k 1 1 2 Pk1 12kk1 K Busch LSU Induc rive S rep induc rive hypo rhesis 2 k 1k 1 1 2 End of Proof Konstantin Busch LSU 8 Harmonic number39s H 21llii 2 J 1123 1 1 1 25 Konstantin Busch LSU Theorem H2 21 72 2 0 Proof Induc rive Basis n O H HOH11191Z 2 2 2 2 Konstantin Busch LSU 10 Induc rive Hypo rhesis n k k Suppose I I39 holds H2k 21 Induc rive S rep n k 1 We will show H2k121 kgl Konstantin Busch LSU 1 1 1 F from induc rive hypoThesis End of Proof Konstantin Busch LSU 12 Theorem H2 1n n20 Proof Induc rive Basis n 0 H2quot H20H111O1n Konstantin Busch LSU Induc rive Hypo rhesis n k Suppose it holds H2k S 1k Induc rive S rep n k 1 We will show H2 1 slk1 Konstantin Busch LSU 14 from induc rive 2k1 hypoThesis End of Proof Konstantin Busch LSU 15 We have shown 1 SH2H 1n I1 HZLlong S S H2 logk 1 SHk 1 10gk Hk log k Konstantin Busch LSU 16 Tr39iominos Theorem Every 2quot x 2quot n 21 checkerboard with one square removed can be led with rriominoes PrOOf Induc rive Basis n21 21x21 gr 7 hole Konstantin Busch LSU 18 Induc rive Hypo rhesis n k Assume Tha r a 2quot x 2quot checkerboard can be led wi rh The hole anywhere 2amp2quot Hole can be anywhere Konstantin Busch LSU 1 9 Induc rive S rep n k 1 2k1 X 2k1 Konstantin Busch LSU 20 By induc rive hypo rhesis 2quot x 2quot squares wi rh a hole can be Tiled 2kgtlt2k 2kgtlt2k add Thr39ee artificial holes Konstantin Busch LSU 21 28 x 28 case Konstantin Busch LSU 22 2kgtlt2k 2kgtlt2k i Replace The Three holes wi rh a Tr39iomino Now The whole area can be Tiled Konstantin Busch LSU 23 28 x 28 case End of Proof Konstantin Busch LSU 24 Strong Induction To prove Pn Inductive Basis Prove that P1 is true Inductive Hypothesis Assume P1 A P2 A A Pk is true Inductive Step Prove that Pk 1 is true Konstantin Busch LSU 25 Theorem Every in reger n 2 2 is o produc r of primes of leos r one prime in The produc r Proof STrong Induc rion Induc rive Basis n 2 Number 2 is a prime Induc rive Hypo rhesis 2 S n S k Suppose Tho r every in reger be rween 2 and k is a produc r of primes Konstantin Busch LSU 26 Induc rive S rep n k 1 If k1 is prime Then The proof is finished If k1 is MT a prime Then if is composi re k1ab 236219316 Konstantin Busch LSU 27 k1ab 23621936 By The induc rive hypo rhesis ij21 a2p1p2 pi gt k1a39bp1 39pi39 qj bM2 quot39qj primes primes End of Pr39oo1c Konstantin Busch LSU 28 Theorem Ever39y pos rage amoun r n 212 can be generated by using 4cen r and 5cen r s ramps Proof S rr39ong InducTion IndUCTive BOSiS We examine four39 cases because of The induc rive s rep n12444 n14554 n13445 n15555 Konstantin Busch LSU 29 Induc rive Hypothesis 12 S n S k Assume ThoT ever39y pos roge omoun r be rween 12 and k can be genero red by using 4cen r and 5cenT sTomps na 4b5 Induc rive S rep n k 1 If 12 S k S 14 Then The induc rive s rep follows directly from induc rive basis Konstantin Busch LSU 30 Consider 215 k1k34 12k 3Sk Inductive hypothesis k 3a394b395 k1k 34a3914b 5 End of Proof Konstantin Busch LSU 3 1 Recursion Recursion is used To describe func rions se rs algorithms Example Fac rorial func rion n Recursive Basis fO 1 Recursive S rep fn 1 2 n 1 fn Konstantin Busch LSU 32 Recursive algori rhm for39 fac ror39ial fac ror39ial n if n 1 Then r39ecur39sive basis return 1 else r39ecur39sive s rep re rur39n n factorialn1 Konstantin Busch LSU 3 3 Fibonacci numbers a d za w Recursive Basis f0 0 f1 1 Recursive S rep fn fn l n 2 n234 Konstantin Busch LSU 34 f00 f11 f2f1f0101 f3f2f1112 f4f3f2213 f5f4f3325 f6f5f4538 f7f6f58513 Konstantin Busch LSU 35 Recursive algorithm for Fibonacci func rion fibonacci n if n E 01 Then r39ecur39sive basis r39e rur39n n else r39ecur39sive s rep r39e139u rn bonaccinl bonaccin2 Konstantin Busch L SU 3 6 I rer39a rive algorithm for39 Fibonacci func rion fibonaccin ifn0 Thenylt O else xlt O ylt 1 for39 ilt 1To n l do zlt xy xlt y ylt z r39e rurn y Konstantin Busch L SU 3 7 Theorem fngt6 2 for n23 1 2 5 2 golden ro o Proof Proof by strong induc rion Induc rive Basis n 3 n 4 f3 2 gt a f4 3 gt a Konstantin Busch LSU 3 8 Induc rive Hypothesis 3 S n S k Suppose i r holds fn gt 639 Induc rive S rep n k 1 We will prove fk1 gt 50H for39 4 S k Konstantin Busch LSU 3 9 5 is The solu rion To equaTion x2 x 1 O l 6261 1 616 1 2 62 6k 3 616k 3 6k 2 6k 3 fk12fk jrk 126k 2 6k3 51H End of Proof Konstantin Busch LSU 40 Grea res r common divisor Recursive Basis gcda0 a Recursive S rep gcdab gcdbam0d 19 62gt Konstantin Busch LSU 41 Recursive olgori rhm for39 gr39eo res r common divisor39 gcd a9 9 ossume ogtb if I 0 Then r39ecursive basis return a else r39ecur39sive s rep re139u rn gcdb a mod I Konstantin Busch LSU 42 Lom s Theorem The Euclidion olgori rhm for39 gcdab a 2 9 uses of mos r 510g10 b divisions i rer39o rions Proof We show Tho r There is o Fibonacci relation in The divisions of The olgori rhm Konstantin Busch LSU 43 divisions a I V0 9 392 r1 remainder rOr1 r0 rlq1r2 0ltr2ltr1 rlr2 r1 r2q2r3 0ltr3ltr2 rn2 13H rn2 rn1qn1 r 0 lt r lt rn1 13H rn rn1 rnqn 0 first zer39o r39esul r nga ngO O gchl r2 ngOZ r3 gcdrn2739n1 ngrn l9rn ngrn90 rn Konstantin Busch LSU 44 r0 rlq1r2 gt r0213r2 r1 r2q2r3 gt 132F2r3 rn Z rn lqn 1rn gt rn Z 2rn 1rn H rnqn0 2 w This holds since 7 lt 12H and qn is in reger39 Konstantin Busch LSU 45 This holds since rH 2 gcdab 21 r gt20 n l r gtQ4Q n 2 731 3 2 731 2 7314 QZQQ n25g rid 2 Z n 1rn jf2 l rid 3 Z n 2rn 1 f5 r22r3r42 n 1 n 2fn V1273V22fnfn4fn1 Konstantin Busch LSU 46 b r1 2 a1 9 gt 5 n1 gt 6n 1 10g10 b gt n 110g10 5 5212 nltwllt5loglobl loglo nSSloglob End of Proof Konstantin Busch LSU 47 Algorithm Mergesor r 82469710153 MN 82469 710153 sor rl lsor r 24689 135710 may 12345678910 Konstantin Busch LSU 48 Sor39T a1a2an 39f m 39 gym2f A sorta1a2am B sortamam1an r39eTur39n mergeA B else r39e rur39n a1 Konstantin Busch LSU 49 Inpu r values of recursive calls 82469710153 82469 710153 4 69 7101 53 4 6 9 7101 5 3 2 7 10 Konstantin Busch LSU Inpu r and ou rpu r values of merging 12345678910 24689 135710 8 69 7101 53 4 6 9 7101 5 3 2 710 Konstantin Busch LSU mer39ge AB 39I wo sor i39ed lisTs Llt whileA andB do Remove smaller first elemen r of A93 from i rs lis r and inser39T it To L if A 0rB Then append remaining elemen rs To L r e rur39n L Konstantin Busch LSU 52 merging 2 4 6 8 9 248 69 A B L Comparison 48 69 2lt4 48 69 2 4lt6 8 69 24 6lt8 8 9 246 8lt9 9 3468 24689 Konstantin Busch LSU 5 3 The ro rol number of comparisons ro mer39ge Two is rs AB is of mos r Merged size comparisons s i A i i Bi Leng rh of A Leng rh of B A beHer39 bound on comparisons is maX A B Konstantin Busch LSU 54 Recursive invoca rion Tree a1 a2 a n ala2a a 19 22 Dan 2 611 Dan an an an a3n a3 an 1 1 1 4 4 2 2 4 4 w wquot ya 1 613614 an 39an 2 an1 an 6 1 a2 a3 a4 art 3 an Z an l an Assumke n 2 Konstantin Busch LSU 55 Recursive invoca rion Tr39ee Elemen rs per39 lis r a1 a2 a 1 0 n 112quotgn Cl Cl 1 2 n 210g 1 2 2 2 a1 a ag r ag ag1a34n a3flan n4 Zlog39H alfaz 537614 an3a afqpan 2 Zlogn logn l 612 gt12 61234 anfg 5H 011 1210 A5533 Ievels of Tree 1 logn Konstantin Busch LSU 56 merging Tree a1 a2 611612czn 2 a1a a 21 4 a 0 3 E 4 a1a4 a ab 2 0304 quot a1 a2 a3 a4 axn Cl Cl Cl 21 229 9 n 2 a 9 9a3n a3n 9 Dan 1 1 4 4 an 3 9 an Z an1 an art 3 an Z an l a Konstantin Busch LSU Elemen rs per39 lis r 71 142 144 57 merging rr39ee Comparisons per level j z nCn al az 9aquot agnja z 3a n 2 j 611 an an1an an1a3n a3 a n4gtE n 1 T 3 3 7 7 A a1a4 an339an 4 n a 017 a1 2 613614 3 n 2 an1an n 39 39 39 I 6 1 a2 a3 a4 art 3 an Z an l an Merges TOTOI COST nlevels1 nlogn per eve Konstantin Busch LSU 58 If n 2k The number of comparisons is of mos r nlogn If n 72 2quot The number of comparisons is of mosT mlogm On log n m zilogni lt 272 Time complexi ry of merge sor39T On log n Konstantin Busch LSU 5 9 Homework 3 Solutions 1 The trick is that the constructor of the class would not be made public but only private or protected and that the class maintains its own instances E g class BoolLit extends Node private boolean value private static ff null private static tt null protected BoolLitboolean v value v public static BoolLit getFalse if ff null ff new BoolLitfalse return ff public static BoolLit getTrue if tt null tt new BoolLittrue return tt In the design patterns literature they call this a Singleton pattern A pure Singleton pattern only maintains a single instance that s why it s called Singleton but as with all design patterns there can be variations BTW in order to simplify the implementation of the builtin Scheme function eq in Project 2 it would be best to implement BoolLit and Nil as Singleton patterns 2 Since we can t modify Widget the only solution is to de ne a forwarding class aka adapter wrapper or envelope for Widget In the design patterns terminology they call this an Adapter design pattern Ifclass Widget implements some interface WidgetInterface that is used in the client then our wrapper could be written to implement the same interface class WWrapper implements WidgetInterface Widget obj public WWrapperWidget o obj o public int wizbangint param print param to log le int rv objwizbang print rv to log le return rv If class Widget has other methods that might be called by our client we need to provide the appropriate methods in the adapter as well public int foo return objfoo The code that initiated Widget objects would now be written as follows WidgetInterface p new WWrappernew Widget Another possibility would be to use inheritance Class WWrapper would inherit everything from class Widget Method wizbang would then be rede ned to provide the logging class WWrapper extends Widget public WWrapper super public int wizbangint param print param to log le int rv superwizbang print rv to log le return rv Widget p new WWrapper If the client refers to the Widget instance through a pointer of type Widget instead of through a pointer of type WidgetInterface we can only use the inheritance version Either implementation would qualify as an adapter pattern For this problem the version using inheritance would be simpler to write since we don39t need other forwarding methods and it would be slightly more ef cient The Adapter pattern is a little more general than what39s shown in this problem In many cases the rst implementation would be preferable or more elegant In this case either implementation is appropriate 3 The values of i j and k are l 2 and 2 respectively When selecting which method to call we rst take the static type of the receiver to nd the potential method types then we select the best match the most speci c applicable method using the static types of the arguments then at run time we have the virtual method dispatch In the rst call the static type of p is C so fooC is the only choice Since at run time p also points to a C object we call CfooC In the second call the static type ofq is also C so fooC is the only choice for a possible function type It s the only choice the compiler sees The assignment to q and the class de nition of D might be in another compilation unit So for selecting the appropriate function type the compiler doesn39t have any other choice It might not know when compiling the call qfooq that class D even eXists At run time q happens to point to a D object so we call the fooC method from class D since this method is in the virtual function table entry in the C part For the third call the story is the same as for the second call since there is only one choice of a method to select in class C The argument of type D can be assigned to the parameter of type C because D is a subclass of C so there39s no problem 4 head even 0 head tail even 2 head tail tail even 4 head tail tail tail even 6 nth even 5 10 nth even 1000 2000 This code conceptually de nes an in nite list of even numbers The function makestream builds such an in nite list head and tail play the roles of car and cdr on streams nth extracts the nth element from a stream Streams are built as a cons node containing the rst element in the car eld and the function next in the cdr eld This function computes the rest of the stream whenever an element is accessed The function tail takes this function next out of the cdr of a stream and calls it to produce the rest of the stream This code is inef cient Normally streams would be built such that elements that were accessed before would be cached or quotmemoizedquot Initially the stream would be constructed as a cons node containing the first element and the function to compute the rest of the stream After accessing the second element the first cons node is updated with setcdr so that the stream now contains the first two elements followed by the function that computes the rest And so on All we need to change for that is tail define tail stream let d cdr stream if procedure d let t d setcdr stream t t d To make building streams easier Scheme provides the macro delay and the library function force see Scheme Report Sections 425 and 64 In a lazy functional language such as Haskell all lists really are streams If Scheme were lazy we could define even as follows define next m cons m lambda m 2 define even next 0


Buy Material

Are you sure you want to buy this material for

25 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

Steve Martinelli UC Los Angeles

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

Janice Dongeun University of Washington

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

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


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

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.