## Adva Nced Dat A Str Uctures Algorithm Analysis-Free PDF

• Date:13 Dec 2019
• Views:38
• Pages:154
• Size:917.36 KB

Share Pdf : Adva Nced Dat A Str Uctures Algorithm Analysis

Report CopyRight/DMCA Form For : Adva Nced Dat A Str Uctures Algorithm Analysis

Transcription:

ROLE OF DATA STRUCTURES,IN COMPUTATION,Makes Computations Faster. Faster is better Another way to make computations faster is to. use parallel or distributed computation,Three Basic Computation Steps. Computation Sequence of Computation Steps,1 Locate Access data values inputs to a step. External External,2 Compute a value output of a step. Input Output,3 Store the new value,Program Algorithm DataStructure Implementation.
The basic method it determines the data items computed. Also the order in which those data items are computed and. hence the order of read write data access operations. Data structures, Supports efficient read write of data items used computed. Total Time Time to access store data Time to compute data. Efficient Algorithm Good method Good data structures. Good Implementation,What is an efficient program,What determines the speed of an Algorithm. A program must also solve a problem Which of the three parts. algorithm data structure and implementation embodies this. ALGORITHM OR METHOD,vs DATA STRUCTURE,Problem Compute the average of three numbers. Two Methods 1 aver x y z 3,2 aver x 3 y 3 z 3, Method 1 superior to Method 2 two less div operations. They access data in the same order x y z aver, Any improvement due to data structure applies equally well to.
both methods,Data structures,a Three variables x y z. b An array nums 0 2, This is inferior to a because accessing an array item takes. more time than accessing a simple variable To access. nums i the executable code has to compute its address. addr nums i addr nums 0 i sizeof int which,involves 1 addition and 1 multiplication. When there are large number of data items naming indi. vidual data items is not practical, Use of individually named data items is not suitable when a. varying number of data items are involved in particular if. they are used as parameters to a function, A Poor Implementation of 1 Using 3 additions and 1 division.
a x y uses 2 additional assignments,LIMITS OF EFFICIENCY. Hardware limit, Physical limits of time speed of electrons and space layout of. circuits This limit is computation problem independent. From 5 mips millions of instructions per sec to 10 mips is an. improvement by the factor of 2, One nano second 10 9 one billionth of a second 10 mips. 100 ns instruction,Software limit, Limitless in a way except for the inherent nature of the problem. That is the limit is problem dependent,Sorting Algorithm A1 O n log n time.
Sorting Algorithm A2 O n2 time,n number of items sorted. A1 is an improvement over A2 by the factor,n log n log n. O n log n is the efficiency limit for sorting Algorithms. MEASURING PERFORMANCE,Analytic Method, Theoretical analysis of the Algorithm s time complexity. Empirical Methods, Count the number of times specific operations are performed by. executing an instrumented version of the program, Measure directly the actual program execution time in a run.
Example of Instrumentation,Original code if x y small x. else small y, Instrumentd code countComparisons initialized elsewhere. if x y small x,else small y,What is wrong with the following instrumentation. if x y countComparisons small x,else small y, Instrument the code below for readCount and writeCount of x. if x 3 y x 5, Show the new code when updates to loopCount is moved outside.
for i j i max i,if x i 0 break, 1 Instrument the code below to count the number of Exchanges. numExchanges and number of comparisons numComparisons. of the array data items Show the values of numExchanges and. numComparisons after each iteration of the outer for loop for the. input items 3 2 4 5 2 0,void crazySort int items int numItems. int i j small, for i 0 i numItems i put ith smallest item in items i. for j i 1 j numItems j,if items i items j exchange. small items j items j items i,items i small,a If we use i numItems 1 in place of i numItems.
in the outer for loop do we still get the same final result. Will it affect the execution time, b Is the algorithm in the code more closely related to inser. tion sort or to selection sort In what way does it differ. 2 For numItems 6 find an input for which crazySort will give. maximum numExchanges When will numExchanges be mini. 3 Give a pseudocode for deciding whether three given line seg. ments of lengths x y and z can form a triangle and if so whether. it is a right angled obtuse angled or an acute angled triangle. Make sure that you minimize the total number operations arith. metic and comparisons of data items, 4 Given an array lengths 1 n of the lengths of n line segments. find a method for testing if they can form a polygon quadrilateral. for n 4 pentagon for n 5 etc,SOLUTION TO SELECTED EXERCISES. 1 void crazySort int items int numItems,int i j small. numComparisons 0 for two elements in items,numExchanges 0 of elements in items.
for i 0 i numItems i put ith smallest item in items i. for j i 1 j numItems j,numComparisons keep it here. if items i items j exchange,numExchanges,small items j items j items i. items i small,printf numComparisons d numExchanges d n. numComparisons numExchanges, After the comparison and exchanges if any for input items 3 2 4 5 2 0. i 0 j 1 items 2 3 4 5 2 0,i 0 j 2 items 2 3 4 5 2 0.
i 0 j 3 items 2 3 4 5 2 0,i 0 j 4 items 2 3 4 5 2 0. i 0 j 5 items 0 3 4 5 2 2,numComparisons 5 numExchanges 2. i 1 j 2 items 0 3 4 5 2 2,i 1 j 3 items 0 3 4 5 2 2. i 1 j 4 items 0 2 4 5 3 2,i 1 j 5 items 0 2 4 5 3 2. numComparisons 9 numExchanges 3,i 2 j 3 items 0 2 4 5 3 2.
i 2 j 4 items 0 2 3 5 4 2,i 2 j 5 items 0 2 2 5 4 3. numComparisons 12 numExchanges 5,i 3 j 4 items 0 2 2 4 5 3. i 3 j 5 items 0 2 2 3 5 4,numComparisons 14 numExchanges 7. i 4 j 5 items 0 2 2 3 4 5,numComparisons 15 numExchanges 8. i 5 j 6 items 0 2 2 3 4 5,numComparisons 15 numExchanges 8.
This is more closely related to selection sort which involves atn most one. exchange for each iteration of outer loop Comparisons is still C 2. 2 Triangle classification pseudocode assume that 0 x y z. zSquare z z xySquareSum x x y y,if zSquare xySquareSum. right angled triangle,else if zSquare xySquareSum,obtuse angled triangle. else acute angled triangle,else not a triangle,3 Condition for polygon. The largest length is less than the sum of the other lengths. The lengths 2 4 5 20 will not make a quadrilateral because. 20 2 4 5 11 but the lengths 2 4 5 10 will,ANALYZING NUMBER OF EXCHANGES. IN CRAZY SORT,Pseudocode 1,1 Create all possible permutations p of 0 1 2 n 1.
2 For each p apply crazySort and determine numExchanges. 3 Collect these data to determine numPermutations i permuta. tions which has numExchanges i for i 0 2 C 2n, 4 Plot numPermutations i against i to visualize the behavior of. numExchanges,Pseudocode 2 No need to store all n permutations. 1 For i 0 i C 2n i initialize numPermutations i 0, 2 While there is a nextPermutation n p do the following. a Apply crazySort to p and determine numExchagnes,b Add 1 to numPermutation numExchanges. 3 Plot numPermutations i against i, Note We can use this idea to analyze other sorting algorithms.
If p is a permutation of S 0 1 2 n 1 then how to deter. mine the nextPermutation p in the lexicographic order Shown. below are permutations for n 4 in lexicographic order. 0123 0312 1203 2013 2301 3102,0132 0321 1230 2031 2310 3120. 0213 1023 1302 2103 3012 3201,0231 1032 1320 2130 3021 3210. PSEUDOCODE vs CODE,Characteristics of Good Pseudocode. Shows the key concepts and the key computation steps of the. Algorithm avoiding too much details,Avoids dependency on any specific prog language. Allows determining the correctness of the Algorithm. Allows choosing a suitable data structures for an efficient imple. mentation and complexity analysis, Example Compute the number of positive and negative items in.
nums 0 n 1 assume each nums i 0, A Pseudocode 1 Initialize positiveCount negativeCount 0. 2 Use each nums i to increment one of the counts by one. Code 1 1 positiveCount negativeCount 0,2 1 for i 0 i n i each nums i 0. 2 2 if 0 nums i positiveCount,2 3 else negativeCount. B Pseudocode 1 Initialize positiveCount 0, 2 Use each nums i 0 to increment positiveCount by one. 3 Let negativeCount n positiveCount,Code 1 positiveCount 0.
2 for i 0 i n i each nums i 0,3 if 0 nums i positiveCount. 4 negativeCount n positiveCount,Why is B slightly more efficient than A. Writing a pseudocode requires skills to express,an Algorithm in a concise and yet clear fashion. PSEUDOCODE FOR SELECTION SORT, Idea Successively find the ith smallest item i 0 1. Algorithm Selection Sort,Input Array items and its size numItems.
Output Array items sorted in increasing order, 1 For each i in 0 1 numItems 1 in some order do a b. a Find the ith smallest item in items,b Place it at position i in items. Finding ith smallest item in items, Finding ith smallest item directly is difficult but it is easy if we. know all the kth smallest items for k 0 1 2 i 1,It is the smallest item among the remaining items. If we assume that items k 0 k i 1 are the kth smallest. items then smallest item in items i numItems 1 ith smallest. item This gives the pseudocode,a 1 smallestItemIndex i.
a 2 for j i 1 j numItems j,a 3 if items j items smallestItemIndex. a 4 then smallestItemIndex j, Question In what way a 1 a 4 is better than step a. Placing ith smallest item at position i in items, b 1 if smallestItemIndex i why not smallestItemIndex i. b 2 then exchange items i and items smallestItemIndex. What comes before how, 1 Which of put the items in right places and fill the places by. right items best describes the selection sort Algorithm Shown. below are the steps in the two methods for input 3 5 0 2 4 1. Put the items in Fill the places,right places with right items.
1 2 5 0 3 4 1 0 5 3 2 4 1,3 moved to right place 1st place is filled by 0. 2 0 5 2 3 4 1 0 1 3 2 4 5,2 moved to right place 2nd place is filled by 1. 3 0 5 2 3 4 1 0 1 2 3 4 5,0 already in right place 3rd place is filled by 2. 4 0 1 2 3 4 5 0 1 2 3 4 5,5 moved to right place all places filled properly. 5 0 1 2 3 4 5,all items in right places, Note that once an item is put in right place you must not change.
its position while putting other items in proper places It is for. this reason we make an exchange and not an insertion when we. move an item in the right place The insertion after removing 3. from its current position in 3 5 0 2 4 1 would have given 5. 0 2 3 4 1 but not 2 5 0 3 4 1 as we showed above, 2 Which input array for the set numbers 0 1 2 3 4 5 requires. maximum number of exchanges in the first approach,3 Give a pseudocode for the first approach. ANOTHER EXAMPLE OF PSEUDOCODE, Problem Find the position of rightmost 00 in binString 0 n 1. 1 Search for 0 right to left upto position 1 initially start at position. 2 If 0 is found and the item to its left is 1 then go back to step 1. to start the search for 0 from the left of the current position. Three Implementations Only the first one fits the pseudocode. 1 i n length of binString,do for i i 1 i 0 i,if 0 binString i break. while 1 binString i has a bug find it,2 for i n 1 i 0 i.
if 0 binString i 0 binString i 1,break inefficient but works. 3 for i n 1 i 0 i bad for loop body updates i,if 0 binString i 0 binString i. break works and efficient, Show how these implementations work differently using the bin. String 000111010101 Extend each implementation to return. the position of the left 0 of the rightmost 00, Instrument each code for readCount of the items in binString. Which of 1 3 is the least efficient in terms readCount. Give a pseudocode to find rightmost 00 without checking all. bits from right till 00 is found,It is not necessary to sacrifice clarity.
for the sake of efficiency, 1 BinStrings n m x x is a binary string of length n and m. ones 0 m n The strings in BinStrings 4 2 in lexicographic. 0011 0101 0110 1001 1010 1100, Which of the pseudocodes below for generating the strings in. BinStrings n m in lexicographic order is more efficient. a 1 Generate and save all binary strings of length n in. lexicographic order,2 Throw away the strings which have numOnes m. b 1 Generate the first binary string 0n m 1m Bin,Strings n m. 2 Successively create the next string in Bin,Strings n m until the last string 1m 0n m.
Which of the three characteristics of a good pseudocode hold for. each of these pseudocodes, 2 Give the pseudocode of a recursive Algorithm for generating the. binary strings in BinStrings n m in lexicographic order. 3 Give an efficient pseudocode for finding the position of rightmost. 01 in an arbitrary string x BinStrings n m The underlined. portion in 10110011100 shows the rightmost 01 Give enough. details so that one can determine the number of times various. items x i in the array x are looked at, 4 Given a string x BinStrings n m give a pseudocode for gen. erating the next string in BinStrings n m if any,ALWAYS TEST YOUR METHOD. AND YOUR ALGORITHM, Create a few general examples of input and the corresponding. ROLE OF DAT A STR UCTURES IN COMPUTATION Makes Computations Faster algorithm data structure and implementation embodies this 1 3 ALGORITHM OR METHOD