COMP2123 Finals Notes - Includes all lecture material, and several examples from the textbook. PDF

Preview

Summary

COMP2123 Finals NotesInductionInduction is a very useful proof technique for proving correctness and bound the running time of an algorithm. Most of the statements about the running times of algorithms that we’ll see during this course will hold for all n> 0, where n is the size of the input. How...

Description

COMP21 2 3Fi n a l sNo t e s I nduc t i o n I n d u c t i oni sav e r yu s e f u lp r o o ft e c h n i q u ef o rp r o v i n gc o r r e c t n e s sa n db o u ndt h er u n n i n gt i me o fa na l g o r i t h m. Mo s to ft h es t a t e me n t sa b outt h er un n i n gt i me so fa l go r i t h mst h a twe ’ l ls e e d u r i n gt h i sc o u r s ewi l lh o l df o ra l ln >0 , wh e r eni st h es i z eo ft h ei n p u t . Ho we v e r , t h i si sa c l a i ma b o u ta ni n fin i t es e to fnu mbe r sa n dh e n c ewec a n ’ tp r o vei tf o re a c he l e me n ts e p a r a t e l y . Ba s eCa s e I n d u c t i onp r o v e st h es t a t e me n tf o rab as ec a s e , wh i c hi st h es ma l l e s te l e me n tf o rwh i c ht h e c l a i mmu s th o l d( n=1 ) . I nduc t i o nSt e p As s u me st h a tt h ec l a i mho l d sf o ra l lv a l u e so fns ma l l e rt h a nt h ec u r r e nto ne . Th i si sc a l l e d t hi si n d uc t i o nh y p ot h e s i s .Us i n gt h ei n d u c t i o nh y p o t he s i s , wet h e ns h o wt h a tt h ec l a i mh o l ds f o rt h en e xtv a l u eo fn . I e . Us i n gt h ei n d uc t i o nh yp o t h e s i sf o rn–1t op r o v et h ec l a i mf o rnoru s i n gt h ei n d u c t i o n h y p o t he s i sf orn / 2t op r o v et h ec l a i mf o rnwh e nni se v e n . Pr o bl e ms Pr o bl e m1 . Re c a l lt h a to n ewa yofd e fin i n gt h eFi b on a c c is e q u e n c ei sa sf o l l ows : F(1)=1, F (2)=2,∧F (n )= F (n – 2 )+ F(n – 1)for n>2. Us ei n d u c t i o nt op r o v et h a t F(n)...