 [FrontPage] [TitleIndex] [WordIndex]

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.

1. 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.

2. 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.

3. 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.

4. Assume a naive implementation of open hashing, i.e., find the next available bin.
5. 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.

## The pset

1. Scheme higher order procedure hacking
1. 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```
2. 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```
3. What should the result of (apply-to-5 (apply-to-5 make-multiplier)) be?

2. 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.

1. 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.
2. How many steps will it take to sort all of the sublists of length k? Again, use theta and indicate what you're analyzing.

3. 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....
4. 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?
5. 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?
3. 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)

4. Hashing
1. 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, 41

2. Draw 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, 41

3. Leaving 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.

5. 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:

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

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

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

4. { w in {a,b}* : w has an odd number of as and an even number of bs}

5. { 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.

2013-07-17 10:43