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: Trace Mante MD


Trace Mante MD

GPA 3.61

C. Huang

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

C. Huang
Class Notes
25 ?




Popular in Course

Popular in Computer Science and Engineering

This 53 page Class Notes was uploaded by Trace Mante MD on Monday October 26, 2015. The Class Notes belongs to CSCE 350 at University of South Carolina - Columbia taught by C. Huang in Fall. Since its upload, it has received 36 views. For similar materials see /class/229582/csce-350-university-of-south-carolina-columbia in Computer Science and Engineering at University of South Carolina - Columbia.

Popular in Computer Science and Engineering




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/26/15
5H Announcement CSCE 350 Reading assignment Chapter 82 84 Data StrUCtUl39eS and AlQOl ltth Homework 6 was assigned on Monday and is due on Wednesday April 8 in ChinTser Huang Class huan ctcse39sc39edu Please download it from class webSIte Have your answers neatly typed Explain your answer clearly and adequately by showing the steps University of South Carolina was2mg 2 Warshall s Algorithm Transitive Closure 7 Warshall siAlgorithm Computes the transitive closure ora relation Mea a path exists between two Vertices i j iff there is an edge from i to j or there is a path from i to j going through vertex 1 or Alternatively all paths in a directed graph Example onransmve Closure there is a path from i to j going through vertex 1 andor 2 or there is a path from i to j going through vertex 1 2 andor 3 or I I l I 3 3 there is a path from i m j going through any of n 1 n n the other vertices adjacency mah lx Emmamm 3 Mus2mg 4 g Warshall s Algorithm Warshall s Algorithm In the 611 Sta e dewrmineil a ath exists between two construct solution through series of boolean mahiceskm RW u g l n P 1 k using increasing subseE of the vertices allowed as inmrmediate Vquot s W quot3 J Vquot 5 WE quot R 391 11 path using just 1 191 RMHI39J or Radium and R quot1kij path from ito k and from klo i usingjust 1 k1 WEIRmm 5 DVDS2mg b Warshall s Algorithm matrix I generation Recurrence relaung elemenB W to elemenB of RW is Win it implies the reudwrnd rules rer generating RU run Run mlJ 0r WUlt1 and mllt11 Rule 1 iren elemnt in yew rend EDlumnis 1n Run itremains 1n m1 Rule 2 iren Elemmt in yew rend Ulumn is u in RU u it nes m be changed m 1 in w rend only r the element in re yew rend Ulumn land the Elemmt in re Ulumn end row kare both 1 s in I u mamas Warshall s Algorithm matrix I generation Hanna 5 a Rule larchangmg zeros m Warshail s alganmnr waxmus x g Warshall s Algorithm example n mamas Warshall s Algorithm pseudocode I and analysrs use HM rrnnnn in n n rmwwu M unilim t n I new inth m 139 n nhd Milwauw nummmumunentnmhd r R m e r m 1 raw 1 1quot m rm 1quot I n new n lur n in nun n in M Iumiv me ef ceno Space ef ciency Mamces can be Written over their predecessors Waxmus m Floyd s Algorithm All pairs l shortest paths Problem In a Weightad dodrepn nd SHDrfE paths between every par vaatites Same idea construct sdidndn Hmugh seres er nemees mu a A using nereesrnd e1bsee urine venites eudwed e intermadiate Examle 2 1234 1234 7 l mlm 1U1U34 Z Z Imus 22 I 56 3 3927111 377 I1 4 mm 4 l g enema Floyd s Algorithm matrix I generatIon on me tech tern n Lhezlgnrithm determines shnnesl paths between every pair nf vmicesijthat Ilse nnly vem39ces amnng 1 k as intamedizte DWII39J min 5quot quotWI 0quot l39rkl t milsi quot quotTML 1 Wm waxmus 12 K mule1 x g Floyd s Algorithm example mama 3 Floyd s Algorithm pseudocode I and analyss ALGORIYNM I mi Map linemanmm n n m New nnnm Hr m Mom mnwmnin imuum m mml l Iln Wm ii ni mull in nne ef ceno 607 Space ef ciency Mamces can be Written over iheir predecessors Note Shortest pains me mselves can be found too waxmus 5i Knapsack Problem by DP Given nitems of ncega WEighE w values Knapsack Problem by DP I example Example Knapsack ofcapaaty W 5 W Va V2 Vquot 1 2 12 a knapsack Dfinmgertapatity W 2 1 10 nd musi valuile subset Uflhe items that t into the knapsazk 3 3 20 4 2 15 capacity Consider n mte de ned by rst Htams and eapanty s m o 1 2 3 4 Le 14w be apmnai value of sum in awte hm 0 max WM w WI WJ ifszu W 2 V 12 1 Viil 39 WM mm m W2 V2 10 2 w 3 1 2o 3 initial Dnditinns 14w u and mu u caai nd MW W 7 2 VF 15 4 a Mama 5 Warm ls Solving Example of Knapsack I Problem us39ng DP M n vimrm view 0 W V vu n mama n Announcement CSCE 350 Reading assignment Chapter 93 5 Data Structures and Agorithms Homework 6 is returned and discussed today Highest 39 Average 321 chinser Huang Homework 7 is assigned on April 8 and is due huan ctgcse SC edu on Friday April 17 in class I I Please download it from class website University of South Carolina 39 Have your answers quotEl Y tYPe Explain your answer clearly and adequately by showing the steps mun2mg 2 1 Announcement Notes on Kruskal s algorithm Iwill travel to Oak Ridge National Lab Algorithm looks easier than Prim s but is next Monday Dr O Kane will give a harder to implement need to check for substitute lecture C Cles39 less ef cient El log lEl Cycle checking a cycle exists iff new edge connects vertices in the same component Union hdalgorithms see section 92 mun2mg 3 mun2mg 4 Dijkstra s Algorithm on D39jkstra Algorithm Undirected Graph Using greedy stratng to find the singlessource shortest paths Similar to Prim39s MST algorithm with the following In Floyd s algorithm we find the allspair shortest paths which may difference 9 quotecessa39Y 39quot mam appl39cam smrt with tree consisting of one vertex Singlessource short path problem 7 find a family of shormst paths t r h m d t t t d h sumquotg rem a given to any one 93 33quot1 0 dgge 3 WW 99 y Cerba39nly allspair shormst paths contain the singlessource shortest 1 Dam But Hey 15 algomhm has 0 VP complex track of shortest path from source to ead1 of the vertices Th r are many algorithms that can solve this problem here we introduce the Diystra39s algorithm 39 at 95 quot 99 WSW 7W m 7 add I A n L A L connecting a vertex in tree I m one not yet in tree w a choose from fringe edges nonnega ve thisisthe greedy step edge m with lowest dsv dvw algorithm stops when all vertices are included mun2mg 5 mun2mg a CSCE 3 50 5 Data Structures and Algorithms ChinTser Huang MW Unlverslty of South Carollna SI Announcement Reading assignment Chapter 42 43 Homework 3 is assigned on February 16 and is due on Wednesday February 25 in class Please download it from class website Have your answers neatly e Explain your answer clearly and adequately by showing the steps nzlxmna z 5 Quicksort Selecta pVDMparuumll39g eleme t Rearrange the llstso matall the elements W the posluons before me plvot are smaller than or equal to the plvot and those alter the plvotare larger than or equal to the plvot Exmarge me plvothlh me last elementln me rst i e lt subllst ri e plvotls new ii l re nal posmon Sortlhe two sublls ru Wm w rluluurmrlrruuumtmur quotl mum ll ll ls tplrunlw alum lll e l AD Sp Ax gt p nZlmnni a nZlmnni o ALGORITHM l Pseudocode of Quicksort ruuwlrl ill llll ulwr w ill r rlu ll ll utrlluulnmltrl lllurulu luuut CSCE 350 5 Data Structures and Algorithms Chin ser Huang huangctcse 5c edu University of South Carolina I Announcement Reading assignment Chapter 52 Homework 3 is returned today High 4 Average 3 35 Homework 4 is assigned on February 25 and is due on Wednesday March 4 in class Please download it from class Website Haye your answers neaby ty ed Explain your answer cieariy and adequately by showing the steps nmmnna z Variabl ized ecrease A Size reduction pattern yanes from one iterabon of an algorithm to another Example Euclid s algorithm for computing tne greatest n iyisor cdmn gcdn m mod n e argurnenm on tne ngntnano side are always smaller than those on the left and side But they are not srnaiier neither by a constant nor by a constant factor nmmnna I Insertion Sort This is a typical decreasebyone technique Assume A0i 1 has been sorted how to achieve the sorted A 0I Solution insert the last element AI to the right osition I Al14liA1ln l L YcuiiJlltim Alil nmmnna i Example Sort 89 45 68 9o 29 34 17 wits 68 9o 29 34 I7 Ea t ig Lo N w 5 i7 25 34 A5 55 so so nmmnna 9 Pseudocode of Insertion Sort ALGORITHM Iiiiiiiiiiuiillll n 7 ill iJSui h stun mm in iiht rhun in mi mutt tlii r e llnliiiiitlt iuliluulcnwnls Miiymtlti r lilli WI 7 l r mum il rriieiiri unuyun mint illtn llmlimliiiiiniitlw furl l Imi I in i l n mmm 5 Analysis of Insertion Sort Time ef ciency Cme quotII1V2 E nz Cavgn quot24 E nz Cbe Ur II 1 E II also fast on almost sorted arrays Space ef ciency inplace Stability yes Best elementaw sorting algorithm overall Binary insertion sort D2272UEB CSCE 350 Data Structures and Algorithms ChinTser Huang huangct csescedu University of South Carolina 5H Announcement Reading assignment Chapter 44 45 Homework 3 is assigned on February 16 and is due on Wednesday February 25 in class Please download it from class website Have your answers natly typed Explain your answer clearly and adequately by showing the steps Draft lecture slides will be available on class website one hour before class u2232m9 l Binary Tree A binary tree 739is defined as a finite set of nodes that is either empty or consists of a root and two disjoint binary trees 72 and 7 called the left and right su btree of the root u2232uw Binary Tree Traversals For analysis convenience we can extend binary trees by replacing empty subtrees by special nodes Internal and external nodes externalinode internaLnode1 O internal gt D external D u2232m9 Binary Tree Algorithm 1 Height of a binary tree ALGORITHM HeightT if 4 retumrl else retum maxltH21ghtTl ngmm 1 Input size II 739 nodes in 7 basic operation quot Recurrence AnT AnTl AnT 1 for nT gt0 A0 0 9 Ann why 9 Ifthe basic operation is the line to check whether a tree is empty 9 CIr2n1 why u2232uw Binary Tree Algorithm 2 Traverse the binary tree List all the nodes Pleoldel traversal root 9 left Subhee 9 right Subhee Inoldel traversal left Subhee 9 root 9 right ilbhee Postoldel traversal left ilbhee 9 right Subhee 9 root ALGORITHM przmdzrm if T 4 output Tm mammal przmder x What is me efficiency U2232EEI9 SI Binary Tree Traversal Example 1 Large Integer Multiplication Some appllcauorls notably rnodern cryptology requlre rnanlbulauon oflrltegers oyer 100 declmal dlng long Reorder Sucn lrltegers are too long to t a slrlgle word of a Inorder computer therefore they requlre speclal treatment 39 Conslder tne mulup canon of two sucn long lrltegers Postorder lfwe use the clasle penrarldrperlcll algondnrn to muluply two ndlglt lrltegers we need dlglt mumpllcatlons Carl we desgrl a dlvlderarldrcorlquer algondnrn to solve dnrs problem wldn better emclency7 mm 7 WW I The Ba5c Idea I One Formula We want to calculate 23 X14 leerl galaquot and EDA corrpute FE b slnce 232 mu quot 1 l Wenaye ca l7cil1cll cnlquot We have 231421n 31uquot11u 41nquot Wm 211n13124m 341uquot m n n 17n vvnlcn lrlcludes four dlglt multlpllcauorls 72 1 01 angtbibngtnc1cngt 3quotl2quot4 2314e21e34 Tnat means only three dlglt mulupllcauorls are needed Therefore we only need three dlglt rrulupllcauorls to willle two Zrdlglt lntegers mm a mm gl To Multiply Two n digit Integers l EffICIency Assume ms eyen wnte Tnerecurrencerelauonls aeqmmmnambemnlhbn Tn3TnZfnrngt1Tll The cab11nquotcmquot cn1uquot Solvlrlg lt by backward subsumuon for H2ylelds 1 1 17 Hr 3m 31m 27 rm n 3 5 1 ngt 17117ngt51 5quot To calculate dne lnyolyed tnree mulubllcatlons e recursronl Stops wnen n1 Therefore Tn W Size lt nztzlmna nzmm l Strassen Matrix Multiplication BruterForce mm matrix muiubiicauon needs number multiplications For example multiplying two 2x2 matrices needs 238 mul plica oi is n where mm In an bi mu bu 3 y We Can Reduce to 7 Multiplications n m mmewm my New where quota an 17m 4 m1 nn nxqx bnn mi 01 an 17m 17 Yvann Tbnr ii Vnianraiigtquot in iigt Vquot 11quot quot07 717m nmimna m l Divide and Conquer Permian the mew inn 4 stmatrites With the Size n2 x n on on Aw Aii5ii Ba Cm G in l Bin Bu The above 7rmultiplitatiun 1a additions an be used bee but they ee n2m2 mew multiplication and additions now How to calculate the n2m2 mew multiplitaiun7 Erwin1 Smp condition Were the matrix Size is m Recurrence miemeieney analysis based on x muitipiieetiun m 7Tn2fnrngtl 1 nmznnna l5 I Solve the Recurrence Solving it by backward subsumuon for amed r2 7r2 7ir2 4 me meiebie m Count the 3 of addlDOl iS Tn7TnZ18nZ1fnrn gt110 n 2 r n e so which is the same as the complexity based on mulupllcatlon nmim il Many ImprovemenB Along This Line For example Coopersmith and Winograd r12376 Getting closer to the theoretic lower bound n2 nmznnna n ClosestPair Problem by Divide an Conquer Step 1 DNidE the pDinE givm into two subsets 5 and 5Z by a vetieei d iine x so that halft e puine iie m the le or on the line an bainbe puine iie m the right or on the line nmimn ix Closest Pair by Divideand Conquer cont Step 2 and recursively the closest pairs for the le am right subsee Step 3 Few minldn 2 We can hm our attention m the ewe in the symmm Vaticalsm emum Ziaspussi leclusestgair LetC em cZ be e subsee Dreams in the le su set 5 and of the nng stset 5 respectively that lie in m velical sm e paints in c em cZ ee snared in meesmg or eruftheir yeee mates which is maintained by merging during the execution We next step Step 4 For every paint P w in CV We inspa pDinE in cZ that may be ese m Pthaw e There an be me more than 5 em pDinE becwse e dz nzmnna Closest Pair by Divideand I Conquer Worst Case The worst case scenario is depicted below yl nzmnna l Efficiency of ClosestPair Algorithm Running time of the algorithm is described by Tr1 2Tr12 Mn where Mr1 e 0r1 By the Master Theorem wiih a 2 b 2 d 1 n e 0 nlog n nzmnna CSCE 350 Data Structures and Algorithms ChinTser Huang huangct csescedu University of South Carolina 5H Announcement Reading assignment Chapter 32 Homework 2 due on Monday February 9 in class Have your answers neatly typed Explain your answer clearly and adequately by showing the steps Midterm Exam 1 will be held on Friday February 13 u2D42m9 I Computing Fibonacci numbers De nitionbased recursive algorithm exponential Nonrecursive de nitionbased algorithm linear Explicit formula algorithm Logarithmic algorithm based on formula for nzl assuming an efficienlway of computing mam powers u2n42uw Another Example Construct an algorithm for computing a where agt0 is a constant and the integer 1120 is the input size Then analyze its time ef ciency Basic operation a multiplication of two numbers Two c oices Nonrecursive algorithm Recursive algorithm Any idea to make it faster eg with a better time ef ciency Bonus Can we solve this problem in 003quot time u2D42m9 g What s next From now on we are going to learn some basic and general strategies in designing algorithms to solve some typical computing problems We will analyze the ef ciency of these algorithms using the tools learned in the past several classes We will learn how to design algorithms with better efficiency u2n42uw Chapter 3 Brute Force I Brute Force A straightforward approach usually based directly on e problem39s statement and definitions of the concepls involved Examples Cornpdung 575 gt o nis a nonnegauye integer z Cornpuung r1 2 Nuluplying two matrices Sequenually searoning for a key of a giyen value in a list mm 7 BruteForce Strengths and Weaknesses Strengths wide applicability sirnplio yields reasonable algoridnrns searcning string rriatcning Weaknesses rarely yelds emoent algoridnrns sorne brutenforce algoridnrns are unacce not as constructive as so mamas for some important proplerrs e g mamx multlpllcauol l sorung me odner design techl39llques ptaply slow BruteForce Sorting Algorithms Selection Sort Seec Sar Scan the array to nd lts smallest element and swap it witn the rst elernent Then starung witn e second elernens Generally on pass o s is n72 nd dne srnallest element in Alma and swap it widn Am MD S S ADJ l Ai iAmWi ill71 in thelv rinel Dasltlans mamas I Selection Sort Example Sortlng 89 45 68 90 29 34 17 lee 45 65 an 29 34 17 l7 29 34 l 90 SE 59 l7 29 34 A la 9 l7 29 34 45 as l an i7 29 4 59 l 90 nzmmns SI Analysis of Selection Sort i ii ii iii iiiii i ii iiiiii iiii iisiiiitii ii 39 me emoency Space emoency stabi li ty Number ofkey swaps mam BruteForce Sorting Algorithms I Bubble Sort Bub 5m Compare adiacent elernens of dne list and d Is nange in lfthey are out of or er The rst pass le pos non e ernent unul a n a fter n71 passes dne list is sorted Generally pass o s is n72 can be represented as follows AWL AUlt gtA1 Am1 l Ami s in meirn mamas lt AMI nel Dasltlans I Bubble Sort Example I AnaIySIs of Bubble Sort First two passes of sorting 89 45 68 90 29 34 17 Amomm mm m n sq L 5 7 93 an 29 u n x tn LWWMW 45 as a as an 24 u H mm n w H WWWMMM p 45 ca 59 an u M 7 Wm my 5 53 as 29 an A 34 n ruwr 1 45 as is 25 A an L n a Cm H 5 ea 39 29 34 7 t w w u mm 4 3 A as L 9 2 29 u n an mmeemoem m2 2 if H E9 7 z 9 Space emcech ca 29 4 n 35 m Stabmtv Number of key swaps mamas x3 mamas m CSCE 35 S Data Structures and Algorithms ChinTser Huang University of South Carolina I Announcement Reading assignment Chapter 23 Homework 1 due on Friday January 30 39 class mamas g Amortized Efficiency Apply to a secpence of operations performed on the same data structure instead 0 to a single run in some cases a singie operaaon mav be expensive but the total me for an enure sequence of n operaaons is signi candv better than n Worst case ef ciency of that singie rauon Similar to businesses amoruzing an expensive item ver is producuve lifeu rne mamas I Summary of Analysis Framework botn tame and space ef ciencies are measured as funcu oris of 7 yr 525 n me errciencv is measured bv Lou7mg Number 0 ames the agonthm s biast a EUm 5 executed space ef ciency is measdred bv mth mbeo extra memoV units Lonimedby agonthm Ef ciencies of some aigoritnms mav dirrer signi candy for different inpuB ofsame size Primary interest iies in tbe Wefthe algoridnrn s running urneexua rnernorv ui iiB consumed as is input size goes to in nity mamas g1 Asymptotic order of growth A way of comparing functions that ignores constant factors and small input sizes no faster than O97 classoffuncuoris 7 that grow 7 97 ciassortuncaonsinmatgrowm as 7 mam ciass of runcaons 7 that grow W as gin mamas wesMi nuune 21 Biqohnmauon iiiiiauwimi mamas gt Big omega 39h noun 2 2 av amegs notation mm s DM WH mmns 1 Big theta nnunszs Bigthmaimumn meow mksmus x Establishing order of growth using I the def n Definition 1 is in 0gr1 if order of growth of n 5 order of growth of 9a within constant multiple ie there exist positive constant and non negative integer l h such that H S 5901 for every r1 2 I Some properties of asymptotic order of growth ll 6 0007 n e Ogn iff 9n sOn If n e 0gr1 and 9n e Ol7n then H e 0 1 Note similarity with a S b Examples If 607 e 091n and 607 e 092n I then 10m CW 601 601 e 0maxigin 9201 S720 lS om mm 9 mm m Establishing order of growth using 5 ts l L39H al39s rule and Stirling39s formula 0 ardexafgmwthaflmlindexm39gmwthafg il iimn My ggt0 smsxsrgmmwm inmamfgmthufg il m ordain3mm m rm inmamfgmth vizgm Examples mm vs 2 2 normz vs a lug n vs law bgtcgtl mmns n L H pital39s rule wva m mwgm m and the derivatives g exist then Iim Kquot Iim n 9039 n Example isan vs nw Stirling39s formula m s 2mm 7e Example nlvs 2quot mksmus lZ Today s Agenda the Last Class Final Exam Various administrative issues on the final exam Review for the semester and the final exam Time Wednesday May 6 9 00 am 1130am Place This room ote closedrbook and closedrnote coverage all matena discussed W the class around 20 of points for the material before the second midterm exam Additional Office Hours m4 2pm Monday May 4 Review For the Final Exam Some Important Points An algorithm is a sequence ofunambiguous instructions for solving a problem ie forobtaining a required output for any legitimate input in afinite amount oftime problem algorithm Each step of an algorithm is unambiguous The range of inputs has to be specified carefully The same algorithm can be represented in different ways The same problem may be solved by different algorithms Different algorithms may take different time to solve the same problem we may preferone to the other Some Wellknown Computational Problems Algorithm Design Strategies Sorting Searching Shortest paths in a graph Minimum spanning tree Primality testing Traveling salesman problem Knapsack problem Chess Towers of Hanoi Brute force Divide and conquer Decrease and conquer Transform and conquer Greedy approach Dynamic programming Space and time tradeoffs Analysis of Algorithms How good is the algorithm Correctness Time efficiency Space efficiency Does there exist a better algorithm Lower bounds Optimality Data Structu res Array linked list stack queue priority queue heap tree ndirecteddirected graph set Binary Tree and Binary Search Tree Binary tree each vertex has no more than two children Binary search tree the number associated with the parent is largerthan its children The height ofa binary tree from the root to the leaf is Llogznjg hg n71 We use this laterin informationtheoretic lower bound estimation Theoretical Analysis of Time Efficiency Time ef ciency is analyzed by determining the number of repetitions ofthe basic ogeration as afunction of ingut size Basic ogeration the operation that contributes most towards the running time ofthe algorithm in ut size Tn zjagcln mmmgume execuucmume Numberottimes forbale operation ham operahm is e ecute Bestcase Averagecase Worstcase For some algorithms ef ciency depends on type of input Worst case Wn maximum over inputs of size n Best case Bn minimum overinputs ofsize n Average case An average over inputs of size n Number of times the basic operation will be executed on typical inpu NOT the average of worst and best case Expected numberof basic operations repetitions considered as a random yanable undersome assumption about the probability distribution ofaH possible inputs ofslze n Order of growth Most important Order of growth within a constant multiple as quot4900 Asymptotic Growth Rate A way of comparing functions that ignores constant factors and small input sizes Ogn class of functions fnthat grow no famethan gn 9 gm class of iunctions fnthat grow alsame rate as gn Qgn class offunctlons rm that grow at least as fast as GM ing rate of growth using Ii ii urderufngLhufTKiurderufngLhufgn um roman on under ufngLh aim inrder ufngLh ufgoi an under ufngLh aim inrda ufngLh ufgu L Hopital s Rule lmn hm f39n wee gm wee gm Basic Asymptotic Efficiency Classes Analyze the Time Efficiency of An Algorithm Nonrecursive Algorithm ALGORITHM Fammlm fe1 forl enon do Recursive Algorithm ALGORITHM Factorl o1 n mum Factorialn e 1 n Time effi iency of Nonrecursive Algorithms Steps in mathematical analysis of nonrecursive algorithms Decide on parametern indicating ingul size identify algorithms basic agealto Determine Worst average and besiease forlnput ofSlZe I7 Setup summation for em reflecting algonthm s loop structure Simplify summation using standard formulas see Appenle A Useful Formulas in Appendix A Make sure to be familiarwith them 26 42 ii ii 20 02 217 ii ii ii Zlil2nm 72 2 Prove by Induction W Time Efficiency of Recursive Algorithms Steps in mathematical analysis of recursive algorithms Decide on parameter n indicating ingut size Identify algorithm s basic ogeration Determine Worst average and best case for input of size n numberoftimes the basic operationwill be executed r input of size n alternatively count recursive cal s Set u a recurrence relation and initial conditions for Cn the oran Solve the recurrence to obta n a c osed form orestimate the order of magnitude of the solution seeAppendix B lmporta nt Recurrence Types One constant operation reduces problem size by one TnTrHc Tid Suiutlun Tm m a linear 3 A pass through input reduces problem size by one TnTrHcn M d Sulutlun Tm nnly2 7110 d guadratlc One constant operation reduces problem size by half Tm nnz 0 m a Sulutiun Tm 0 lg n a logarithmic A pass through input reduces problem size by half Tm 2Tn2 cn m d Sulutiun Tm migan nlugn Design Strategy 1 BruteForce closest palrand convex hull exhaustive search knapsack and assignment problem Bubble sort sequential search bruteforce string matching forTSP 89445 68 90 29 34 4 89 968 90 29 34 45 68 89990 a 29 34 45 68 89 29 90 34 45 68 89 29 34 90 17 45 68 89 29 34 17 I 90 v HHHH Ill Design Strategy 2 ide and Conquer Mergesort Recurrence Cn2c nlz Cmergen for ngt1 25 Easic operati n is a comparison and we have Cmergenn1 Using the Master Theorem the complexity ormergesort algorithm is en log n it is more emcientthan SelectionSort EubbleSort and lnsertionSort wherethe time complexity is law wasan Guicksort Basic ogeration key comparison Best case split in the middle n log n Worst case sorted array o n2 Average case random arrays e n log n AD SP Az 2 p Binary Search TnTn21 for ngt1 r11 gtTn ouogn Search for K70 mdzx 01 2 3 4 5 6 7 8 9 1011 12 Value 3 14 27 31 39 42 55 70 74 81 85 93 98 1 m r Itzr1 nch 1 m r 122m lm r Other Dividea ndConquer Applications Binarytree traversal Large integermultiplication Strassen s Matrix Multiplication Closest pairthrough divide and conquer quickhull Design Strategy 3 Decrease and Conquer Insertion Sort This is atypical decreasebyone technique Assume A0i1has been sorted how to achieve the sorted A0i Solution insert the last elementAU to the right position AMEmg A1ltA15 7A smallerihanurequaliu Am gaierihan Am Algorithm complexity Twyw 608 760005 ri DFS Traversal DFS Forest and Stack c His 7 Shell pullllpop Topological Sorting Problem find a total order consistent with a partial order DFSrbased alglrilhm DFS traversal note the order with w ich evemcesarepopped off stackltdea en gt Reverse order solves topological sorting Back edges encountered7gtNOT a DAGi er 1 so Note problem is solvable iff graph is dag Design Strategy 4 Transformand Conquer Solve problem by transforming into a more convenient instance ofthe same problem simplification somn Gaussian elimination a different representation ofthe same instance regresentation change balanced search trees heaps and heapsort polynomial evaluation by Homer s rule Fast Fourier Transform a different problem altogether problem reduction reductions to graph problems linearprogrammin Balanced Trees AVL trees Maintain the Balance of An AVL Tree Forevery node difference in height between left and right subtree is atmost1 An AVI tn Nat an AVI In The numbershown above the node is its balance factor the difference between the heights ofthe node s left and right subtrees Insert a new node to a AVL binary search tree may make it unbalanced The new node is always inserted as a leaf We transform it into a balanced one by rotation operations rotation in an AVL tree is a local transformation of its subtree rooted at a node whose alance factor has become either 2 or 2 because ofthe insertion ofa new node If there are several such nodes we rotate the tree rooted at the unbalanced node that is closest to the newly inserted leaf There are fourtypes of rotations and two of them are mirror images of the other two Heap and Hea psort Heap Implementation A heap is a binary tree with the following conditions 1 it is essentially complete all its levels are full except possibly the last level where only some rightmost leaves may be missing 2 The key at each node is 2 keys at its children A heap can be implemented as an array H1n by recording Its elements in the topdown lefttorl39ght fashion Leave H0empty First yr2i elements are parental node keys and the last lnzl elements are leaf keys ith element s children are located in positions Ziand 2i1 0123456 Heap Construction Bottomup Approach Heap Construction Topdown Approach Town 55017 E20172 2w log2ltn1gtgt sew insert a new key 10 into the heap with 6 keys 9 6 a 2 5 7 0 0 9 0 00 00 0 00060000 0000 Zlogl e nlogn ei Heapsort Two stage algorithm to sort a list ofn keys First heap construction 0n c sequential root deletion the largest is deleted first and the second largest one is deleted second etc 7H Cn s ZZlogzl e 0nlogn i1 Therefore the time efficiency of heapsort is 0nlogn in the worst case which is the same as mergesort Note Average case efficiency is also 0nlogn Design Strategy 5 SpaceTime Tradeoffs Formany problems some extra space really pays off extra space in tables breathing room hashin non compansonrbased sorting input enhancement indexing schemes eg Entrees auxiliary tables shift tables for pattern matching tables ofinfonnation that do all the work dynamic programming Horspool s Algoritll Ill lhepattern39slengthm f c isnot amongthe rst m a 1 characters of the pattern 25 the distance from the rightmost c amongthe first m a 1 characters of the p attern to its last character otherwise Shift Table for the pattern BARBER Example See Section 72 forthe pseudocode ofthe shifttable o struction algorithm and Horspool s algorithm Example find the pattern BARBERfrom the following text JIM SAW ME IN A BARBERsHo BARBER BARBER BARBER BARBER BARBER BARBER Open Hashing Store student record into 10 bucket using hashing function nssss mod 10 xxxxx6453 xxxxx2038 xxx xxosla ml 2m xxxxx4382 quotm 2ng xxxxxSOBA xxxxx2498 Closed Hashing Linear Probing XXXXX6453 XXXXXZOSB XXXXX0913 XXXXX4382 XXXXXSOBA XXXXXZASB Design Strategy 6 Dynamic Programming Dynamic Programming is a general algorithm design technique invented by American mathematician Richard Bellman in the 1950s to solve optimization problems Programming here means planning Main idea solve severalsmalleroverlappingsupproolems record solutions in a table so that each supproolem is only solved once inai State ofthe tabie WlH be or contain Soiutlol l Walsh quot393 Algorithm Tnnsltlvo Closur Computes the transitive closure of a relation Alternatively all paths in a directed graph Example of transitive closure Hush 395 Algorithm In the 1611 stage determine if a path exists between two vertices i jusing just vertices among 1 k Raquot1ijj path using just 1 k1 Rashx or Radik and Rik39l kjj path from ito k and ram k to i 91 using just 1 O 39 k h stage Floyd39s Algorlthm A Mil shortst plths In a weighted graph find shortest paths between every pair of vertices Same idea construct solution th of matrices DM D 1i usin n i of the vertices as intermedia ies ough series n ia bset 4 123 ac 10103 ac 2205 1 3770 0 45159 Ol O AB Similar to Warshall s Algorithm 015 in d is equal to the length ofshortest path among all paths from the ith vertex to jth vertex with each intermediate ertex if any numbered not higherthan a n d5 mindkquotdf diff fork 21px WV Design Strategy 7 Greedy algorithms uuon through nn ach step the ch Fealee Satlsfytne plublem s ccin localy optimal the nest chciice lnevoceole once made it cannet be changed later Optimal solutions change maxin Minimum Spanning Tree MST Singlersuurce shertest paths sim lescheuuling prublems Approximations Traveling Salesman Plublem TSP K a sacx plublem etherccimhinatcirial cipnmizaticin plublems Prim s MST algorithm Start with tree consisting of one vertex grow tree one vertexedge at atime to produce MST Construct a Series ofexpanding Subtrees T1 T2 Tio1 from TI I I I 1 connecting a vertex in tree T to one not yet in tree c ringe edges this is the greedy stepi algorithm stops when all vertices are included Step 4 Add the minimumweight fringe edge fb4 into r Remaining vertices dr5 er2 Another Greedy algorithm for MST Kruskal Start with empty forest of trees grow MST one edge at atime intermediate stages usuaHy have forest oftrees not ted tea h stage add minimum weight edge among those not yet used that does not create a c e edges are H Hiiaiiy sorted at each st go the edge rn rexpand an existingtre lt 2 byincreasirig weight ax e rcombine two existing trees into a singie tree rcreate a new tre need efficientway of detectingavoiding cycies algorithm stops when all vertices are included Step 5 add the next edge without getting a cycle SingleSource Shortest Path Algorith In jkstra s Simiiarto Prim s MST aigonthm with the following difference Start with tree consisting of one vertex grow tree one vertexedge at a time to produce spanning tree stiuct a series of expanding subtreesTi Tzi Keep tracx oishortest path from source to each oithe vemces in T at each stage construct TM from T addmaneemeighteege connecting a vertex in tree Tgto one not yet in tree echoose from fringe edges thiS is the greedy stepi edge MW h lowesmuv MW aigorithm stops when an vemces are inciuded Step 3 Tree vertices a0 ba3 dbi5 Remaining vertices cb34 e W9ed54 Huffman Coding Algorithm step 1 lnitialize n one node trees and label them with the characters ofthe alphabet Record the frequency ofeach character in its tree s root to indicate the tree s weight step 2 Repeat the following operation until a single tree is obtained nd two trees with the smallest weights Make them the left and right subtrees of a new tree and record the um of theirweights in the root ofthe new tree as its weight Example alphabet A B c D with frequency P NP and NPComplete Problems A l a l c l D l probabilityl 035 01 l 02 l 02 l 015 As we discussed problems that can be solved in polynomial time are usually called tractable and the problems that cannot be solved in polynomial time are called intractable is there a polynomial time algorithm that solves the problem 7 5 the class of decision problems that are solvable in Opn where pn is a polynomial on n M the class ofdecision problems that are solvable in polynomial time on a nondetenninistic mach39ne A decision problem D is NP complete NFC iff 7 D a NP 2 every problem H l NP l5 polynomlaHlme reducible to D Thank you Good luck in yourfinal exam CSCE 350 5 Data Structures and Algorithms ChinTser Huang W University of South Carolina I About Me ChinTser Huang PhD in Computer Sciences University of Texas at Austin Research in network security network protocol design and verification distributed systems My web page can be found at hm Mww cse sc eduhuangct nllZInni z About What Students Think of Me nllZInni z l About the Course An undergraduate course focusing on the fundamentals of data structures and Data structure schemes for information representat on and processing Techniques for algorithm design Application ofthese techniques on various types of roblems Analysis of algorithms nllZInni o qt About the Course We will cover the fundamental knowledge you SHOULD know We will also try to nd out what you WANT to learn So we expect there will be abundant interaction between you an nllZInni s Course Information Online httpwwwcsescedulhuangcthSCE 35009lindexhtm Syllabus class schedule of ce hours Links to handouts and other useful links are available on the page Lecture slids will be available online nllZInni s g Your Best Strategy Come to every lecture and take notes in class Keep yourself exposed to interestin computational problems and appreciate their lgorithmic solutions Finish each assigned reading and participate th iscussion Do not wait till last minute to work on assignments or prepare for exam Enjoy the fun Chapter 1 Introduction nlte amount of u rne mm 7 I Algo hm 1 H sto al Perspective Anmmmls sequence oful lamblguousll lstructlol ls fo yng a problern l e for o li lli lg a requlred output for any leglurnate lnput ln a Euclid39s alg 39thm for nding the greatest common divisor 339d century C bl Muhammad ibn Musa alKhwarizmi 9 quot Pquot quot39 century mathematician quot I Book Ual lslated ll lto Latin 90mm Algorltrn de nurnero urn mlmm a mlmm m SI Why study algorithms Theoretical im portance the core of computer science Practical importance A practitioner39s toolkit of known algorithms Framework for designing and analyzing algorithms for new problems mlmnna Some Important Points About Algo 39thms Each step ofal39l algorlthm lsul l rrblguous The range of lnpue has to be speclfed carefully The same algorlthm can be represented li l dlfferel39lt ways The same problem may be solved by dlfferel39lt algorlthms leferel39lt algorlthms may take dlfferel39lt ume to solve the same problem e we may prefer one to the other mlmnna 5 Example Euclid s Algorithm Problem Find gcdmn the greatest common divisor of two nonnegative not both zero integers m and n Examples gcd6024 12 gcd600 60 gcd00 m122uw 13 5 Example Euclid s Algorithm Euclid39s algorithm is based on repmted application of uality cdInn gcdn In mod n until the second number becoms 0 which makes the problem tIiVIa Example gcd5024 gcd2412 gcd120 12 How do you know this algorithm will eventually stop mlZmug 14 1 Two descriptions of Euclid s algorithm Step 1 Ifn 0 return Inand stop otherwise go to Step 2 Step 2 Divide In by n and assign the value fo the remainder to I Step 3 Assign the value of n to In and the value ofrto n m122uw 15 H Two descriptions of Euclid s algorithm ALGORITHM Euclidmn while It 0 remmodn men ner remm m In th39s course you usually wrim the algorithm in pseudocode instead of the real code in some specific language mlZmug 15 Other methods for computing gcdmn Consecutive integer checking algorithm Step 1 Assign the value ofminInn to 139 Step 2 Divide In by t Ifthe remainder is 0 go to Step otherwise go te 4 Step 3 Divide n by t Ifthe remainder is 0 return tand stop otherwise go to Step 4 Step 4 Decrease tby 1 and go to Step 2 What is the range of input for this algorithm Can one of m to e Zero No both In and n must be positive for this algorithm m122uw 17 Other methods for computing gcdmn cont Middleschool procedure Step 1 Find the prime factorization of In Step 2 Find the prime factorization of n Step 3 Find all the common prime factors Step 4 Compute the product of all the common prime factors and return it as gcdmn Is this a legitimate algorithm No steps 1 and 2 are not defined unambiguously mlZmug m CSCE 3 50 5 Data Structures and Algorithms ChinTser Huang nuangct cse sc edu University or South Carolina Announcement Reading assignment Chapter 33 Homework 2 due on Monday February 9 in c ass Midterm Exam study guide is posted on class websi e HW score has been updated at CSE dropbox httgs d rogboxcsesced u nznmnna I Bonus Question Can We solve me problem or corrpuung a in oaoga ume7 ALGORITHM lnlfxpn irn 0 return 1 else irn mod 2 0 return lnlfxpn2Z else return lnlfxpn712Z x a I Brute Force Sequential Search Problem nd a search key in a given list e ii hi ALGDWYNM iiiiiiiiiiiiiiiiiiiiiii iiii i it siiii mmiii iiiiintaiiiiiiiistaaitiiiiiismiaii it iiii iinin iiiiiiiiii llii iiii iiiiiaii an A i a mi iit i ii iiiaa i iiai nii i iii iii ii n ma ruiim Ef ciency nznmnna nznmnna I Brut Force Sequential Search An enhancement to remove the check on is value atcunimm iiiiiiiiiii iii iiiiiii ii iiiiiii iiiiai iii aii iiii iii ii iiiaiui ttii aiiiiiii vi iiiiiiagiiiM i a iiiiii i l iiiti iiviiii iiia iiiaiiiaisiiiaaii m 6 Na need to heck iltn in every izeieziani ii iiiquot Ef ciency nznmnna I Brut Force String Matching Hobie ind a subsh39ing in the Mmat matches the Emern garter7 a saing or mcnaracters to seaicn rOi text a longer saing or ncnaracters to seaicn in Brute orce al oridnm Step 1 Align pattern at beginning uftext 31 2 Moving rain lz to right ampere eean aneeacei arpemein to me corresponding Enaadar in text until all Ena39adars are reang to math successful seamn Dr 5 inisinecan is detected 31 3 wniie pattern is not reang and me text is not yet exnwsted realign pattern me stitiDn to me right and repeat Step 2 Examples of BruteForce String I Matchlng onvorlcsnu1m Typical applications nd39 function in MS Word Google search azraspaaa I Pseudocode and EffICIency ALGDWYHM unit rmt tmaarramt tnaa taro amrt analrma lt lrlltl39 llllr ll ma lll llmrr tlnr artrsrtmasemma r inland r rm wrunnmarma marten arntarma t rraa ns tarnrrmam eltlttt tartlrotm ml ttrlltt ltlluli lll ll rlaa l 4 ermtltrm Ef clency worst case7 average case7 We wlll see more et oentalgonanms tor ants proplem nznslmna I Closes air Problem nno the two closest porne n a set or nporne in the twondlmenslonal Carteslan plane campate the olstante between every palr atolstlntt pants and 72mm the lnoexes attne pane tar wnltn tne olstante is the smallest azraspaaa Brut Force ClosestPair Algorithm AlG ilVNM Irllnlnlu tnmlwulrll t mmlsll urw l tar mama tattleMarat and ma Inl lhctlmui my mamar mrraex Ml Ii on tar lt arnrln a t r n e arrl umItihgnlmllmailulltntlll weamm e a man et quotat er aramrrraatrnrrrata Efflclency Carl We make it faster7 azraslmaa m Convex Hull We won39t cover it here but the book studis a bruteforce algorithm for computing convex hulls azraspaaa I Exhaus Ive Search A brutenforce approach to complnatonal problem cenerate eatn and men element attne problem s dnmaln Then tampare and selett tne deslrile element that satls es tne aet tanstralne involve tamplnatanal aplete satn permuzamns tammamna and subsetsata glvm aet The tlme enltlenty lsusuallv bed eaaaally the Dmplexlty graws WWW the lnput SiZE Three examples Traellng salesman praplem Knapsatk prap em Assgnment prapem azraslmaa lZ ChinTser Huang MW Unlverslty of South Carollna CSCE 350 S Data Structures and Algorithms SI Announcement Reading assignment Chapter 43 44 Homework 3 is assigned on February 16 and is due on Wednesday February 25 in class Please download it from class website Have your answers neatly typed Explain your answer clearly and adequately by showing the steps nZlxlmni z 5 Quicksort Selecta amnparuuonrlg element Rearrange the llstso matall the elements W m before me plvot e posluorrs are smaller than or equal to me plvot and l Pseudocode of Quicksort ALGORITHM ummlrrll mm w ill rllll llll ll ll uulluulnmlm lllurlelu mum mose alter me plvotare larger than or equal to me plvot 4 I Exmarge the plvot Wll the last elementll l the rst l e llu ulnnlu ll llmlmi lll unudumullvt UlllAl subllst ri e plvotls new li l lB nal poemon if Alx 51 AI 2 p g Pseudocode of Partition magnum urrmrrlu lll l l ulmulmrr wunarlx m lmni lkllrlclrliulil x rm lulu mull li llar lllllrli utr lhhli rmlmll lllu lll ill lwlmlN mm l uulllurlr lrllmlll illlw lumll lrlr l llll l l lulululul Mmequot ml 9 Illustration of Partition a 1 1 1 e e s 1 W e an nZlxlmni 2111 Example Sort53198247 uzmzmg Example uzmzmg A Fancier Example Source Wikipedia uzmzmg 9 Efficiency of Quicksort Basic ogaton key comparison Bestcase39 split in the middle n log n Wolstcase sorted array 012 Aveage case random arrays n log n Improvements better pivot selection median of three partitioning voids worst case in sorted Ies switch to insertion sort on small sub les elimination of recursion these combine to 2025 improvement o21E2m9 l Binary Search Brute Force sequential search n Binary Search searching in a sorted array Basic idea Compare a search key Kwith the array39s middle element Am If they match the algorithm stops Otherwise repeat the same operation recursively for the first half of the array if Klt4m and for the second half if Kgt4m K I A0 Am 1 Am Am1 An 1 5 search here if e ch here if KltAm mam o21E2m9 11 Pseudocode of BinarySearch ALGORITHM 1 mm im 7 iii A ilmpimmni nmnwuym mm e ilnpui n1rr xiv llwmdimmcnmngmuemnu 1 warehh K sUInpuL n uhlu inf ilk tild39 t clamit llm germ n a m m lam minnewnmm i A lmlnmnm L lel v will 7 m ulw m 1 relum 7i uzmzmg I Example Search for 70 mdzx 0 1 2 3 4 5 6 7 8 9 10 11 12 Value 3 14 27 31 39 42 55 70 74 81 85 93 98 m r 1 m r in y Elmamm Time Ef ciency In the worst case no key KexisE in this array isi nonrecursive algorithm we can Although d1 s an see that the time ef ciency can be analyzed using the recurrence relation Using backwad subsu39 on Exact solution TOT L105 nj1 logzui 1 l Binary search is in fact not a typical example of divide and conquer ause it does not solve two subproblems Elma2mg CSCE 350 5 Data Structures and Algorithms Chin ser Huang huangcthse sc edu Unlyerslty ot Soutn Carollna I Announcement Reading assignment chapter 113 Homework 7 is returned and discussed today Homework 8 is assigned on April 17 and is due on Wednesday April 22 in class Have your answers nea y ped Explaln your answer clearly and adequately by Showlng the Steps Stud guide for nal exam has been dish39i uted in last Friday39s class mamas Methods of Obtaining Lower Bound Trivial lower bounds Informationtheoretic arguments Problem reduction mamas Lower Bounds by Problem I Reduction Idea prroblem Plsatleast as bad as problem a then a lower bound for le also a lower bound for p Hence nd problem owr a Known lower bound tnat can be reduced to problem Pln dues on nus m norms rm rm arrow rw v on letlba err mum 1 n dc rdrrrem readrun mltrgnr m dawn nurture rrrrrrrsw orquot burn mullxrlnanmi ul n iwl mm orrrr urtruwrr nrdrdnusrm u more balms arrr39r drum mamas Lower Bounds by Problem I Reduction Example Euclldean MST problem leen a set of HpolnE rn the plane construct a tree wrtn mrnrmum total lengtn tnat conn consrdered as problem a To get a lower bound for tnrs problem reduce the dement ecE tne gryen pornts Uriwavess pmbem to rt consrdered as problem 0 Ifan algorrtnm faster tnan n log newse for Euclldean MST lherl one must take 0Hlog n om Mum exlsE for element unroueness a so Ana contradrctronl Therefore any algorrtnm for Euclldean MST e l A s I Classrfylng Problem Complexity As we drscussed problems that can be solyed rn polynomral trme are usually called tractable otnerwrse are called lniIactable now the duesoon to ask rs Is Ma39s gamma r same agorrrnm marsdyes 0 75 pf Posslble answers yes no betouse rt ton be broyed trot all aleorrtnrrrs Lake ewbonentrol nrrre betg use rt ton be broyed trot no aleorrtnrrr eyrsts at all to solve trrrs errr don tknow don t know but rrsutn aloorrtnrn were to be round dren rt would proyrde a means o solyrng marry otne problerrs rn polynomlal trrne madam I Types of Problems Op 39mza on probem construct a solution that maximizes or minimizes some objective function Decision probem answer ysno to a question Many problems will have decision and optimization versions Eg Traveling Salesman Problem uph39rm39zab39an nd Hamiltonian cycle of minimum weight ecisv39an Is there a Hamiltonian cycle of weight lt k ownmm Some More Problems P DUO7 Given nposiuve integers determine whether it is possble to partition them into two dlSJOll it subseB with the same sum Em geekg given Hitems whose sizes are positive rauonal numbers not iarger than 1 put them into the smaiiest number of pins of sze 1 Gig7 camm For a given graph ind its chromatc number i e the smaiiest number of coiors that need to be assigned to the graphs veuces so that no two adjacent veruces are assigned the same color CAfsaUs abNQ Given a booleari expre iori in conjunctive normai torm coniuncton otdisiunctons or literals is there a truth assignment to the variables that makes the expression true7 m2n2uug 5H Announcement CSCE 350 Reading assignment Chapter 31 Data Structures and Algorithms Homework 1 graded Homework 2 Problems 218 219 222 225 227bc 234 ChinTser Huang 241bcd 244 huangct csescedu Account for 4 points inward nal grade Due on Monday Februaly 9 in class Midterm Egtltam 1wi be held on Friday February 13 uzDZIIDQ 2 University of South Carolina 1 Fibonacci numbers Solving Fibonacci recurrence The Fibonacci numbers The Fibonacci recurrence cannot be solved with 0 1 1 2 3 5 8 13 21 backward substitution The Fibonacci recurrence Instad we will solve it with a theorem for solving F F 1 F Z homogeneous 2 quot order linear recurrence W r Fm 0 constantcoe clens i1 aXn bXn1 own2 0 This sequence comes up in many unexpecmd places run time of Euclid s algoriihm nature branching in irees spiral of shells leaflee of pineapples reproduciion in bees art via me golden ratio popular culture The DaVinci Code D2EIZ2EIEB 3 UZDZIIEIQ 4 g Sol 39 g aXnbXn 1On 2 o Solving Fibonacci recurrence Refer to Appendix B Theorem 1 FM l FUz or FU FUH FM Z 0 Set up the Charade7ch equao39on quadratic l Characteristic equation a roots Solve to obtain roots r1 and r2 General solution to the recurrence ifrland rzare distinct real roots Xn clrl Brz 39 we have Fm ifr1r2 r Xn chBnr Particular solution can be found by using initial l Using F00 and F11 9 COHdItlonS a1 5 and 3 7143 u2n22uw 5 u2n22un9 a CSCE 350 Data Structures and Algorithms ChinTser Huang huangct csescedu University of South Carolina Announcement Reading assignment Chapter 113 Homework 8 is due today Study guide for final exam has been distributed in last Friday s class m222EIEI9 l Types of Fjroblems Op 39mza on probem construct a solution that maximizes or minimizes some objective function Decision probem answer ysno to a question Many problems have decision and optimization versions Eg Traveling Salesman Prob em uph39rrlizab39an nd Hamiltonian cycle of minimum weight ecisv39an Is there a Hamiltonian cycle of weight lt k D4222EIEB Some More Problems paragon Given nposiuve integers determine whether it is possble to par tioi l them into two dlSJOll it subseB with the same sum Em geek given nitems whose sizes are positive ratonal numbers not larger than 1 put them into the smallest number of bins of sze 1 Gig7 cobm For a given graph ind its chromatc number i e the smallest number or colors that need to be assigned to the graph39s vetoes so that no two adjacent veruces are assigned the same color CAFsaUs abhg Given a boolean expre lorl in eoniunetve normal rorm eoniunetton ordisiunettons or literals is there a truth assignment to the variables that makes the expression true7 m222EIEI9 The Class P B the class of decision problems that are solvable in Opn where pn is a polynomial on n Why polynomial if not very inef cient nice closure properties machine independent D422IIEB The Class IVP M the class ofdecision problems that are solvable in polynomial time on a nondetennns c machine A delarmmisb39ccompumr is what we know A nondetermmis ccomputer is one that can guess the right answer or solution Thus lVPcan also be thought of as the class of problems whose solutions can be verified 39n polynomial time or Note that lVPstands for Nondeterministic Polynomial timequot m222EIEI9 Example39 Conjunctive Normal Form CNF Satis ability This problem is in IVP Nondeterministic algorithm Guess truth assignment check assignment m see if it satis es CNF formula Example Boolean operation vb v5EvbEvb v5 Truth assignments a true b true c false gt the entire expression true Checking phase II u4222uw 7 Where Are We Now Exhibited nondeterministic polytime algorithm for CNF satis ability CNFsat is in IVP Similar algorithms can be found for TSP HC Partition etc proving that these problems are also in IVP All the problems in Pcan also be solved in this manner but no guessing is necessaiy so we have Big question P IVP 0422ng E P NP One of the most important unsolved problems is computer science is whether or not PVP If PIVP then a ridiculous number of problems currently believed to be very dif cult will turn out have ef cient algorithms If FatVP then those problems de nitely do not have polynomial time solutions Most computer scientists suspect that P I NP These suspicions are based partly on the idea of NPcompleteness u4222uw 9 NPComplete Problems A decision problem Dis VPcomplete if it39s as hard as any roblem in NP ie Dis in VP every problem in NPis polynomialtime reducible to D mama CooksLevin theorem 1971 1973 CNFssat is Nllcomplem 0422ng IVPComplete Problems cont Other VPcomplete problems can be obtained through polynomialtime reductions from a known VPcomplete problem My th Examples TSP knapsack partition graphcoloring and hundreds of other problems of combinatorial nature u4222uw n Polynomial Reductions A decision problem D1 is said to be polynomial reducible to a decision problem D2 if there exists a function that transforms instances of D1 to instances of D2 such that tmaps a yes instancs of D1 to ya instances of D2 and all no instances of D1 to no instances of tis computable by a polynomialtime algorithm Implication If D2 can be solved in polynomial time 9 D1 can be solved in polynomial time A 0422ng 12 gl Polynomial Reductions Example Polynomialtime reduction of HC to decision version of TSP TSP wi total distance no larger than k3 given integer distance 1 1 What does this prove HC is harder or easier than TSP decison7 HC is NPC 9 TSPD is NPC7 or TSPD is NPC 9 HC is NPC7 min2cm To Prove a Decision Problem is in C 1 Prove it is in lVPven39 cation takes polynomial time 2 Prove that all problen39s in lVPis reducible to this problem or 3 Prove that a known lVPCproblem is reducible to this problem fwe canprove any given NPC problem can be solved In polynomial time 9 PIVP mizzizms H Practical Implication of NP I completeness 5 173 5e 4 M i can39t ind an ei eentaigondnrn i guess i am too durrb quot mizzizum is Practical Implication of NP I completeness M lt ii i can t nd an ef cient aigoninrn because no such aigoninrn lS ossibie quot mizzizms 16 Practical Implication of NP l completeness Lib i can t nd an ef cimt aigoninrn but neither can all inese famous people quot mizzizum i7 CSCE 350 Data Structures and Algorithms ChinTser Huang huangct csescedu University of South Carolina 5H Announcement Homework 8 is returned and discussed today Highest 2 Average 179 All grades up to HW 8 have been updated at your dropbox Study guide for final exam has been distributed in last Friday s class m242uug Chapter 12 Coping with the 1 Limitations of Algorithm Power Tackling Difficult Combinatorial Problems There are two principal approaches to tackling NPhard problems or other intractable problems Use a strategy that guarantees solving the problem exactly but doesn t guarantee to find a solution in polynomial time Use an approximation algorithm that can nd an approximate suboptimal solution in polynomial time m242un9 4 Exact solutions The exact solution approach includes the strategies exhaus 39ve search brute force useful only for small instances backhackng eliminates some cases from consideration banclrand boun further cuts down on the search fast solutions for most instances worst case is still exponential tummm Backtracking Construct the state sgace ee nodes partial solutions edges choices in comple ng solutions Explore the state space tree using depth rst search DFS Prune nonpromising nodes DFS smps exploring ilbhee rooted at nodes leading m no solutions and backhacks to is parent node m242un9 5 Example The nQueen problem Place nqueens on an n by nchess board so that no two of them are on the same row column or diagonal i 2 3 A l l 47 queenl 2 lt queen 2 3 4 queen 3 A lt queen A nmmnna 7 mommu s Statespace of the fourqueens I problem Example Hamiltonian Circuit gi Problem nmmm I Branch and Bound An enhancement of backtracking Applicable to optimization problems Uses a ower bound for the value of the objective function for each node partial solution so as to guide the search through states ace rule out certain branches as unpromising39 mommus m Example The Assignment 1 Problem Select me element in mch rnw er the cast matrix C sn that mi twn selected elements zrein the Mme cnlumn and the sumismimmizesl Fur example Job 11152 Job 1154 new 9 z 7 a Fersunb a 4 3 7 Fersun s a l a F m1 7 a 9 4 Laws hmmrl Any Snllltinn tn this pmhlem will have tml cast erat least nmmnna Assignment problem lower l bounds luwel notquot heme ll lo lllc node mommus lZ I State space levels 0 1 2 new izj stsls Landzanhesxzm soaaenae rhonslarceolmemeslcnmrm Droh39nm We wiped W the hcu Illa bunch ana houn nlwolvlhm ammo I Complete state space omlmoa ma m la 39lvelllslaro rs anomaly ml y all mm rawhom an I Approximation Approach Apply a fast l e a polwomlalcume approx maoon algononm to geta solunon mans notl39leoessarlly opomal but nopemllyclose to it Aocuracy measures of arr approximate solunon 5 15 K5 w ror mlnlmlzaoon problems 5 e w K5 ror maximlzauol39l proplems Wnere Ks and 5 are yalues orone objective iul39lcuol39lf ror one approximate solunon gano acmal opomal soluoon 5 b a c raw or me algononm A Waste lowest LDDer bound of s on all ll lstal lces 5 ylsmng all the A xi AeBeceDernengmm D1 C Nata Nearest39rlelghbor tour may depmd Accuracy R DU unoounoeo ewe e make the lengnn DfAD aoloanly large n the aooye Example omlmoa l NearestNeighbor Algorithm for TSP Siamng at some Elly always go to the neaesi unylslceo City and a ar one cmes 72mm to the smrng o 3 3 z a AeBeDeCernenguax on the sramng Elly TwiceAroundtheTree Algorithm Stage 1 eonsoucr a mlnlmum wannlng oee uflhe grapn e g by an39s or Kmskal s algonnnm Stage 2 S artlng at an aroloary vertex create a path that goes omce around 12022 and remms co the same vertex Stage 3 ereace a tour from the crculr consoucceo ln Exage 2 by maklrlg enorrcuo co ayolo ylsmng lncermeolace VErtlEES more than once Nata RA DD for general lrlslarltes but no algnrllhm tends to produce oena tours than the nearest elghbor algnrlthm ammo o I Example Walk aeheeehedeeedehea omlmoa Tnur aeheeedeeea 39 Christofides Algorithm Cnnswu a m mmum wanmng hie dme graph m E suede 2 Add edges dfe m mmumwe ght memnd Ufa the Dddr degree vemcs m the mwmrmm spanmng tree suede 3 Fwd an 81me Urcmt df the numer abewned m Exage 2 suede 4 Cream a mur mm the pew nns mded m Stage 2 by makmd shame m avmd wsmng ntermadwata venees rmrE than DHEE RA m fur deneex nsEHEE but u tends m pdeuEE batty Burs thaw the therarmndrmermwmmumrwae a g nmmnna x9 Example Christofides Algorithm Mme CSCE 350 S Data Structures and Algorithms ChinTser Huang W University of South Carolina I Announcement I Reading assignment Chapter 25 Homework 1 is due today Homework 2 Probierns218 2 19 222 225 227bc234 2 4 1bcd 2 4 4 Account for 4 bone toward nal grade ue on Monday February 9 n class Midterm Exam 1 will be held on Friday February 13 manma z gl Example 3 Matrix multiplication mamas z Plan for Analysis of Recursive Algo thms Decide on parameter 7 indicaung W idenuty aigontnrn39s asre age Determine worst averge and best cases for different input ofsrze 7 Setxuf a recurrence IEanon wrtn an approbnate 705 to man tin exoresang e nurnber of umes tne basic op is executea Solve tne recurrence or at tne veryleast estabirsn re soluuon39s order of growdn by backward ibsm Lmms or anotner rnetnod manma 4 l Example 1 Recursive evaluation of n e nmon 7l12 ne1n for721 and or 1 Recursive de nmon of7l an and v7 for 7 21 and ALGGRlTMM liin 0 1 him mom or mum rr rUumur mt rilllt in u n ilrtlurnl r r 5r ze Basic operauon Recurrence relau on mamas 1 Solvrng the recurrence for M M7 e Mn1 1 M0 o ernruai condmon Method of backward substitution M n e 1 1 Mne211Mne22 Mne312Mne33 Mnenn M0n n manma s 5 Example 2 Tower of Hanoi Puzzle e11 Recurrence for number of moves momma Solving recurrence for number of I moves Mn 2Mn1 1 M1 1 menmus Tree Puzz of calls for the Tower of Hanoi le quot1 quotM H quot momma I Example 3 Counting bits Amomm ii in nu iliiiiii inns n H mm omen nmr W21 makes rn values orn iha Solve ine recurrence onlvf r n e e r smoothness Rule wl1d1 claims mar under very broad assumpnons one order or 9on observe ror n e k gives a correct answer about me order or gron ror all values orn emod or backward smsnmuon smrnble on tis not powers or 2 Solving recurrence for number of I add ns Solve for n 2k A2K A2K391 1 A20 0 momma I F bonac numbers The Fibonacci nurnbers 0112358 1321 The Fibonacci recurrence Fn Fn1 Frr2 0 er Eueiro39s algorithm namre brenenrng in irees spiral ersneiis ieenee orprneeppies reproduction in bees an via the golden ratio popular ulmre The banner Code awnmus 55 Solving Fibonacci recurrence The Fibonacci recurrence cannot be solved with backward substitution Instead we will solve it with a theorem for solving homogeneous 2 quot order linear recurrence with 5 constantcoef clen aXn bXn1 6112 0 DIEDmm CSCE 350 Data Structures and Algorithms ChinTser Huang huangct csescedu University of South Carolina Announcement Reading assignment Chapter 63 Homework Sis assigned on March 6 and is due on Monday March 16 in class Please download it from class website Have you answers naty type Explain your answer clearly and adequately by showing t e steps Study guide for 2 midterm egtltam and omework 4 solution are available on class Site Happy spring break m mug 2 1 Transformiand Conquer Solve problem by transforming inm a more convenient instance of the same problem instance simpli cation presornng I Gatsslari elimil39la oi l a different represenmtion of the same instance r esenbb39an d1 e I balanced seardn ees heaps arid heapsort pol womlal evaluanon by Homer s rule Fast Fourier Trarsform a different problem almgether lobem reduction I r dLl 0m oblerns linear progammll39vg DaD IIEB Instance Simplification Example Presorting Solve instance of problem by transforming into another simplereasier instance of the same P m Many problems involvin lists are easier when list is sorted For example computing the median a special case of selection problem element uniqueness computing the mode sarchin m mug 4 Presorting Example 1 Selec lon Problem Find the kmsmallest element in A1An Special cases Himmum k1 maxim Presortingrbased algorithm sort list e g using mergesort return A lt Partitionrbased algorithm Variablersizerdecrease and conquer pivotsplit at As using partitioning algorithm frorn quicksort ifsk remrri Ms else if sltlt repeatwtth subllstAs1 A7 H55sgtltrepeatwldnsubllstA1 Afsu mama2mg Notes on Selection Problem Presortingbased algorithm 911 logr 01 911 logr Partitionbased algorithm VariablesiZedecrease and conquer worst case Tn Ton n1 gt 90 bestcase om average caseTn Tn2 n1 gt n Extra bene t also identifies the k smallest elemenE not just the km Special cass of max min better simpler linmr algorithm brute force onclusion Presorting does Irothelp in this case ow m 52mg Presorting Example 2 Element Uniqueness Problem Presortingbased algorithm use mergesort optimal n logr scan array in nd repeated mLent 9 3909 ll elements II Brute force algorithm compare all pairs of elements nZ Conclusion Presorting yields signi cant improvement mama2mg 7 Presorting Example 3 Computing A Mode A mode is the value that occurs most often in a given list of numbers For example the mode of 5 1 5 7 5 5 7 is 5 Bruteforce technique construct a list to record the frequency of ach distinct elemen In each imrau on the H11 element is com ared to the smred distinct elemenE If a mamhing is found is frequency is list as a distinct element Worst case complexity 00 when all lhe given 1 elemenE are distinct mus2mg a Computing A Mode With 1 Presorting Algorithm ALGORITHM PresortMadeMlo n 71 Sort the array A l E 0 modfrequem y e o hlghesl requency seen so far while 1 S n7 1 in mlength e1 mmtue e AU while i mengm n 71 and AU mnlength Mime Mllength e mlength 1 if mengm gt modefrequemy modefrequemy e mnlength modeldue e gimme l er runen h M mama2mg 9 Complexity of Preson ModeO The dominating part is on the sorting On logn The complexity of the outer while loop is linear since each element will be visited once for comparison Therefore the complexity of presortMode is On This is much more efficient than the bruteforce algorithm that needs 0 mus2mg m Presorting Example 4 Searching Problem Bruteforce search worst case GIr Presorted search TIrT5mn Tmmt n Gn log n Glog I Gn log I Biliary search Therefore the presorted search is inferior to the brute force searc However if we are going to repmt the searching in the same list many tims presorted search may be more ef cient because the sorting need not be repeated mama2mg n Taxonomy of Searching Algorithms Elementary searching algorithms sequential search Balanced tree searching nees redsblack trees mul way balanced nees 273 trees 234 trees B trees Hashing separam chaining open addressing mus2mg 12 g Balanced Search Trees Attraeuyeness otbrnarysearm Ereels rnarred by dne bad lrnear worstease emerency Two ldeas to overcome lt are to rebalarlce brnary searen tree wnen a new rnseruon rn tree too unbalanced rnstance slmpll cauon AVL V225 ramamen to allow rnore dnan one key per node of a searen tree representau on enange as nznsnnni gl Balanced Trees AVL Trees AVL tree lS narned after re two lnyentors G M Adelsonn Velsky 1922 and E M Landls 1921 e 1997 wno publlsned lt ll l then 1952 paper An algondnrn for dne organlzatlon of lnforrnauon An AVL treels a blnary searcn tree ll l wnlcn for eyery nodet1ne dlrterence between dne n lgHB ole left and 6 g e is Tm m a a le an e wldn t e elgnt ofal39l ernpty tree de ned as 71 balante tattorle s1btree39s nelgnt n ngnt subtree39s nelgnt nznsmm I AVL Tree Example rne nurnber snown aboye eatn node ls re yame fans For an AVL tree eatn node39s balante fatter ls eltner n 1 Dr 71 a b A AVL t n IVquot a nznsnnni Ma t n the Balance of An AVL Tree lnserung a new node to an Avt blnary searcn tree may make ltunbalanoed The new node ls always lnserted as a leaf We Ual39sform lt lnm a balanced one by maven operauons d w e elmer 2 or 72 because of the lnseruon of a new node Where are several sudn nodes we rotate the tree rooted at the There are four types ofromuons and two otunern are rnlrror lrnages of me other two nznsmm Four Types of Rotations for Three Node AVL Trees f s A Xe smgle Rnrobauol39l ft3 Double LRnromuol39l nznsnnni Sll lg e Lnromuol39l if oEE Double Reroba on El General Form Single Rrotation nznsmm General Form Double LRrotation nzmstnna SI Notes on Rotations Rotauons can be done tn constant urne steps Rotau no W or manner utun neet batanced but t stoma t serve e C re ert o abtn y atcn nee te 3 the keys tn tnetett SJbUee snoutd be smaH t than the root the rec t Hr ttmkestntnetn bee Hetgnt n otan AVL nee wttn nnodes ts bounded by tn 5 n 14 o4tgn 2 713277 averag 1o tg 7 o1tortarge 7 So the o erauons otseatcntng and tnseruon tn an AVL Dee take eaogn tn the Worst case tzmstm Example Construct an AVL Tree for g the 39st 5 6 8 3 2 4 7 I w nzmstnna Example Construct an AVL Tree for the st 5 6 8 3 2 4 7 cont nzmstmna CSCE 350 5 Data Structures and Algorithms ChinTsar Huang huangct che SC edu uhryersrty of South Carohha sq Merg esort n two and make copres of each ha f Spht array A0 my rh arrays B0 H2171 and cm W2 71 Sort arrays B and c recursryery Merge sorted arrays B and c rhto array A as foHoWs Repeat the tenawrrrg urrtrt rra eterherre rerhah h arre tme arrays ampere the rrrst erehers m the vemammq unvvacessed Damans ar the arrays aw the smaHev ar the Ma rrta t We mnementmq the mdex rrartatrra the urvvmcessed Dmhan ar that array orrte aH etemmts h me Bf the arays ae pratessad tapy the rerhahrrrg urrpratessed eterherre from the other array hte A 739 may uh r e w nzxmnna arttraa a g Mergesort Example I Pseudocode of Mergesort ALGORITHM utrtttmrt wt rr 7 Hr trrr rrr rrrrrr rrrrrr rrtrrrrttrrrrrt 0thquot mt w v r wontu rtr rrrrrrtttertrrmrgrrrtttr rrr r ttrrrr H hr 1 a utrrhht rrr arr r r rrrrryr M r r hr rrrrrrerrr rrrrtrrrr r aroma arttraa SI Pseudocode of Merge I Efflcrency amonth yrrtrrurrr 7 Wyer rtoaar rh Recurrence H ratrryrrarrrrtr tnnmhvwrvtmut 7 2 n2cmmnfomgt1r 400 13tr r rr 2 r r rZJ r r rI rr39rjr r39Ymr r rrrr Bas coperatwn sacompamson ave rerr rear err CMM771Worstcase quotquotquotfc M quotT I quot 4 quotquot Usmg the Master Theorerh the comp exlty of rhergesort W y atgorrthrhrs rlwiH 39rr rr rt Meg JV Itrs rhore ef crerrtthah Setecuthortahd BubbteSort LINN r W I H wheretheurhecorhptexrtyrsew t rt rsrtrh ptace7 a amtma I Master Theorem 5 Announcement 739n aKnb fn where n e 070 d20 Homework 2 is returned today in class Highest 4 If a ltbd 739n e 0717 Average 323 If a bd 7n e dlog I7 Midterm Exam study guide and sample If a gt bd 739n e d09ba questions have been posted on class website HW score has been updated at CSE dropbox httpsdropboxcsescedu D2112EIEB u2112un9


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

Anthony Lee UC Santa Barbara

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

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Parker Thompson 500 Startups

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

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.