**NOTE: You may do this assignment on paper or on your computer, whichever's easier. I would like TWO copies on paper turned in, one for me and one for the peer grader. If you do your pset electronically, please ALSO email me that portion. Peer graders will be assigned on Tuesday (9/28) in class.**

## Answers to questions I've been asked

- When answering a scheme coding problem on a pset, it is fine (nay, even encouraged) to make use of an available scheme interpreter.
See ResourcesForScheme for resources.

- O, Omega, Theta are upper, lower, and tight bounds on a function. This has nothing to do with best/worst/average case analysis. The best/worst/average case running time of an algorithm is described by a function. A function can have an upper or lower bound (or both).
*k*is a parameter you're going to be setting, so do not assume that it is constant in your analysis. When you get to the value-setting question, your goal is to beat the running time of merge sort, i.e., not to make your new, improved algorithm do worse than merge sort by itself. If you wish, you may give the constant factor on merge sort a name. This is particularly encouraged if it figures into setting the value of k.See ReadingRoom/OrdersOfGrowth for resources.

The backwards E means

*there exists*. The upside down A means*for all*or*for each*or*for every*. The curvy e-thing means*is in*or*is a member of*, which in the specific case of this problem can be treated as*=*.I thought that

*lg*meant*log_2_*in this particular author's notation, but additional evidence leads me to believe that I might be mistaken. You can make that assumption or any other reasonable assumption.See ReadingRoom/OrdersOfGrowth for resources.

- Assume a naive implementation of open hashing, i.e., find the next available bin.
An FSM may have multiple final (accepting) states. The start state

*may*be an accepting state.The answers to these questions are supposed to be

*deterministic*FSMs. I'd rather see a nondeterministic FSM than none at all, but the fully correct answers involve DFSMs.The correct answer to each of these five sub-questions accepts all strings in the given set and

*only*strings in the given set. For example, 5.a. is a DFSM that accepts ba, babbba, and bbbbbabababbbba, but not*abba*or*babaa*.See ReadingRoom/FiniteStateMachines for resources

## The pset

- Scheme higher order procedure hacking
Write a scheme procedure

`make-multiplier`that takes one number as an argument and returns a procedure that multiplies*its*argument by the original number. For example,> (define triple (make-multiplier 3)) > (triple 6) 18 > (triple 4.5) 13.5 > ((make-multiplier 4) 5) 20

Write a scheme procedure,

`apply-to-5`, that takes one argument and returns the result of applying that argument to 5. For example,> (apply-to-5 double) 10 > (apply-to-5 triple) 15 > (apply-to-5 -) -5 > (apply-to-5 list) (5) > (apply-to-5 make-multiplier) <#procedure> > (apply-to-5 (lambda (x) x)) 5

What should the result of

`(apply-to-5 (apply-to-5 make-multiplier))`be?

- Sort analysis
Consider an optimization of

**merge sort**in which the original list of length n is divided into disjoint sublists of length k, these lists are sorted using**insertion sort**, and then the n/k sublists of length k are merged (pairwise, successively, as in merge-sort) until the final sorted list of length n is achieved.- How many steps will it take to sort each of the sublists of length k? Give your answer in asymptotic (theta, like big-Oh) notation. Indicate whether your analysis is best, worst, or average case.
How many steps will it take to sort

*all*of the sublists of length k? Again, use theta and indicate what you're analyzing.- Once the n/k sublists of length k are individually sorted, how long will it take to merge them all back together? Again, theta and case....
- Given your analysis and what you know about merge sort, how should we choose k (as a function of n) so that this algorithm is asymptotically (theta-notation) comparable to merge sort?
- Merge sort typically has a higher constant factor on its (asymptotic) running time than insertion sort. How could this be taken into account in selecting k?

- Asymptotic Notation
*Ugh. These are really ugly on the wiki. I will hand them out in class and hopefully someone will take pity and format them somewhere so that they're web accessible. Or teach me (or MoinMoin) MathML. My ascii skills aren't up to Mel's. Sorry.***This problem has been printed on dead trees, and is lying in a stack outside of AC 312. It was also distributed in class on 9/24**(What is the difference between lg and log? I've seen some notes that say lg = log_2, but in other places on the assignment the base is explicitely called out, so I'm confused. Is log = log_10, unless another base is specified? Is lg = log_2? --

*DrewHarry*Sorry....Any reasonable assumption that you make is fine. I believe that this came up in class on Friday and I answered it then: In these problems, the convention of

*this*author is that log is base 10; lg is base 2. --*las*) - Hashing
Draw a picture of a hash table with 8 buckets using

**closed hashing**and the hashing function*mod 8*after inserting the following data: 1, 3, 9, 5, 18, 41Draw a picture of a hash table with 8 buckets using naive

**open hashing**and the hashing function*mod 8*after inserting the following data: 1, 3, 9, 5, 18, 41Leaving the pun aside, would the hash function

*mod n*be a clever choice if we want to build a hashtable of Olin roommate pairs (i.e., using your room numbers as keys and storing two student data at each node? If so, for what value(s) of n and why? If not, suggest a better hash function.

- Finite State Automata
*Note: Finite state automata are the topic of the Friday 9/24 class. It would not be surprising if you could not complete this problem prior to that session.*Draw state diagrams for deterministic finite automata accepting each of the following languages:{

*w*in {*a*,*b*}* : each*a*in*w*is immediately preceded by a*b*}{

*w*in {*a*,*b*}* :*w*has*abab*as a substring}{

*w*in {*a*,*b*}* :*w*has neither*aa*nor*bb*as a substring }{

*w*in {*a*,*b*}* :*w*has an odd number of*a*s and an even number of*b*s}{

*w*in {*a*,*b*}* :*w*has both*ab*and*ba*as substrings}

NB: These problems are often based on or taken directly from some of the books we're using in this class. Credits available on request.