need to write the algorithm for the given data

K now le d ge R etr ie val P art 2 :

I m ple m en t s earc h a lg orit h m Dead lin e:

F rid ay 8 th O cto ber F or t h is p art, w e h ave c re ate d a F unctio nal O bje ct- O rie nte d N etw ork ( F O ON) m erg in g y o ur l a belin g d one i n t h e p re vio us p art.

N ow , y o u h ave t o i m ple m ent s e arc h a lg orit h m s s o t h at i t c a n e xtr a ct a t a sk t r e e t o p re pare a ny d is h e xis tin g i n F O ON.

A t a sk t r e e h as t h e e xa ct s a m e s tr u ctu re o f a s u bgra ph. In put: Y our p ro gra m s h ould h ave t h e f o llo w in g i n put: 1 . F O ON ( A . tx t f ile ) 2 . A g oal o bje ct t o s e arc h . 3 . Lis t o f i n gre die nts a nd u te nsils a va ila ble i n t h e k it c h en ( A . tx t f ile ) F O ON, s a m ple g oal o bje cts a nd a k it c h en f ile w ill b e f o und i n C an va s F ile s s e ctio n. T a sks: 1 . Im ple m ent t w o s e arc h a lg orit h m s. 1 . Y o u c an i m ple m en t a n y u nin fo rm ed s e arc h a lg orit h m ( e .g .

B FS , D FS e tc .) t h at y o u t h in k s u it a b le h ere .

I f t h ere a re m any p ossib le path s t o r e ach t h e d esir e d n ode, j u st o utp ut t h e f ir s t o ne t h at y o u fin d.

A p ath i s c o nsid ere d a s o lu tio n i f a ll t h e i n gre die nts i n t h at p ath are a va ila ble i n t h e k it c h en.

A s o lu tio n i s p ro vid ed h ere : h ttp s://a rx iv .o rg /p df/1 902.0 1537.p df 2 . M odif y t h e f ir s t s earc h a lg orit h m b y u sin g a h eu ris tic .

T o e xp lo re a n ode, i n ste ad o f c h oosin g a p ath r a ndom ly f r o m v a rio us o ptio ns, c h oose a p ath t h at r e quir e s m in im um n um ber o f i n put o bje cts . F or e xa m ple , i f y o u f in d t h at s cra m ble d e gg c a n b e p re pare d w it h eit h er { e gg, o il, c h eese , o nio n} o r { e gg, o il, s a lt } , t a ke t h e p ath t h at r e quir e s { e gg, o il, s a lt } .

B eca use , i n t h is p ath , y o u n eed f e w er i n put o bje cts . 2 . V is u aliz e t h e r e tr ie ve d t a sk t r e es a n d c h eck i f t h ey m ake s e nse .

Y ou sh ould u se i t t o d ebug y o ur p ro gra m . 3. S ave t w o t a sk t r e es ( o ne f o r e ach a lg orit h m ) i n t w o s e para te . tx t f ile s.

I f a ta sk t r e e c a nnot b e r e tr ie ve d ( th e k it c h en p ro vid ed t o y o u d oesn ’t c o nta in all n ece ssa ry c o okin g u te nsils o r i n gre die nts ), j u st p rin t w hic h i t e m s a re m is sin g. P seu doco de: T he p se udoco de p ro vid ed h ere i s f o r t h e a lg orit h m m entio ned i n t h e o rig in al F O ON p aper. Y ou s o lu tio n c a n b e d if f e re nt t h an t h e f o llo w in g o ne: 1 . Id entif y t h e g oal n ode G a nd d ete rm in e w he th er i t e xis ts i n t h e n etw ork .

I f i t d oes, p ro ce ed t o n ext s te p.

2 . Id entif y i t e m s t h at y o u h ave i n k it c h en a nd k e ep t h em i n a l is t K .

3 . C re ate a q ueue S t h at c o nta in s i t e m s y o u d o n ot k n ow h o w t o m ake . E nqueue G t o S .

4 . D equeue e le m ent E f r o m S .

I f E i s a lr e ady i n K , S earc h f o r a ll f u nctio nal u nit s i n F O ON t h at h as E a s o ne o f i t s o utp ut n odes.

A dd c a ndid ate u nit s to l is t C .

F or y o ur s e co nd a lg orit h m , s o rt C b a se d o n t h e n um ber o f i n put i n a f u nctio nal u nit . 5 . R em ove t h e f ir s t c a ndid ate a nd c h eck i f w e h ave i n put n odes i n K .

I f w e have a ll i n put n odes, a dd f u nctio na l u nit t o f in al t r e e T .

A dd t h em t o K .

I f a ny i n put n odes a re m is sin g, a dd t h em t o S .

A dd E b ack t o S .

6 . If K c o nta in s G , t h en e nd t h e s e arc h a nd r e tu rn t h e f in al l is t o f s te ps (fu nctio nal u nit s ) T ; e ls e , g o b ack t o s te p 4 a nd k e ep s e arc h in g t o f in d o ut h ow t o m ake n eeded i t e m s. O utp ut: T w o t a sk t r e es s a ve d i n t w o s e para te . tx t f ile s, o ne f o r e ach s e arc h in g a lg orit h m . H ow y o ur p ro gra m w ill b e t e ste d : I w ill h ave m y o w n k it c h en f ile ( d if f e re nt f r o m w ha t y o u w ill h a ve ) a nd a f e w obje cts t o s e arc h .

W it h t h is k it c h en f ile , I w ill s e arc h t h e o bje cts i n F O ON a nd ch eck t h e r e tr ie ve d t a sk t r e es. S ubm is sio n: You c a n u se a ny p ro gra m min g l a ng uage f o r t h is p ro je ct.

C re ate a z ip f ile in clu din g e ve ry th in g t h at i s r e quir e d t o r u n y o ur p ro gra m .

T ha t i s , ● F O ON ( .tx t f ile ) ● Y our c o de ● K it c h en F ile ● Tw o r e tr ie ve d t a sk t r e es i n t w o s e p ara te . tx t f ile s. ● A r e adm e f ile w it h t h e i n str u ctio ns a b out h ow t o r u n y o ur p ro gra m .

A ls o m entio n i f a ny p acka ge n eeds t o b e i n sta lle d. N am e t h e z ip f ile w it h y o ur U ID ( e .g .

U 13 611 582.z ip ).

S ubm it i t o n C anva s. T his p art o f t h e p ro je ct i s w orth 5 0% o f y o ur f in al p ro je ct’s g ra d e.