MIT OpenCourseWare http ocw mit edu 6 006 Introduction to Algorithms Spring 2008 For information about citing these materials or our Terms of Use visit http ocw mit edu terms Introduction to Algorithms 6 006 Massachusetts Institute of Technology Professors Srini Devadas and Erik Demaine Feb 7 2007 Handout 3 Problem Set 1 This problem set is due Thursday February 21 at 11 59PM Solutions should be turned in through the course website in PDF form using LATEX or scanned handwritten solutions A template for writing up solutions in LATEX is available on the course website Remember your goal is to communicate Full credit will be given only to the correct solution which is described clearly Convoluted and obtuse descriptions might receive low marks even when they are correct Also aim for concise solutions as it will save you time spent on writeups and also help you conceptualize the key idea of the problem Exercises are for extra practice and should not be turned in Exercises Exercise 2 3 6 page 37 from CLRS Exercise 3 1 3 page 50 from CLRS Exercise 3 1 4 page 50 from CLRS 1 11 points Asymptotic Growth Rank the following functions by increasing order of growth that is nd an arrangement g1 g2 g11 of the functions satisfying g1 O g2 g2 O g3 g10 O g11 Partition your list into equivalence classes such that f n and g n are in the same class if and only if f n g n All the logs are in base 2 n 100 1 n 3n n100 22n 10100 n 1 5 4n 3 n n log n log n 2 19 points Binary Search In Problem Solving With Algorithms And Data Structures Using Python by Miller and Ranum two examples are given of a binary search algorithm Both functions take a sorted list of numbers alist and a query item and return true if and only if 2 Handout 3 Problem Set 1 item alist The rst version is iterative using a loop within a single function call and the second is recursive calling itself with di erent arguments Both versions can be found on the last page of this problem set Let n len alist a 6 points What is the runtime of the iterative version in terms of n and why Be sure to state a recurrence relation and solve it b 8 points What is the runtime of the recursive version in terms of n and why Be sure to state a recurrence relation and solve it c 5 points Explain how you might x the recursive version so that it has the same asymptotic running time as the iterative version but is still recursive 3 30 points Set Intersection Python has a built in set data structure A set is a collection of elements without repetition In an interactive Python session type the following to create an empty set s set To nd out what operations are available on sets type dir s Some fundamental operations include add remove and contains and len Note that contains and len are more commonly called with the syntax element in set and len set All four of these operations run in constant time i e O 1 time For this problem we will be analyzing the runtime of s intersection t that takes two sets s and t and returns a new set with all the elements that occur in both s and t We will then use intersection in a new version of the Document Distance code from the rst two lectures a 5 points Using notation make a conjecture for the asymptotic running time of s intersection t in terms of the sizes of the sets s and t Justify your conjecture HINT Think about the fundamental operations above b 10 points Determine experimentally the running time of s intersection t by running it with di erent sized sets Fill in the following chart Include in your PDF submission a snippet of code that determines one of the entries in the chart Note there are a number of ways to time code You can use the timeit mod ule see http www diveintopython org performance tuning timeit html Handout 3 Problem Set 1 3 for a good description of how to use it Alternatively if you have ipython in stalled see http ipython scipy org you can use their builtin timeit com mand which is more user friendly time in s s 103 s 104 s 105 s 106 t 103 t 104 t 105 t 106 c 5 points Give an approximate formula for asymptotic running time of s intersection t based on your experiments How does this compare with your conjecture in part a If the results di er from your conjecture make a new conjecture about the algorithm used d 10 points In the Document Distance problem from the rst two lectures we compared two documents by counting the words in each treating theses counts as vectors and computing the angle between these two vectors For this problem we will change the Document Distance code to use a new metric Now we will only care about words that show up in both documents and we will ignore the contributions of words that only show up in one document Download ps1 py docdist7 py and test ps1 py from the class website docdist7 py is mostly the same as docdist6 py seen in class however it does not implement vector angle or inner product instead it imports those functions from ps1 py Currently ps1 py contains code copied straight from docdist6 py but you will need to modify this code to implement the new metric Modify inner product to take a third argument domain which will be a set containing the words in both texts Modify the code so that it only increases sum if the word is in domain Don t forget to change the documentation string at the top Modify vector angle so that it creates sets of the words in both L1 and L2 takes their intersection and uses that intersection when calling inner product Again don t forget to change the docstring at the top Run test ps1 py to make sure your modi ed code works The same test suite will be run when you submit ps1 py to the class website Does your code take signi cantly longer with the new metric Why or why not Submit ps1 py on the class website All code submitted for this class will be checked for accuracy asymptotic e ciency and clarity 4 Handout 3 Problem Set 1 Iterative Version def binarySearch alist item first 0 last len alist 1 found False while first last and not found midpoint first last 2 if alist midpoint item found True else if item alist midpoint last midpoint 1 else first midpoint 1 return found Recursive Version def binarySearch alist item if len alist 0 return False else midpoint len alist 2 if alist midpoint item return True else if item alist midpoint return binarySearch alist midpoint item else return binarySearch alist midpoint 1 item
View Full Document
Unlocking...