DOC PREVIEW
MIT 6 006 - Problem Set 1

This preview shows page 1-2 out of 5 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 Feb 7, 2007 Professors Srini Devadas and Erik Demaine 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. Rememb er, 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 write- ups, 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 point s) Asymptotic Growth Rank the following functions by increasing order of growth; that is, find 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 , 3n , n100 ,100 1/n, 22n , 10100n, 3√n , 1/5, 4n , n log n, log(n!). 2. (19 point s) 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 if2 Handout 3: Problem Set 1 item ∈ alist. The first version is iterative (using a loop within a single function call) and the second is recursive (calling itself with different 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 point s) Explain how you might fix the recursive version so that it has the same asymptotic running time as the iterative version (but is still recursive). 3. (30 point s) 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 s et: s = set() To find 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 first 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 different 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.html3 Handout 3: Problem Set 1 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 differ from your conjecture, make a new conjecture about the algorithm used. (d) (10 points) In the Document Distance problem from the first 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 modified code works. The same test suite will be run when you submit ps1.py to the class website. Does your code take significantly 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 efficiency, 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


View Full Document

MIT 6 006 - Problem Set 1

Documents in this Course
Quiz 1

Quiz 1

7 pages

Quiz 2

Quiz 2

12 pages

Quiz 2

Quiz 2

9 pages

Quiz 1

Quiz 1

10 pages

Quiz 2

Quiz 2

11 pages

Quiz 1

Quiz 1

12 pages

Graphs

Graphs

27 pages

Load more
Download Problem Set 1
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Problem Set 1 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Problem Set 1 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?