### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Data Structures and Algorithms I CS 240

CSU Pomona

GPA 3.57

### View Full Document

## 23

## 0

## Popular in Course

## Popular in ComputerScienence

This 72 page Class Notes was uploaded by Jean Dach on Saturday October 3, 2015. The Class Notes belongs to CS 240 at California State Polytechnic University taught by Fuh Sang in Fall. Since its upload, it has received 23 views. For similar materials see /class/218307/cs-240-california-state-polytechnic-university in ComputerScienence at California State Polytechnic University.

## Reviews for Data Structures and Algorithms I

### 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/03/15

Chapter 1 Analysis of Algorithms Topics Algorithms Order Big 0 Notation Best Case Worst Case Analysis Average Case Analysis Theoretical approach vs Experimental approach Mathematical Background Algorithms An algorithm is a simple unambiguous mechanical procedure to carry out some task Why algorithm instead of program Writing an algorithm is simpler because we don t need to worry about the detailed implementation or language syntax An algorithm is easier to read than a program written in for instance C Multiplying Two Positive Integers For example 45 x 19 Algorithm 1 45 19 x 405 45 855 Multiplying Two Positive Integers Algorithm 2 Multiplier AZ Multiplicand Result B2 pick numbers in the 2ncl column when the corresponding number under the multiplier is odd 19 19 38 76 76 152 152 304 608 608 855 Instances An instance of a problem is a specific assignment of values to the parameters The above algorithm can be used for multiplying any two positive integers we say that 45 19 is an instance of this problem Most problems have infinite collection of instances It s ok to define the domain ie the set of instances to be considered And the algorithm should work for all instances in that domain Although the above algorithm will not work if the first operand is negative this does not invalidate the algorithm since 45 19 is not an instance of the problem being considered Algorithm 1 vs Algorithm 2 Algorithm 1 may look faster But Algorithm 2 doesn t need to memorize any multiplication table you only need to know how to divide a number by 2 how to double a number and how to add numbers In fact quotdivide by 2 and quotdouble a number can be done by quotshift right and quotshift left bitwise operations respectively On most older microprocessors these operations are slightly faster than addition and subtraction and usually significantly faster than multiplication and division operations Frequency Count Usually we use the frequency count to compare algorithms Consider the following three programs a b C foriltondo forlzltondo xxy forj1tondo xxy The frequency count of statement xxy is 1 n n2 No matter which machine we use to run these programs the execution time of b should be n times the execution time of a Order What is the frequency count for the following program forieltondo forjeitondo x forjeltoido y The frequency count of different algorithms may be 9n245 10n2 11n2 104 etc It s hard to compare them so we introduce Order Notation to define complexity classes BigO Notation Definitionfn Ogn if and only if El two positive constants c and no such that fn S c gn V n 2 n0 So gn is the upper bound offn Example 17n2 5 0n2 because 17n2 5 S 17n2 V n 2 1 c 17 n0 1 Example Is 35n3 100 On3 yes because 35n3 100 S 36n3 V n 2 5 c 36 n0 5 Questions Is 62n n2 02 Is 4n3 3n2 0n2 ls 2n1 02 Is 22n 02 Is 3n 2 On3 11 0 Notation Definitionfn Qgn if and only if El two positive constants c and no such that fn 2 c gn V n 2 n0 So gn is the lower bound offn Example 3n 2 Qn because 3n223n Vn21 c 3 n0 1 Example Is 3n 2 01 yes because 3n2211 Vn21 c 1 n0 1 Questions Is 62n n2 Qn100 Is 17n2 5 Qn2 13 9 Notation Definitionfn Ggn if and only if El three positive constants c1 c2 no such that Cl gn S fn S c2 gn V n 2 n0 So gn is both the upper and the lower bound offn 99 iff 09 and Q9n Example 3n 2 9n because 3n S 3n2S 4n V n22 c13c24n02 1 4 Questions 53n29n2 0 Is 62n n2 92 0 Is 4n3 3n2 9n2 Property of Order Transitive ffn 0gn and 07 0hn then f0 0hn ffn 0gn and 07 0hn then f0 0hn ffn 9gn and 07 90707 then f0 90707 Reflexive f0 0fn fn Qfn fn 9fn Symmetric fn 9gn iffgn 9fn fn 0gn iffgn Qfn 16 The Importance of Order Notation Algorithm 1 Algorithm 2 Algorithm 3 Algorithm 4 Algorithm 5 2n Frequency 33n 46nlogn 13n2 34n3 count n10 lt 1 sec lt 1 sec lt 1 sec lt 1 sec lt 1 sec n10000 lt 1 sec 6 sec 22 min 39 days 4x1014 centuries where n is the size of the instance For instance bubble sort takes 6n2 where n is the total number of elements to be sorted 17 Complexity Classes log n n linear time log Polynomial time easy or tractable n2 n3 2n Exponential time hard or intractable n For example if algorithm A has frequency count 33n100 which is en and algorithm B has frequency count 46n2 which is also 6n then we say that they are in the same complexity class Running Time 0 Most algorithms transform input objects into output objects The running time of an algorithm typically grows with the input size although it may also vary for different inputs of the same size We will study the relationship between the running time of an algorithm and the size of its input Example suppose a sorting algorithm has complexity 9nlog2n If it takes 100 units for a list of length 64 how long it will take for a list of length 512 64 log264 100 units 512 log2512 x units so x 512 x 9 x100 64 x 6 1200 units 19 Questions A search algorithm s complexity is 9log2n If it takes 50 time units for a list of length 32 how long would we expect it to take for a list of length 1024 Suppose an algorithm with complexity 9n3 takes 10 minutes for a problem with input size 100 What size problem would we expect to be able to solve in 270 minutes 20 Analysis of Algorithms We will show you best case and worst case analysis with the following example The groblem sort n elements into nondecreasing order Solution insertion sort Idea insert the ith element into a sorted array of length il by looking at numbers one at a time for all igt1 21 Best Case Worst Case Analysis public static void insertionSortint a for int i1 iltalength i int current ai int j i l while jgtOampampajgtcurrent ajlaj ajl current Best Case Worst Case Analysis The inner loop will be skipped when the input is sorted Best case performance is 6n or On Worst case performance is 9n2 or Onz The running time of insertion sort is between On to Onz or we can say that the running time is bound to Onz However it s improper to say that the running time of insertion sort is 9n2 since it can run with On when the input is sorted 23 Average Case Analysis The problem finding the value x in array a of n elements Solution sequential search public static int sSearchint a int x for int i0 iltalength i if aix return i return 1 2 4 Average Case Analysis 1 Assume x is in the array and assume equal probability for x being at any location then probxkth Vn VlskSn If xkth of key comparisons k so An Vn 1 Vn 2 Vn n Vn 12n n1 2 about half of the array is searched 2 Average Case Analysis Ifx may not be in the array assume probx in arrayp so probxkthp Vn probx not in array1 p and it takes n comparisons to know that x is not in the array so An p Vn 12n 1 p n n 1p2 p2 if p1 An n12 as calculated in case 1 if pV2 An n about of the array is searched Algorithm Analysis Best case is not representative Average case is more descriptive but complicated to calculate involves considering all possible instances assumptions and probabilities So we emphasize on worst case analysis Theoretical Approach There are two ways to compare algorithms theoretical approach and experimental approach Theoretical Approach find the amount of time needed for each algorithm using frequency count every statement vs key comparisons based on the size of input Example The traveling salesman problem TSP Given a set of cities and the cost function for every pair of two cities find a tour with minimum cost where a tour is a directed cycle starting from city i visiting every other cities exactly once and returning to i straightforward solution n with dynamic programming nZZn 28 Experimental Approach Experimental Approach code the algorithm test the program on a computer with different instances and record the actual time spent in each execution After performing several experiments on many different test inputs of various sizes we can visualize the results by plotting the performance of each run of the algorithm as a point with xcoordinate equal to the input size n and ycoordinate equal to the running time t See the following picture spuooes uonnos e 196 0 sum e eJeAV OZ 9L 0L Experimental Approach 0 quot r quot distributed Number of robots Theoretical vs Experimental Theoretical analysis allows us to evaluate the speed of an algorithm independent of the hardwaresoftware environment too complicated for averagecase analysis in most applications Experimental analysis Experiments can be done only on a limited set of test inputs so they may not be indicative of the running time on other inputs not included in the experiment Complements traditional theoretical analysis Mathematical Background Definition logbx y if by x for bgt1 In other words y is the power to which b must be raised in order to get x logb is a strictly increasing function so if x1ltx2 then logb x1 lt logb x2 logb is a onetoone function so if logb x1 logb x2 then x1x2 logb 1 O Vb logb xa a logbx Mathematical Background logbx1 x2 logb x1 logb x2 xllogb x2 leogb x1 To convert from one base to another logblx M so 9Iog2n 9Iog100n 10gb2 b1 nn1 Sum of consecutive integers 1211 T k I ak11 Geometric sums Za 1 i0 a Note Iog2 lg logen Exercise Verify whether each of the following pairs of functions in the same complexity class If so justify your answer Otherwise rank them by order of growth from low to high Note that two functions fn and gn are in the same class if and only if nf gh l a n1 n 2n ZnZ c Z39g n dn1Ign 25 34 Exercise Consider the following algorithm a find the total frequency count for all statements in CountSort b apply this algorithm to sort the list 60 35 81 98 14 47 Procedure CountSort AOn l for i 6 O to n l do Counti lt O for i 6 O to n 2 do for j il to n l do if AiltAj Count j 6 Countj 1 else Counti Counti l for i 6 O to n l do SCounti lt Ai return S 33 Exercise Verify state true or false the following equations Justify your answer a 2n1 3n1 93n b x10n27n 9n2 C n1001 n n 0n1001 d gn Qngn 36 Chapter 1 Analysis of Algorithms Topics Algorithms Order Big 0 Notation Best Case Worst Case Analysis Average Case Analysis Theoretical approach vs Experimental approach Mathematical Background Algorithms An algorithm is a simple unambiguous mechanical procedure to carry out some task Why algorithm instead of program Writing an algorithm is simpler because we don t need to worry about the detailed implementation or language syntax An algorithm is easier to read than a program written in for instance C Multiplying Two Positive Integers For example 45 x 19 Algorithm 1 45 19 x 405 45 855 Multiplying Two Positive Integers Algorithm 2 Multiplier AZ Multiplicand Result B2 pick numbers in the 2ncl column when the corresponding number under the multiplier is odd 19 19 38 76 76 152 152 304 608 608 855 Instances An instance of a problem is a specific assignment of values to the parameters The above algorithm can be used for multiplying any two positive integers we say that 45 19 is an instance of this problem Most problems have infinite collection of instances It s ok to define the domain ie the set of instances to be considered And the algorithm should work for all instances in that domain Although the above algorithm will not work if the first operand is negative this does not invalidate the algorithm since 45 19 is not an instance of the problem being considered Algorithm 1 vs Algorithm 2 Algorithm 1 may look faster But Algorithm 2 doesn t need to memorize any multiplication table you only need to know how to divide a number by 2 how to double a number and how to add numbers In fact quotdivide by 2 and quotdouble a number can be done by quotshift right and quotshift left bitwise operations respectively On most older microprocessors these operations are slightly faster than addition and subtraction and usually significantly faster than multiplication and division operations Frequency Count Usually we use the frequency count to compare algorithms Consider the following three programs a b C foriltondo forlzltondo xxy forj1tondo xxy The frequency count of statement xxy is 1 n n2 No matter which machine we use to run these programs the execution time of b should be n times the execution time of a Order What is the frequency count for the following program forieltondo forjeitondo x forjeltoido y The frequency count of different algorithms may be 9n245 10n2 11n2 104 etc It s hard to compare them so we introduce Order Notation to define complexity classes BigO Notation Definitionfn Ogn if and only if El two positive constants c and no such that fn S c gn V n 2 n0 So gn is the upper bound offn Example 17n2 5 0n2 because 17n2 5 S 17n2 V n 2 1 c 17 n0 1 Example Is 35n3 100 On3 yes because 35n3 100 S 36n3 V n 2 5 c 36 n0 5 Questions Is 62n n2 02 Is 4n3 3n2 0n2 ls 2n1 02 Is 22n 02 Is 3n 2 On3 11 0 Notation Definitionfn Qgn if and only if El two positive constants c and no such that fn 2 c gn V n 2 n0 So gn is the lower bound offn Example 3n 2 Qn because 3n223n Vn21 c 3 n0 1 Example Is 3n 2 01 yes because 3n2211 Vn21 c 1 n0 1 Questions Is 62n n2 Qn100 Is 17n2 5 Qn2 13 9 Notation Definitionfn Ggn if and only if El three positive constants c1 c2 no such that Cl gn S fn S c2 gn V n 2 n0 So gn is both the upper and the lower bound offn 99 iff 09 and Q9n Example 3n 2 9n because 3n S 3n2S 4n V n22 c13c24n02 1 4 Questions 53n29n2 0 Is 62n n2 92 0 Is 4n3 3n2 9n2 Property of Order Transitive ffn 0gn and 07 0hn then f0 0hn ffn 0gn and 07 0hn then f0 0hn ffn 9gn and 07 90707 then f0 90707 Reflexive f0 0fn fn Qfn fn 9fn Symmetric fn 9gn iffgn 9fn fn 0gn iffgn Qfn 16 The Importance of Order Notation Algorithm 1 Algorithm 2 Algorithm 3 Algorithm 4 Algorithm 5 2n Frequency 33n 46nlogn 13n2 34n3 count n10 lt 1 sec lt 1 sec lt 1 sec lt 1 sec lt 1 sec n10000 lt 1 sec 6 sec 22 min 39 days 4x1014 centuries where n is the size of the instance For instance bubble sort takes 6n2 where n is the total number of elements to be sorted 17 Complexity Classes log n n linear time log Polynomial time easy or tractable n2 n3 2n Exponential time hard or intractable n For example if algorithm A has frequency count 33n100 which is en and algorithm B has frequency count 46n2 which is also 6n then we say that they are in the same complexity class Running Time 0 Most algorithms transform input objects into output objects The running time of an algorithm typically grows with the input size although it may also vary for different inputs of the same size We will study the relationship between the running time of an algorithm and the size of its input Example suppose a sorting algorithm has complexity 9nlog2n If it takes 100 units for a list of length 64 how long it will take for a list of length 512 64 log264 100 units 512 log2512 x units so x 512 x 9 x100 64 x 6 1200 units 19 Questions A search algorithm s complexity is 9log2n If it takes 50 time units for a list of length 32 how long would we expect it to take for a list of length 1024 Suppose an algorithm with complexity 9n3 takes 10 minutes for a problem with input size 100 What size problem would we expect to be able to solve in 270 minutes 20 Analysis of Algorithms We will show you best case and worst case analysis with the following example The groblem sort n elements into nondecreasing order Solution insertion sort Idea insert the ith element into a sorted array of length il by looking at numbers one at a time for all igt1 21 Best Case Worst Case Analysis public static void insertionSortint a for int i1 iltalength i int current ai int j i l while jgtOampampajgtcurrent ajlaj ajl current Best Case Worst Case Analysis The inner loop will be skipped when the input is sorted Best case performance is 6n or On Worst case performance is 9n2 or Onz The running time of insertion sort is between On to Onz or we can say that the running time is bound to Onz However it s improper to say that the running time of insertion sort is 9n2 since it can run with On when the input is sorted 23 Average Case Analysis The problem finding the value x in array a of n elements Solution sequential search public static int sSearchint a int x for int i0 iltalength i if aix return i return 1 2 4 Average Case Analysis 1 Assume x is in the array and assume equal probability for x being at any location then probxkth Vn VlskSn If xkth of key comparisons k so An Vn 1 Vn 2 Vn n Vn 12n n1 2 about half of the array is searched 2 Average Case Analysis Ifx may not be in the array assume probx in arrayp so probxkthp Vn probx not in array1 p and it takes n comparisons to know that x is not in the array so An p Vn 12n 1 p n n 1p2 p2 if p1 An n12 as calculated in case 1 if pV2 An n about of the array is searched Algorithm Analysis Best case is not representative Average case is more descriptive but complicated to calculate involves considering all possible instances assumptions and probabilities So we emphasize on worst case analysis Theoretical Approach There are two ways to compare algorithms theoretical approach and experimental approach Theoretical Approach find the amount of time needed for each algorithm using frequency count every statement vs key comparisons based on the size of input Example The traveling salesman problem TSP Given a set of cities and the cost function for every pair of two cities find a tour with minimum cost where a tour is a directed cycle starting from city i visiting every other cities exactly once and returning to i straightforward solution n with dynamic programming nZZn 28 Experimental Approach Experimental Approach code the algorithm test the program on a computer with different instances and record the actual time spent in each execution After performing several experiments on many different test inputs of various sizes we can visualize the results by plotting the performance of each run of the algorithm as a point with xcoordinate equal to the input size n and ycoordinate equal to the running time t See the following picture spuooes uonnos e 196 0 sum e eJeAV OZ 9L 0L Experimental Approach 0 quot r quot distributed Number of robots Theoretical vs Experimental Theoretical analysis allows us to evaluate the speed of an algorithm independent of the hardwaresoftware environment too complicated for averagecase analysis in most applications Experimental analysis Experiments can be done only on a limited set of test inputs so they may not be indicative of the running time on other inputs not included in the experiment Complements traditional theoretical analysis Mathematical Background Definition logbx y if by x for bgt1 In other words y is the power to which b must be raised in order to get x logb is a strictly increasing function so if x1ltx2 then logb x1 lt logb x2 logb is a onetoone function so if logb x1 logb x2 then x1x2 logb 1 O Vb logb xa a logbx Mathematical Background logbx1 x2 logb x1 logb x2 xllogb x2 leogb x1 To convert from one base to another logblx M so 9Iog2n 9Iog100n 10gb2 b1 nn1 Sum of consecutive integers 1211 T k I ak11 Geometric sums Za 1 i0 a Note Iog2 lg logen Exercise Verify whether each of the following pairs of functions in the same complexity class If so justify your answer Otherwise rank them by order of growth from low to high Note that two functions fn and gn are in the same class if and only if nf gh l a n1 n 2n ZnZ c Z39g n dn1Ign 25 34 Exercise Consider the following algorithm a find the total frequency count for all statements in CountSort b apply this algorithm to sort the list 60 35 81 98 14 47 Procedure CountSort AOn l for i 6 O to n l do Counti lt O for i 6 O to n 2 do for j il to n l do if AiltAj Count j 6 Countj 1 else Counti Counti l for i 6 O to n l do SCounti lt Ai return S 33 Exercise Verify state true or false the following equations Justify your answer a 2n1 3n1 93n b x10n27n 9n2 C n1001 n n 0n1001 d gn Qngn 36

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

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

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

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

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

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.