### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Class Note for ECE 474A with Professor Lysecky at UA 3

### View Full Document

## 20

## 0

## Popular in Course

## Popular in Department

This 13 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Arizona taught by a professor in Fall. Since its upload, it has received 20 views.

## Reviews for Class Note for ECE 474A with Professor Lysecky at UA 3

### 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: 02/06/15

ECE 474A57A Compute Aided Logic Design Lecture 9 BranchandBound and Simulated Annealing 5m mew Logic Optimization Techniques Logc 0pm mizan on Techniques KrmaDS Gvauhicai QuineMKiuskEV Exam Aigaimm mm miniminiim Rwniumn ommm EstessD Hemsnt 7 weii see mis m2 stun Oiher Generaiized Aigoriihms I Brznth zmrbmnd Simuafad Anneaiiru mam mme exiscs my gneni zigunihm rm be 2Dpied in 2 vzvieivofvwbiem am on ihe idu of dam ire Iniegev my ngnmming ILP 9me z Dwgzmming v MM Wham may GemiizNQunihm 5m mew Decision Trees Decision tree Enumerauon approach in which We have Hdecisiori variabies arid iistthe 2 possibie vaiues P1 P2 P3 P4 Gwen a mime impiicam chan and me cunESpundiHE Essentiai mime impiicamsi mmduwe denea minimum cmiwnii me YEmainiVVE mime impiicams 7 X X XX M15 5m mew Decision Trees P1 V2 P3 P4 RENE2012Essentiaimimeimpiicams ihEVaanianWin MEEDVEV Numbevihe YEmainiVVE mime impiicams 5 ms easieiini X usiuiead X M15 XX Let s sianuuiuecisimiiiee Whateveihe dEEisiun u mm Shuuidwe inciude Pi in mm mm Shuuid we inciude P2 in mm mm Shuuid we inciude P3 in mm mm Shuuid we inciude w iii uuv cmeiv sum WWW Decision Trees The ieaes aie vuuv pussinie S imi ns my V1 72 m m mums ass 4 my me mm my V1 Ewei 72 m m mam mums ass 3 cm Mm Boxer my Boxer min Vsiimyeicos 2 Vsiimesicog 2 Vsiimesicog 2 sum WWW Bra ncha ndbound Idea Brandmaridbourid Swazi Dunmai sdunnns mav Exist we miv need in rd me ice is thatmavbe we Univ have m Visit Dan DH E deusieri v22 We can emmace the im mum in a subvee and that im mm is hghei man the miimt minimum we mm need in iuck sum sumee k iiied subhee cum Minimum 3 sum WWW Generic Branchandbound Pseudocode ECDI F u mvmnlsu lt F mmsu F mum F tunede 4 damnancems mvhwmmnxruvdmescummsammn wnh mese mm mwvms emu vanabks and vvhes Fewcm Klevmmz axeFlt m WWWquot U smmsmmmsmw K ismmzmims Vvahdandbeuermanenimvsammn updmsa manand velun mmsen m gt gt cmmm awerbmmd mm mew see mhe sAMree 5 m aakmv 1 L e Lmuowm F zuvenlSo n m L a u rum no o unm Make ademsan mm may we mm mdudeem ud a mums new w mmwmm x momma s F Ummntsoultxi Mm eumumummaest szMS J L Fetuvn5 us summamm WWW 55quot s Ecv F u Mensaquot WW mm a a We Emmi pm velum mngmunom 5 s 4 Return begsahman 5m new Bra ncha ndbound Pseudocode Inua caH m 50gt mnemsun set an empty was bmnd U set an the mmba m seams puma mmcams 1 Guznnlee w the m whdm uuun We Wu be zzmued F s mecmmtmrsmntemanm CaH mREDUEG m m swam me mm m yamsan mom mm New Art 2amp1er u m muse Remuvldommlrgvov Remuwdommledm umn cm M unm mzlvx Emplv mm mm Sphmngvarwab ex Vanab e 52mm has rm moan m cunacmzs muads vun nme Fm 2 gm Eamon fut m uDDU mm m m whmz Eamon me mm mm an m Pmmna anddatesa mm w my WWW mm mm be put ufuphmz mm cam w mm m m m mm mm m m 2 man a hung mm m new Branchandbound Lower Bound Calculation How do ca cuam me ower bound of a subwee vanes dwmnng an vcuv mum Mmmum cave mum kw buund numbevof Fm md zznl zo umn mde w st MaximaHy Independent Set st Ema m the rumba unnnepmdmuws m the name Row m mdeperderl F nomhpw w mm the mm mm numbev 0mm thzml veauwed m towu m m WWW 1 n We Want mystcasa su we lack the avgestset 1 a 5 m Ifnmrdwmdmtvmls ave cum ihmav mm in s mm mm s at 53512 IfmzmxCvthznozduvnzmvxz mWXMh zhmu dhml quotquot5 2 enz ed Mm e mzmx mg 2 WWW mm zu umn m mum m towu In em new Finding MIS M S owcw Heunsu ande a gornhm can be used m nd MIS H M H memes mws thn M a a ddenndmws massan Wm mm CHOOSE SHORTE39STJOW subuucadue can be 7 s u lt0 mm n swam wavs M Dagmwmszcmejowqm J mMHMHm Oohm x 39Ruw u vow wlh the Md mm mm ME mum bvezwng m m wmguwm my com 2 39Ruw u e eded w m umn mum y u mum bvezwng m m wmguwm my m 2 v w um 1 ng m x x x M x x m x x x w zzkuhled mam Au x39 m m m x39 m zu umn x 2 2nd vow x w zzkuhled w 2ddngz x39 n m umn x z 5m mew MSQUCK Example Use MISQUIGlt apnon 1 to nd MIS M15 z m stltn MdmwlluMIS Dem Hunting m z 7 M15 02 Mdmwzmms Dem Hunting m 55 MIS 1 3 Low bomd o 2 no esserma s premousw added W MSQUCK Example Use MISQUIOlt apnon 2 to nd MIS st u u H 395 K stltn Mdvownoms M MW m z 7 a m 39 321quot Wm mmwmm 2 l l De ele devednng3 mummme M s 139 539 6 Wml wdalatlvMIXJvuhmkad Low bomd 3 no esserma s premousw added Wmmomm mww 5m mew Bra ncha ndbound Exampxew Usu39vg Branmanabwnd nd rmrumum cover outuacDFUlt M x x mm m mmquot a m umml m M mm m k m m mmb e mm m z m mam 2 mm mm m o Cazu ae awubaundanxublree minim Em W N mm mm wwwme mm ms 5 Hum m 7 5 mgmmmmm 5m mew Bra ncha ndbound Exampxew 0H m W F u W gtlt nu m x x x z m I l 2 Wm mm mm m z mmmm m U u 4 u m a I a mm mm W mm V M x 5m mew Bra ncha ndbound Exampxew ommmm Hum mx 3 n 1 m2 8 X x WWWWmnmmmm m xx mam ml u 2 mm m n 3 WNW o am mmmmmm X minim 33 m Wk WNW m m 5 mm s 7 5 MMWM ummmm W quotMu mm Done All opuons x mm H examined 5m mew Bra ncha ndbound Examp e 2 Usmg Brandwrandrbwnd nd mu umum cover Ecv F u o x z z 7 xmmm my a m umml m m an m mam mm mm m Cazu ae awubmmd an ublree mm Wm m m m m mm 1 a mm ms L Bu Na x zm 5 30 u mum x 5m mm M W m k m Mqu Bra ncha ndbound Examp e 2 2 am F u m m mam 5m mew Bra ncha ndbound Examp e 2 am F u m 7 y 0 MM v1 mm mm m 1 Cazu ae awubmmd an ublree mm mum ms WNW mxm ms 5 30 u mum x 5m mew p new BMW 7 L W m mmquotan mm Bra ncha ndbound Examp e 2 KW yum m m W Va v9 unvn 2 MM 2 mmmmm wmmmmmm uniqusz 5 WWW mg WWW 5 mm 5 x vsnva 7 s zm Markham 5 mm m mew Bra ncha ndbound Examp e 2 am W u ltvxvsvsgt M 7 vs 2 MM 5 3 n be 5 mm ya I 5m mew Bra ncha ndbound Examp e 2 am F j u m m 2 MM 2 mmmmm o Cazu ae awubaundanxublree mm WM a quotmagma ammo 2 5 mu Na s x 7 S WF UzumnlSn ntX mm m u m mew Bra ncha ndbound Examp e 2 amnmm FMvJvsvsvI 2 Wm H z mmmmm o Cazu ae awubaundanxublree mm WM a quotmagma WWW 2 5 Hum s 7 s zmawmmm x Cnl5 LNa a 9 FUzunenlSn nAx mmwmm W 3 mmurhwrm u WWW Bra ncha ndbound Examp e 2 am S u mus mu vswgvl 2 MM 2 mmmm m o Cazu ae awubmmd an ublree mm m mm mm wmwzz 3 5 Hum M mm m k M mm m m mew Bra ncha ndbound Examp e 2 EcvFummmsonultvl mm 2 Mmm 3 smmmm 0 can 22 mum an m mum W m mgme WWW 25 5 Laum s 7 x a 930 u WNW m vemmBESL UHOMS 9 EJ3352me 5m mew Bra ncha ndbound Examp e 2 Ecv F u o z Reduze mzmx 3 smmd Na mmmmWm mm W m WWW NM m w x 5 mu m s p 7 Ho u mm H x was m a quotMu mm 5m mew Bra ncha ndbound Examp e 2 a m Ecv F V u v n 2 Wm w 0 mum m m N m BMW 5m mew Bra ncha ndbound Examp e 2 a m Ecv F V u v n z Mmm 3 WWW quot W 0 mum twang 0 cm mmmm an gum mam mums m u 5 n be a 29 WNW mm m ms 5 Hum Done All options mun examined w Km m a mm m mew BranchandBound Summary BrandwrandrBourid aigorimm used m meip quot 5 determine a minimai cover We have a seamed Dime mime in quot 51 33 I mmse ivtm i 2 P1 P2 P3 P4 3 1 15 an n u u in is m With one snoud We Choose rst Methuds m mmse sdimmd Vaiiabie 7W2 skiDDEd Eaiunm snii Emmai mavbeiust siuwa Determining the iower bomd is veryimporizrt we want in be mime 5i we dm39t wasta my me Hume ths sewsmuudsui be mt Addumaiiy as prime impiicarits are added We can use roWooiumri dominance m m arid simpiify remainrvg matrix I Hans tn Speed up aiuait m iowhuund A iewema s Soiunori is exact opnmai ruming nme varies on seiecnom process arid bouncing caicu anon sum mew Logic Optimization Techniques Logc Opt mi zanom Tedmmiqies KrmaDSKSvaDhcai QuneMKiuskEMExanMgmthm ESDYESSDHELHSQE other Generaiized Aigorimms I Evanmrandrbmm I Slmulzmd Nuazlma mam mme Exists Iniev Lnezv wogzmming ILP Dmiemognmmmg emieiiqmim sum mew Simulated Annealing Background Simuiaued Amneaiimg Name and mspmm me cm annaaiiru m metaiiuiQV Hem and mtmiiad ceding d a mataiai m mice decensnmdease svmut Appiied m iocai Search methodoiogv to avoid gemmg smdlt at me iocai minimum m Viabaiabsaime sum mew 10 General Simulated Annealing Pseudocode aivim ivlh wim ba hga s anxmznga aiazi x ME iZ EsiE 9i ush zil izinia b h iu mlwdva aiazi x ME awash a Simulated Annealing Derive a new solution S by randomly making a change to the current solution S initial solut on T in tial temperature gt0 Whle T gt O Determine the cost difference between the old and new 539 pick a random neighbor to S solution Is the new solution better C cost of S cost of S CgtOX S S lfthe new solution is better keep the new solution else r random number in range 01 Randomly we sometimes take the worse solution AVOID LOCAL MINIMUM m 1el CTI f The probability of this happening corresponds the to I r lt m the temperature the higherthe temperature early in S S the algorithm the more ikely we take this chance e mathematical constant 271828 Decrease the temperature T reduced T lt This is the cooling schedule how fast does the temperature decrease ECE 7 a1575a 31 of 38 Susan Lysecky Simulated Annealing Cooling Schedules at M y hamxmnwm M m Choosing initial temperature and cooling schedule has great impact on the algorithm Make sure we run long enough to find a good solution Make sure we get out of local optimum take chances on worse solutions Many options available no definitive way to choose these t TuTN x1tanh15 TN Simulated Annealing Coo ing Schedu es Brian T Luke PhD httpl conyxnc fcrf govlukebsimanf1html ECE 7 a1575a 32 of 38 Susan Lysecky Simulate Annealing Example mm same we g imm as new 539 w W wwa 3 5 3 31 39wt i 113 at we m r 4 at M w w v as am 539 6 m we 5 a3 i3 39wt i 5113 m we we 1 2 3 4 How do we apply to the minimum cover problem P1 r m m P2 39 1 Choose an initial solution set an initial temperature p3 P4 amp 8 2 Is temperature T gt 0 Yes P5 39 P6 3 Make a random change to S What can we change 0 Add ng another prime impl cant to our cover 0 Removing a prime implicant from the current cover JRemOV P2 4 Determ ne cost difference CcostofS costofS c4 3 1 We should also consider if th 5 solution is correct Yes a Is the solution better Yes Keep new solution 6 Decrease Temperature T T 25 75 33 of 38 Susan Lysecky 11 Simulate Annealing Example z Mzk 2 mm hm lo 5 2 g ISIS umemm u o u 2 WWW WWWWWM 2 VS a g o Delevmmzmldmmme 6 u wwm Mam rm 22W 2mm ya 5 M 4 2 x the mum balm No b 2mm mamwmpi an 5 WWWquot We m winizngm 7 Deaezxe Yemvenlum 5m mew Simulate Annealing Example 2 mmmmws u r quotmumwi u a a 2 MW WWWMWhem u 395 O C 2 mummide 6 wwm Mam rm 22W mm ya 2 x the mum mum m s Dene Ymvevzlure 5m mew Simulate Annealing Example mum 2 u m 22 22 22 z Mzkez mm mm ms 2 g Y TZIJTSZSFi me Mm w m ym m u a 2 WWW mxmwmmmtm 2 VS 2 MM imminent 6 Wummmm mm mm ya 2 klhexolulimbelley7No b Should wt nndmlvzzmp l 2nvw2vx7 ME mm We m mwmwsu um m 2 magnum s Deanne Yempenlue 5m mew Simulate Annealing Example 1 xgumpmmrsnmu m m2 m m Done 2 g solmonP4P5Ps u u C vs 0 a w a y u Is 11 sduuon opumaP ND IdeaW ms a gonmm Wou d rm orger so We can ew ore more of me somnon space and posser nd a bemr sduum 232 3quot Conclusion Conswdered severa ogwc opmmzauon tedwmcues Kmps 39 Qu neMK uskEv Esuvessu Cmswdered severa other generahzed a gonmms usem for ogwc opmmzauon as We as omer appmums I Evanmramrbmnd I S muafad Anneahru Manv wave was Negev may ngnmmmg ILP Wm mwmmg GWMQWM sm mew 13

### 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

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

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

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

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION 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 support@studysoup.com

#### STUDYSOUP REFUND POLICY

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: support@studysoup.com

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 support@studysoup.com

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.