Spring 2017

# assignments

due Thu Jan 26

## getting started

• Make sure you can log into this site. If you aren't on my roster yet, email me at mahoney@marlboro.edu .
• Read the "Introduction" chapter in Problem Solving with Algorithms and Data Structures, which reviews python.
• Use the Fraction class as described in the text to find exactly $$\sum_{n=1}^{100}\frac{1}{n^2}$$ . (Anything interesting about that number? Hint: multiply by six and take the square root.)
• As one more python coding practice, find the ratio of consecutive Fibonnaci numbers for large n.
• bonus: Make a plot of n vs Fib[n] , fit to a curve of the form $$y = b x^a$$ , and discuss.
due Thu Feb 2

## analysis and "big-O" notation

• Read the Analysis chapter of our textbook.
• To give you some practice making a plot (I suggest IPython as discussed, but you can use any tool you like, as long as you submit a plot as part of your homework) and to think about the O() notion :
• Suppose the number of steps for two algorithms are $$f(n) = 10 n + 0.1 n \log(n)$$ and $$g(n) = 0.01 n^2$$.
• Plot these functions.
• What are their O() behaviors?
• Which algorithm is faster?
• A sorting algorithm takes 1 second to sort 1000 items. About how long do you think it will take to do 10,000 items if
• the algorithm is O(n**2)
• the algorithm is O(n log(n))
• Consider the problem of implementing is_substring(a,b) which is True if and only if a which has m characters is a substring of b which has n characters . For example, if a="is" and b="My name is Jim.", then the answer to is_substring(a,b) is True. On the other hand, is_substring("one", "alpha beta gamma"), then it returns False.
• If the only operation you can preform is comparing characters(i.e. a[i]==b[j]), invent an algorithm that implements this algorithm. Any algorithm will do - it does not have to be the most efficient.
• Describe what you think the O() behavior of your algorithm is, in terms of m and n.
• Implement and test your algorithm.
• Measure the time it takes your code to run on random strings of varying length, and create a plot that explicitly shows the runtime for some choices of n and m.
• Repeat the previous numerical experiment using Python's built-in operation "a in b" which also returns True or False. (This will run very fast for most strings - you can time it by putting in a large loop to do it many times, then dividing the time for the whole loop by the number of times through the loop. Or check out python's "timeit" library.)
• What do you think is the O() behavior of Python's "a in b" operation?
• Discuss what you think are sorts of strings a and b give the best, worst, and average behavior of your is_substring algorithm. What do you think the O() behaviors are for these cases?
due Thu Feb 9

• Read the Data Structures chapter in the text, particularly the Stack, Queue, and LinkedList parts.
• Implement and test a doubly-linked list in python which can serve as both a stack and a queue. Your API should include at least methods for __str__, push, pop (i.e. the stack API), enqueue and dequeue (i.e. the queue API), reverse, nth (i.e. return the n'th element of the list), and a way to insert a new element into the list.
• Describe the expected O() behavior of each method. Measure at least one with a numerical experiment to verify that it does have the O() behavior you expect.
due Thu Feb 23

## recursion

• Write a program to recursively draw the Sierpinski triangle. (Hint: the python turtle can do this, using its fillcolor, begin_fill, and end_fill methods, and noticing that "erasing" can be the same as "filling white".)
• Pascal's Triangle is a famous array of binomial coefficients. (Google it if you are unfamiliar). Each term can be determined recursively from two smaller ones. Write a program to print out n lines of these coefficients. (Coding exercise 13 in the text.)
• Read the descriptions of coding exercises 14 (knapsack problem) and 15 (string edit distance). For one of these two, implement an algorithm using memoization. (These can also be done with dynamic programming, but I'm not requiring that. Both of these are well studied, so if you don't see how to proceed without help, google to find a discussion. If so, quote your sources.) Discuss briefly the O() behavior of your approach, and the brute force O() behavior (i.e. without memoization).
due Thu Mar 2

## searching

• Read the sequential, binary, and hashing parts of the Searching chapter in the text. (We're doing sorting next, so continue on into that if time allows.)
• Write and test functions that do sequential and binary search on an ordered list of random integers, and show that binary is much faster for big lists, at least waving your hands at seeing the O(n) vs O(log n) difference. (That means I want you to demonstrate what's going on but am not requiring lots of data with graphs and curve fitting and all that.) You can use the textbook code (if so quote your sources), but make sure you understand what's going on.
• Write and test a program that stores strings in a hash table. All the details are up to you, including the choice of a hash function and how to handle collisions. Do explain what's going on, and what the pros and cons are of your choices. Again, you can use code from the textbook - or parts of their code - but if so quote your sources and make sure you understand it.
• Coming soon : a midterm numerical sorting project, due right before spring break. (You can work on this over break if you so choose.) Details coming.
due Fri Mar 10

## midterm sorting project

• Choose two sorting algorithms to implement, test, analyze, and compare. Any of the ones in the text or that we've discussed are fair game. If you want to do a different one, check with me.
• For each, your mission is to
• Explain how it works - enough to convince me you understand it. Also explain what its O() behavior should be on random lists, and why. Discuss when (if ever) this algorithm might be an appropriate choice.
• Implement it.
• Test it, i.e. show it does sort lists successfully.
• Measure with numerical experiments the run time or number of steps it takes when sorting lists of random numbers of (at least) length 1e1, 1e3, 1e5, 1e7. Show explicitly with a graph that it has the O() behavior you expect.