DATA STRUCALGORITHMS COP 3530
Popular in Course
Popular in Computer Programming
This 51 page Class Notes was uploaded by Hans Farrell PhD on Friday September 18, 2015. The Class Notes belongs to COP 3530 at University of Florida taught by Staff in Fall. Since its upload, it has received 57 views. For similar materials see /class/206695/cop-3530-university-of-florida in Computer Programming at University of Florida.
Reviews for DATA STRUCALGORITHMS
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: 09/18/15
Arrays 1D Array Representation In Java C and CH Memory I start 1dimensiona1 array X a b c d 0 map into contiguous memory locations locationXi start i Space Overhead Memory start space overhead 4 bytes for start 4 bytes for Xlength 8 bytes excludes space needed for the elements of X 2D Arrays The elements of a 2dimensional array a declared as int a new int34 may be shown as a table a00 a01 a02 a03 a10 a11 a12 a13 a20 a21 a22 a23 Rows Of A 2D Array W rowo W fowl W rowz Columns Of A 2D Array a0l 0 a0 1 a0 2 a0l 3 a1l 0 a1 1 a1 2 am 3 a2 0 a2 1 a2 2 a2 3 column 0 column 1 column 2 column 3 2D Array Representation In Java C and C 2dimensiona1 array X a b c d 63 f3 g3 h i j k 1 View 2D array as a 1D array of rows X row0 rowl row 2 row 0 ab c 1 row 1 e f g h r0w2 ij k 1 and store as 4 1D arrays 2D Array Representation In Java C and C xn Xlength 3 X0length X1length X2length 4 Space Overhead space overhead overhead for 4 1D arrays 4 8 bytes 32 bytes number of rows l X 8 bytes Array Representation In J ava C and C x i m This representation is called the arrayof arrays representation Requires contiguous memory of size 3 4 4 and 4 for the 4 1D arrays 1 memory block of size number of rows and number of rows blocks of size number of columns RowMaj or Mapping Example 3 X 4 array abcd efgh i j kl Convert into 1D array y by collecting elements by rows Within a row elements are collected from left to right Rows are collected from top to bottom We get y a b c d e f g h ij k l Locating Element Xi j assume X has r rows and 0 columns each row has 0 elements i rows to the left of row i so ic elements to the left of Xi0 so Xij is mapped to position ic j ofthe 1D array Space Overhead 4 bytes for start of 1D array 4 bytes for length of 1D array 4 bytes for c number of columns 12 bytes number of rows length c Disadvantage Need contiguous memory of size rc ColumnMaj or Mapping abcd e f g h i j kl 0 Convert into 1D array y by collecting elements by columns 0 Within a column elements are collected from top to bottom 0 Columns are collected from left to right a 63 i3 b3 f3j3 03 g3 k3 d3 113 Matrix Table of values Has rows and columns but numbering begins at 1 rather than 0 a b c 1 row 1 e f g h row 2 i j k 1 row 3 0 Use notation Xlj rather than Xij 0 May use a 2D array to represent a matriX Shortcomings Of Using A 2D Array For A Matrix 0 Indexes are off by l 0 Java arrays do not support matrix operations such as add transpose multiply and so on Suppose that x and y are 2D arrays Can t do x y x y x y etc in Java 0 Develop a class Matrix for objectoriented support of all matrix operations See text Diagonal Matrix An 11 x 11 matrix in which all nonzero terms are on the diagonal Diagonal Matrix 000 0 00 00 0 000 0 xiJ is on diagonal iff i j 0 number of diagonal elements in an n x 11 matrix is n 0 non diagonal elements are zero 0 store diagonal only vs 112 whole Lower Triangular Matrix An 11 x 11 matrix in which all nonzero terms are either on or below the diagonal l 0 0 0 2 3 0 0 4 5 6 0 7 8 9 10 xiJ is part of lower triangle iff i gt j 0 number of elements in lower triangle is l 2 n nnl2 0 store only the lower triangle Array Of Arrays Representation xu Use an irregular 2D array length of rows is not required to be the same Creating And Using An Irregular Array declare a twodimensional array variable and allocate the desired number of rows int irregularArray new int numberOfRows now allocate space for the elements in each row for inti 0 i lt numberOfRows i irregularArrayi new int sizei use the array like any regular array irregularArray2 3 5 irregularArray4 6 irregularArray23 2 irregularArrayl 1 3 Map Lower Triangular Array Into A 1D Array Use rowmajor order but omit terms that are not part of the lower triangle For the matrix 100 0 23 0 0 45 6 0 78910 weget 123456789 10 Index Of Element ij 0 l 3 6 m 0 Order is row 1 row 2 row 3 0 Row i is preceded by rows 1 2 il Size of row i is i 0 Number of elements that precede row i is 123 i1ii12 0 So element iJ is at position iil2 j 1 of the 1D array Q V Dynamic Programming Sequence of decisions Problem state Principle of optimality Dynamic Programming Recurrence Equations Solution of recurrence equations Sequence Of Decisions As in the greedy method the solution to a problem is viewed as the result of a sequence of decisions Unlike the greedy method decisions are not made in a greedy and binding manner 01 Knapsack Problem 3 Let xi 1 when item i is selected and let xi 0 when item i is not selected n maximize 1 pi Xi 1 n subject to Z1 Wi xi lt c 1 andxi00r l for alli All profits and weights are positive Sequence Of Decisions 9 Decide the xivalues in the order x1 x2 x3 xquot Decide the xivalues in the order xquot xn1 xmz x1 Decide the x values in the order x1 xquot xi xn1 Or any other order Problem State I The state of the 01 knapsack problem is given by r the weights and pro ts of the available items I the capacity ofthe knapsack I When a decision on one of the xi values is made the problem state changes 7 item i is no longer available I the remaining knapsack capacity may be less Problem State I Suppose that decisions are made in the order x1 x2 x3 x I The initial state ofthe problem is described by the pair 0 Items 1 through n are available the weights pro ts and n are implicit The available knapsack capacity is c I Following the rst decision the state becomes one ofthe following39 2 c when the decision is to set x1 0 2 cwl when the decision is to setxr 1 Problem State I Suppose that decisions are made in the order x xnrl xnrz x1 I The initial state ofthe problem is described by the pair n 0 Items 1 through n are available the weighs pro m and rst item index are implicit The available knapsack capacity is c I Following the rst decision the state becomes one ofthe following nl c when the decision is to set X 0 nl cwn when the decision is to set X 1 Principle Of Optimality I An optimal solution satisfies the following property I No matter what the first decision the remaining decisions are optimal with respect to the state that results from this decision I Dynamic programming may be used only when the principle of optimality holds 3 01 Knapsack Problem 4 Suppose that decisions are made in the order x1 x2 x3 xquot 0 Letxl a1 x2a2 x3 a3 xn anbe an optimal solution If a1 0 then following the first decision the state is 2 0 a2 a3 anmust be an optimal solution to the knapsack instance given by the state 2c X1a10 H n maximize 2 pi xi 1 n subject to Wi xi lt c 1 2 andxi00r l foralli If not this instance has a better solution b2 b3 1391 n 2 Pabi gt piai i2 2 X1a10 3 x1 a1 x2 b2 x3 b3 xquot bn is a better solution to the original instance than is x1 a1 x2 a2x3 a3 xnan Sox1a1x a cannot be an optimal solution a contradiction with the assumption that it is optimal X1a1l E Next consider the case a1 1 Following the first decision the state is 2 cWl a2 a3 an must be an optimal solution to the knapsack instance given by the state 2c 39W1 X1a1l A n maximize 2 pi xi 1 n subject to 2 Wi xi lt 339 W1 1 and xi 0 or 1 for alli I If not this instance has a better solution b2 b3 n n n 2 Fab gt piai 12 12 X1a1l x1 a1 x2b2 x3 xnbn is abetter solution to the original instance than is x1 a1 x2 a2 x3 a3 xnan I So x1 a1 x2 a2 x3 a3 xquot an cannotbe an optimal solution a contradiction with the assumption that it is optimal 01 Knapsack Problem I Therefore no matter What the first decision the remaining decisions are optimal with respect to the state that results from this decision I The principle of optimality holds and dynamic programming may be app ie Dynamic Programming Recurrence I Let fiy be the pro t Value of the optimal solution to the knapsack instance de ned by the state iy Items i through n are available Available capacity is y I For the time being assume that We Wish to determine only the Value of the best solution Later we will wony about determining the xs that yield this maximum Value I Under this assumption our task is to determine flc Dynamic Pro gramming Recurrence fny is the value of the optimal solution to the knapsack instance defined by the state ny 7 Only item rr is available 7 Available capacity is y If Wn lt y fmy Pn lfwn gt y fny 0 Dynamic Programming Recurrence Suppose thati lt n fiy is the value of the optimal solution to the knapsack instance defined by the state iy 7 Items i through rr are available 7 Available capacity is y Suppose that in the optimal solution for the state iy the first decision is to set xi 0 From the principle of optimality we have shown that this principle holds for the knapsack problem it follows that fiy fily Dynamic Pro gramming Recurrence The only other possibility for the first decision is xi 1 The case xi 1 can arise only when y gt w From the principle of optimality it follows that fLY fi1YW P Combining the two cases we get 7 fiy fily Whenever y lt W V fiy maxfily filyWQ p y gtW1 Recursive Code retur39n fiy private static int fint i int y if i n return 0 ltwn 7 0 pn if y lt wi return fi l y return Mathmaxfi l y fi1y W1 Plil Recursion Tree flc f c f2 cWl f3c f3cw2 f3CW1 f3c w1 iwz f4c f4cw3 f4cw2 f4cw17w 3gt f5cw1 W3 7w4 r5c n Time Complexity 1 0 Let tn be the time required When n items are available t0 tl a Where a is a constant 0 When tgt l tn lt 2tn l b Where b is a constant tn 02 Solving dynamic programming recurrences a recursively can be hazardous to run time 3 Reducing Run Time flc f c f2 cWl f3c f3cw2 f3CW1 f3c w1 iwz f4c f4cw3 f4cw2 f5cw1 W3 7w4 f4cw1 W3 r5c Time Complexity 0 Level i of the recursion tree has up to 2i391 nodes 0 At each such node an fiy is computed Several nodes may compute the same fiy We can save time by not recomputing already computed fiys Save computed fiys in a dictionary Key is i y value fi y is computed recursively only when iy is not in the dictionary Otherwise the dictionary value is used Integer Weights Assume that each weight is an integer The knapsack capacity c may also be assumed to be an integer Only fiys with l lt i lt n and 0 lt y lt c are of interest Even though level i of the recursion tree has up to 2quot1 nodes at most cl represent different fiys Integer Weights Dictionary I Use an array fArray as the dictionary I fArrayln0c I fArrayiy 1 iff fiy not yet computed I This initialization is done before the recursive method is invoked I The initialization takes Ocn time No Recomputation Code I private static int fint i int y if fArrayiy gt 0 retum fAnayiy if i n fAnayiy CV lt Wlnl 70 3 PM return fArrayiYl if 0 ltWlil fAITaYUllYl m 1gt Y else fArrayiy Mathmaxfi 1 y fi1gty 39 W111 P111 return fArrayiy Time Complexity tn Ocn Analysis done in text Good when cn is small relative to 2quot n 3 c 1010101 W 100102 1000321 6327 p 102 505 5 2n 8 cn 3030303 Data Compression 0 Reduce the size of data Reduces storage space and hence storage cost Compression ratio original data sizecompressed data size Reduces time to retrieve and transmit data g g Lossless And Lossy Compression a 39 compressedData compressoriginalData decompressedData decompresscompressedData When originalData decompressedData the compression is lossless When originalData decompressedData the compression is lossy a Lossless And Lossy Compression Lossy compressors generally obtain much higher compression ratios than do lossless compressors Say 100 vs 2 39 Lossless compression is essential in applications such as text le compression Lossy compression is acceptable in many imaging applications In video transmission a slight loss in the transmitted video is not noticed by the human eye a Text Compression a Lossless compression is essential Popular text compressors such as zip and Unix s compress are based I on the LZW LempelZiv Welch method a LZW Compression a Character sequences in the original text are replaced by codes that are dynamically determined 0 The code table is not encoded into the compressed text because it may be reconstructed from the compressed text during decompression Q LZW Compression g Assume the letters in the text are limited to a b In practice the alphabet may be the 256 character ASCII set The characters in the alphabet are assigned code numbers beginning at 0 The initial code table is a LZW Compression g Original text abababbabaabbabbaabba Compression is done by scanning the original text from left to right Find longest pre x p for which there is a code in the code table Represent p by its code pCode and assign the next available code number to pc where c is the next character in the text that is to be compressed g LZW Compression a Original text abababbabaabbabbaabba p a pCode O c b Represent a by O and enter ab into the code table Compressed text 0 Q LZW Comiression a Original text abababbabaabbabbaabba Compressed text 0 p b pCode 1 c a Represent b by 1 and enter ba into the code table Compressed text 01 Q LZW Comiression g Original text abababbabaabbabbaabba Compressed text 01 p ab pCode 2 c a Represent ab by 2 and enter aba into the code table Compressed text 012 g LZW Comiression a Original text abababbabaabbabbaabba Compressed text 012 p ab pCode 2 c b Represent ab by 2 and enter abb into the code table Compressed text 0122 a LZW Compression g Original text abababbabaabbabbaabba Compressed text 0122 p ba pCode 3 c b Represent ba by 3 and enter bab into the code table Compressed text 01223 a LZW Compression g Original text abababbabaabbabbaabba Compressed text 01223 p ba pCode 3 c a Represent ba by 3 and enter baa into the code table Compressed text 012233 a LZW Compression g Original text abababbabaabbabbaabba Compressed text 012233 p abb pCode 5 c a Represent abb by 5 and enter abba into the code table Compressed text 0122335 a LZW Compression g Original text abababbabaabbabbaabba Compressed text 0122335 p abba pCode 8 c a Represent abba by 8 and enter abbaa into the code table Compressed text 01223358 a LZW Compression 3 Original text abababbabaabbabbaabba Compressed text 01223358 p abba pCode 8 c null Represent abba by 8 Compressed text 012233588 a Code Table Representation Dictionary Pairs are key element keycode Operations are getkey and putkey code Limit number of codes to 212 Use a hash table Convert variable length keys into xed length keys Each key has the form pc where the string p is a key that is already in the table Replace pc with pCodec a Code Table Representation a LZW Decompression Original text abababbabaabbabbaabba Compressed text 012233588 Convert codes to text from left to right 0 represents a Decompressed text a pCode O and p a p a followed by next text character 0 is entered into the code table LZW Decomiression Original text abababbabaabbabbaabba Compressed text 012233588 1 represents b Decompressed text ab pCode 1 and p b lastP a followed by rst character of p is entered into the code table LZW Decomiression Original text abababbabaabbabbaabba Compressed text 012233588 2 represents ab Decompressed text abab pCode 2 and p ab lastP b followed by rst character of p is entered into the code table LZW Decomiression Original text abababbabaabbabbaabba Compressed text 012233588 2 represents ab Decompressed text ababab pCode 2 and p ab lastP ab followed by rst character of p is entered into the code table LZW Decomiression Original text abababbabaabbabbaabba Compressed text 012233588 3 represents ba Decompressed text abababba pCode 3 and p ba lastP ab followed by rst character of p is entered into the code table LZW Decomiression Original text abababbabaabbabbaabba Compressed text 012233588 3 represents ba Decompressed text abababbaba pCode 3 and p ba lastP ba followed by rst character of p is entered into the code table LZW Decomiression Original text abababbabaabbabbaabba Compressed text 012233588 5 represents abb Decompressed text abababbabaabb pCode 5 and p abb lastP ba followed by rst character of p is entered into the code table LZW Decomiression Original text abababbabaabbabbaabba Compressed text 012233588 8 represents 27 When a code is not in the table its key is lastP followed by rst character of lastP lastP abb So 8 represents abba LZW Decomiression Original text abababbabaabbabbaabba Compressed text 012233588 8 represents abba Decompressed text abababbabaabbabbaabba pCode 8 and p abba lastP abba followed by rst character of p is entered into the code table Code Table Re resentation Dictionary Pairs are key element code what the code represents code codeKey Operations are getkey and putkey code 0 Keys are integers O 1 2 Use a 1D array codeTable codeTablecode codeKey Each code key has the form pc where the string p is a code key that is already in the table Replace pc with pCodec Time Complexity Q 39 Compression 0n expected time where n is the length of the text that is being compressed Decompression 0n time where n is the length of the decompressed ten Image Compression 39 GIF reduce color map to a few colors represent each by a small code good for graphics cartoons etc JPEG transform to frequency domain quantize frequency coef cients zigzag scan then Huffman code Video Compression 39 MPEG uses 3 kinds of frames I P and B frames I frames are compressed like JPEG P frames depend on previous 1 or P frame 0 B frames depend on nearest I andor P Describe rotation translation expansion then describe differences
Are you sure you want to buy this material for
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'