Problem Generalization for Designing Recursive Algorithms

P oblem Gene aliza ion o Designing Recu si e Algo i hms Diana Bo ego(B), I ene Ba ba, Miguel To o, and Ca melo Del Valle Depa amen o de Lenguajes y Sis emas In o m´ a icos, Uni e sidad de Se illa, Se illa, Spain {dianabn,i eneb ,miguel o o,ca melo}@us.es Abs ac . This pape ocuses on he di icul y o uni e si y s uden s o acqui e, wi hin compu a ional hinking, he skills o sol e ce ain p oblems h ough ecu - sion. The acquisi ion o his ype o easoning is essen ial o unde s and he di - e en p oblem sol ing echniques ha a e based on ecu si e algo i hms, such as di ide and conque o dynamic p og amming. The e o e, i s , he gene aliza ion o p oblems is p oposed as a s a egy o designing ecu si e algo i hms. As a second s ep, ha gene aliza ion is o malized h ough a speci ica ion shee ha con ains di e en ields ha co espond o he cha ac e is ics ha a e ele an o sol e a p oblem ecu si ely. Keywo ds: Recu si e algo i hms ·Compu a ional hinking ·P oblem gene aliza ion 1 In oduc ion Compu e science uni e si y s uden s ha e he need o de elop compu a ional hinking, which is he men al p ocess used o o mula e p oblems whose solu ions can be ca - ied ou by a compu e . Compu a ional hinking includes skills such as modeling and b eaking down p oblems, p ocessing da a, c ea ing algo i hms and gene alizing hem. The e a e se e al de ini ions ela ed o compu a ional hinking in he li e a u e. Re iewing publica ions abou his opic, Wing e al. [6], who made he e m com- pu a ional hinking amous, p esen he ollowing de ini ion: “Compu a ional hinking in ol es sol ing p oblems, designing sys ems, and human beha io unde s anding, by d awing on he concep s undamen al o compu e science. Compu a ional hinking includes a ange o men al ools ha e lec he b ead h o he ield o compu e science.” The e o e, s uden s mus acqui e compu a ional hinking o be able o ca y ou p ob- lem sol ing h ough modula iza ion, op-down analysis, bo om-up analysis, ecu sion, and so on. Pa icula ly, he unde s anding and applica ion o his las concep o ecu - sion [3,4] equi es he s uden s o make an ex a men al e o . They usually unde s and and lea n mo e easily he i e a i e o mula ions o p oblems. Howe e , o unde s and he ecu si e o mula ion, a special ype o hinking is needed, and he e o e o be able o use ecu si e hinking [7]. This p esen s a di icul y ha makes a men al p edisposi ion necessa y ha is no always equen o easy o each depending on each pe son. In de ail, he ecu si e esolu ion o a p oblem is aised when he speci ica ion o i s solu ion is made based on he solu ion o o he p oblems o he same na u e bu a c smalle size. The e o e, e e y ecu si e de ini ion has (i) base case(s), encompassing and esol ing cases whe e he esolu ion o he p oblem is di ec and does no equi e he use o he unc ion being de ined; (ii) ecu si e case(s), which a e hose whose esolu ion does equi e he use o he unc ion being de ined; and (iii) size o he p ob- lem, which is a ca dinal indica ing he dimension o he p oblem o be sol ed, and ha dec eases in each subp oblem. Thus, a ecu si e algo i hm is one ha exp esses he solu ion o a p oblem in e ms o in oking i sel . As an example, he de ini ion and ecu si e algo i hm o he esolu ion o he ac- o ial o a numbe na e shown below. n!=1n=0 n∗(n−1)!n>0 N (In ege n){ Ns; i {n == 0}{ s=1; }else { s=n* (n-1); } e u n s; } Algo i hm 1: Recu si e algo i hm o calcula ing he Fac o ial numbe (in Ja a) No all ecu si e de ini ions a e sui able o building an algo i hm. To be adequa e, i mus ha e: (1) a leas one base case; (2) in each ecu si e s ep he size should be educed (which implies ha he execu ion o he algo i hm will end). Taking all his in o accoun , and o acili a e he acquisi ion and applica ion o ecu - si e hinking, his pape p oposes o ca y ou wo s eps p io o he design o a ecu si e algo i hm o sol e a gi en p oblem, as shown in Fig. 1. Speci ically, hese s eps a e: 1. Gene aliza ion o he p oblem h ough a se o p oblems [1]. Mo e p ecisely, gene - alizing consis s o adding p ope ies o he o iginal p oblem o conside i a pa icula case o a wide se o p oblems. Fig. 1. P oposed app oach o designing ecu si e algo i hms 2. Speci ica ion o he solu ion o he p oblem h ough a p ede ined speci ica ion shee based on he p e ious gene aliza ion made. This shee con ains di e en ields ha co espond o he cha ac e is ics ha a e ele an o sol e his p oblem ecu si ely. No e ha he goal o he p oposed app oach is no o p o ide a o mal me hod bu o acili a e he acquisi ion o skills ela ed o he design o ecu si e algo i hms. Fo his, we use ou expe ience in he design o ypes in he con ex o objec -o ien ed p og am- ming o concep ualize he popula ion o p oblems ha a e gene a ed when designing ecu si e algo i hms, i.e., when he gene aliza ion is ca ied ou . In such con ex , he co ec de ini ion o he size o he p oblems ( ha is a de i ed p ope y o such p ob- lems) is key when analyzing he co ec ness o he gene aliza ion pe o med. To be mo e p ecise, when gene alizing a p oblem o designing a ecu si e algo i hm, i is necessa y o e i y ha he e is an ini ial p oblem, and ha all he p oblems a e o de ed by size. The emainde o he pape is s uc u ed as ollows: Sec . 2p esen s he gene aliza- ion o p oblems h ough se s o p oblems, Sec . 3includes he speci ica ion shee o he p oblem solu ion by ecu sion along wi h some illus a i e examples, and Sec . 4 p esen s a c i ical discussion o he p oposed app oach. Finally conclusions a e d awn and u u e wo k is p oposed in Sec . 5. 2 P oblem Gene aliza ion This sec ion p esen s he p oposed app oach: Sec . 2.1 explains he concep o se o p oblems in he con ex o p oblem gene aliza ion, Sec . 2.2 de ails how such se o p oblems can be used o p oblem gene aliza ion, and, las ly, Sec . 2.3 includes he gen- e al schema o ecu sion ha is ela ed o he p oposed p oblem gene aliza ion. 2.1 Se o P oblems In a ecu si e de ini ion i is always necessa y o s a om a se o p oblems P= {p,p0,p1,...}. In such se each p oblem is cha ac e ized by a se o p ope ies x= {x0,x1,...}. Each p ope y o a se o p oblems can be ca ego ized as: – Sha ed: sha ed p ope ies a e de ined as p ope ies o he se o p oblems ha ake he same alue o all p oblems o such se . – Indi idual: indi idual p ope ies a e de ined as p ope ies o he se o p oblems ha ake di e en alues o each p oblem o such se . Bo h sha ed and indi idual p ope ies can be ca ego ized as basic o de i ed p op- e ies. The inclusion o he la e , unlike he o me , is op ional since hei alues can be calcula ed om he alues o he basic p ope ies. De i ed p ope ies a e ypically included o he sake o cla i y. I is impo an o cla i y ha he basic indi idual p op- e ies a e he ones ha unequi ocally iden i y each p oblem wi hin he se o p oblems, i.e., he e a e no wo p oblems wi h he same alues o all basic indi idual p ope ies. Mo eo e , each p oblem o a se o p oblems has a speci ic size, ha is a de i ed indi idual p ope y. To be mo e p ecise, he size o a p oblem is de ined as an in ege g ea e han o equal o ze o ha is ela ed o he complexi y o he p oblem (i.e., how a is he p oblem om a case base). The e a e di e en ways o de ining he size o a p oblem. Howe e , i is necessa y o check he co ec ness o such de ini ion by consid- e ing ha he size o a p oblem should (1) be a unc ion o e some o he p ope ies o he p oblem, (2) be educed as a base case is app oached. The p oblems o a se o p oblems can be ca ego ized as: – Base case o a se o p oblems P: a p oblem o a se o p oblems is a base case when i has a di ec solu ion (i.e., wi hou pe o ming a ecu si e call). A p oblem ha is a base case has a small size. Mo eo e , he e can exis se e al base cases wi hin he same se o p oblems. – Recu si e case o a se o p oblems P: a p oblem o a se o p oblems is a ecu si e case when i does no ha e a di ec solu ion (i.e., i is necessa y o pe o m a ecu si e call o sol e i ). The solu ion o a ecu si e p oblem is de ined by combining he solu ions ela ed o p oblems o smalle sizes (i.e., subp oblems). – All p oblems, in he se o p oblems o in e es , e i y a p edica e d(x). This p edi- ca e es ablishes he domain o alid p oblems. 2.2 P oblem Gene aliza ion The key idea o sol e a p oblem in a ecu si e way is based on exp essing i s solu ion in e ms o ope a ions o e solu ions o a se o p oblems o smalle size. Fo his, in many cases i becomes necessa y o imagine ha se o p oblems om he o iginal p oblem (i.e., p oblem gene aliza ion). To be mo e p ecise, he p oblem gene aliza ion consis s o he ollowing s eps: 1. Adding, i necessa y, a se o addi ional p ope ies o hose ha al eady had he p oblem and classi y hem in o basic, de i ed, indi idual, sha ed, e c. 2. De ining he domain o p oblems o in e es h ough a p edica e. 3. De ining he size o a p oblem. 4. S a ing he base cases and he ecu si e cases. 5. Speci ying how each ecu si e case is educed o subp oblems wi h a smalle size. 6. Speci ying how each ecu si e case’s solu ion is ela ed o ha o i s subp oblems. 7. Speci ying he solu ion o base case. 8. Indica ing which o he p oblems in he p oblem se co esponds o he o iginal p oblem. 2.3 Gene al S uc u e o a Recu si e Algo i hm In o de o design a ecu si e algo i hm o sol ing a p oblem wi h pa ame e s x(o ype X) i is ypically ad ised o pe o m 2 unc ions. The i s one (i.e., unc ion , c . Algo i hm 2) ecei es as inpu pa ame e s o he ini ial p oblem o sol e x, and pe - o ms an ini ial call o a second unc ion g(c . Algo i hm 3). The la e is a ecu si e unc ion ha ecei e as inpu pa ame e bo h he pa ame e s o p oblem o sol e xand he addi ional p ope ies ha a e conside ed a e p oblem gene aliza ion (i.e., yo ype Y). F om now on he p ope ies o he gene alized p oblem will be bo h he pa ame e s o he o iginal p oblem and he new p ope ies added. Func ion is op ional. The e a e cases whe e he unc ion gis su icien and does no appea . This si ua ion is ound when i is possible o conside a b oad se o p oblems by a ying wi hin a domain he alues o he pa ame e s. One unc ion calls he o he as depic ed in Algo i hm 2. S (X x) { e u n g(x,y_0); } S g(X x, Y y){ ... } Algo i hm 2: Func ions in a ecu si e algo i hm (in Ja a) The gene al s uc u e o a ecu si e algo i hm is shown in Algo i hm 3. S (X x) { e u n g(x,y_0); } S g(X x, Y y){ Ss; i (b(x,y){ s = sb(x,y); } else { Y y_0 = sp_0(x,y); S s_0 = g(x,y_0); Y y_1 = sp_1(x,y); S s_1 = g(x,y_1); ...; Y y_{m-1} = sp_{m-1}(x,y); S s_{m-1} = g(x,y_{m-1}); s = c(s_0,s_1,...,s_{m-1},x,y); } e u n s; } Algo i hm 3: Gene al s uc u e o a ecu si e algo i hm (in Ja a) As ollows, concep s ela ed o Algo i hm 3a e de ailed: –x: pa ame e s o p oblem o ype X. –S: ype o he solu ion. –y: addi ional p ope ies (o ype Y) o he se o p oblems ha a e included a e p oblem gene aliza ion. –size(x,y): unc ion ha e u ns he size o he p oblem (x,y). –d(x,y): p edica e es ablishing he domain o (x,y). –b(x,y): p edica e ha shows i a p oblem is a base case –sb(x,y): unc ion ha e u ns he solu ion o a base case. –np(x,y): unc ion ha e u ns he numbe o subp oblems ela ed o (x,y). –m=np(x,y): he numbe o subp oblems –y0,y1,...,ym−1: a iables o ype Y ha s o e he subp oblems ela ed o (x,y).To be mo e p ecise, yi e e s o he i- h p oblem ela ed o (x,y). –sp0(x,y),sp1(x,y),...,spm−1(x,y): unc ions ha e u n he subp oblems ela ed o (x,y). To be mo e p ecise, spi(x,y) e u ns he he i- h p oblem ela ed o (x,y). –s0,s1,...,sm−1: a iables o ype Ss o ing he solu ions o he subp oblems ela ed o (x,y). Thus, si e e s o he solu ion o he i- h p oblem ela ed o (x,y). –c(s0,s1,...,x,y): unc ion ha e u ns he solu ion o xby combining he solu ions o i s subp oblems. 3 Speci ica ion Shee o he P oblem Gene aliza ion This sec ion de ails he shee ha is p oposed o speci ying he p oblem gene aliza ion p e iously explained (c . Sec . 2.2). The pa s ha a e included in such speci ica ion shee a e explained as ollows: – Types: in o ma ion ela ed o he ypes ha a e ele an o sol e he p oblem, e.g., he ype o he solu ion. – Sha ed p ope ies: sha ed p ope ies o he se o p oblems ha is ob ained a e he p oblem gene aliza ion. – Indi idual p ope ies: indi idual p ope ies o he se o p oblems ha is ob ained a e he p oblem gene aliza ion. – Size: size o he p oblem, which is a unc ion o e he p ope ies o such p oblem. – Ini ial ins an ia ion: ini ial alue ha is gi en o he indi idual p ope ies. – Base cases: i gi es in o ma ion abou whe he a p oblem is a base case. In case he e is mo e han one condi ion ha causes a p oblem o be conside ed a base case, one pe line is speci ied. – Solu ion o base cases: solu ions o he p oblems ha a e base cases. I he e is mo e han one base case condi ion, he solu ion is p o ided o each o hem on di e en lines, using he ope a o →. – Numbe o subp oblems: numbe o subp oblems ha need o be sol ed o ob ain he solu ion o he o iginal p oblem. – Subp oblems: subp oblems ha need o be sol ed o ob ain he solu ion o he o ig- inal p oblem. When de e mining hem, i is only necessa y o speci y he changes ha occu in he indi idual p ope ies wi h espec o he o iginal p oblem, since he sha ed p ope ies emain he same o all p oblems. Di e en subp oblems a e also speci ied in di e en lines, wi h he ope a o →. In case ha only one subp oblem needs o be sol ed, i s is de e mined h ough he condi ion o selec which one, wi h he o ma ci→si. On he o he hand, when he e a e mo e han one subp oblem, a supe sc ip is added o dis inguish he e e ed one ( 0 →,1 →,...). – Combine: unc ion ha ob ains he solu ion o he o iginal p oblem by combining he solu ions ha a e ob ained o he subp oblems. As can be obse ed, he e a e many simila i ies be ween he elemen s o he spec- i ica ion shee and he elemen s o he gene al s uc u e o a ecu si e algo i hm ( o de ails c . Table 1). Table 1. Rela ion be ween he speci ica ion shee and he ecu si e algo i hm. Speci ica ion shee Gene al s uc u e o a ecu si e algo i hm Types S,X,Y Sha ed p ope ies Indi idual p ope ies Domain d(x,y)p edica e Size size(x,y) unc ion Ini ial ins an ia ion y0 Base cases b(x)p edica e Solu ion o base cases sb(x,y) unc ion Numbe o subp oblems np(x,y) unc ion Subp oblems sp0,sp1,.... unc ions Combine c(s0,s1,...,x,y) unc ion 3.1 Running Examples This sec ion includes how he p oposed app oach is applied o wo illus a i e examples. Fo each example, (1) he speci ica ion shee ela ed o he p oblem gene aliza ion and (2) he ela ed ecu si e algo i hm a e de ailed. Example 1. Calcula ing he Fibonacci numbe s [5].The Fibonacci numbe is ecu - si ely de ined as ollows: (n)=nn≤1 (n−1)+ (n−2)o he wise Rega ding such de ini ion, a ecu si e algo i hm can be designed (c . Algo i hm 4) acco ding o he p oblem gene aliza ion ha is speci ied in Table 2. N ib(In ege n){ Ns; i (n<=1){ =n; } else { In ege y_0 = n-1; s_0 = ib(y_0); In ege y_1 = n-2; s_1 = ib(y_1); s = s_0+s_1; } e u n s; } Algo i hm 4: ib - Recu si e algo i hm o calcula ing Fibonacci numbe s (in Ja a) Table 2. Speci ica ion shee o sol ing he Fibonacci p oblem. Fibonacci Types Solu ion: In ege Sha ed p ope ies Indi idual p ope ies n: In ege Domain n≥0 Size n Ini ial ins an ia ion Base cases n≤1 Solu ion o base cases n Numbe o subp oblems 2 Subp oblems (n)0 →(n−1) (n)1 →(n−2) Combine s0+s1 Example 2. Bina y sea ch in a so ed lis [2].The bina y sea ch algo i hm is an e i- cien sea ch me hod, which inds he posi ion o a a ge alue wi hin a so ed lis . To do his, he algo i hm di ides he lis by i s middle elemen in o wo smalle sublis s, and compa es he a ge alue wi h he middle elemen . I hey a e equal, he sea ch ends. I he a ge alue is lowe , i mus be (i p esen ) in he i s hal o he lis , in he second hal o he wise. The p ocess con inues un il he a ge is ound, o un il i eaches an emp y sublis due o he a ge alue is no in he lis ( e u ning −1), which a e wo base cases condi ions. Fo his p oblem, he ollowing sha ed p ope ies a e conside ed: (1) lis o elemen s ls, (2) elemen ha is sea ched m, and (3) size o he lis o elemen s, ha is a de i ed p ope y n. To gene alize, he ollowing indi idual p ope ies a e es ablished: (1) index i ha indica es he s a ing posi ion o he sublis conside ed o he cu en subp oblem, (2) index j ha indica es he ending posi ion o he sublis conside ed o he cu en subp oblem, and (3) he middle posi ion k, a de i ed p ope y, be ween i,j. As de ailed, he p oblem only in okes one o he wo possible subp oblems. Mo e de ails a e gi en in Table 3, and he ela ed algo i hms a e depic ed (c . Algo i hm 5). As can be obse ed, he main algo i hm (c . bs in Algo i hm 5) pe o ms he ini ial call o he ecu si e algo i hm (c . bs gin Algo i hm 5) acco ding o he ini ial ins an ia ion o he indi idual p ope ies. 4 Discussion The p oposal p esen ed in his pape p esen s se e al ad an ages. To be mo e p ecise, on he one hand, he ac o analysing he solu ion o a p oblem be o e ca ying ou he implemen a ion i sel acili a es e o isola ion as well as e o de ec ion. On he o he hand, he gene aliza ion o p oblems and he ela ed speci ica ion shee allow o es ablishing a sys ema ic way o designing a ecu si e algo i hm o sol ing a speci ic p oblem. Based on ou expe ience as eache s o p og amming subjec s in he i s uni e si y- le el cou ses, s uden s a e eluc an a i s o speci y he gene aliza ion o p oblems h ough he speci ica ion shee . On he one hand, his is some hing new o hem, and he e o e, a pe iod o lea ning and aining is equi ed. In his pe iod, s uden s acqui e he necessa y knowledge ega ding he meaning and use ulness o each o he p ope ies ha a e included in he speci ica ion shee . On he o he hand, speci ying he p oblem gene aliza ion is mo e ime-consuming han di ec ly implemen ing he solu ion. Mo e- o e , he applica ion o he p oposed app oach makes sense o p oblems ha p esen s ce ain cha ac e is ics. To be mo e p ecise, he p oposed app oach makes mo e sense in he case ha designing an e icien ecu si e algo i hm o sol ing a p oblem is no i ial o he s uden s, i.e., p e ious analysis is equi ed (e.g., c . Example 2). Howe e , he e a e some p oblems, i.e., hose p oblems whose de ini ion i sel is ecu si e, ha Table 3. Speci ica ion shee o sol ing he Bina y sea ch p oblem. Bina y sea ch Types Solu ion: In ege Sha ed p ope ies ls: Lis <E> e: E n: In ege (de i ed - size o ls) Indi idual p ope ies i: In ege j: In ege k: In ege (de i ed), k=(j+i)/2 Domain i∈[0,n)&& j∈[i,n] Size j−i Ini ial ins an ia ion (0,n) Base cases e=ls[k] j−i<1 Solu ion o base cases e== ls[k]→k j−i<1→−1 Numbe o subp oblems 1 Subp oblems e>ls[k]→(k,j) e≤ls[k]→(i,k) Combine s0