You have been hired by Nanosoft. Your boss, Gill Bates, drops by your spacious cubicle sipping a refreshing and stimulating Jolt Cola ("All the sugar, and twice the caffeine!"). Gill begins by reminding you that a decider is a program that takes an input and eventually halts and accepts (says "yes" to its inputs) or rejects (says "no" to its input). For example, a decider for the prime numbers would take a number, perhaps encoded in binary, as input and would eventually halt saying "yes" (it's prime) or "no" (it's not prime).
- "OK, so here's your first task," says Gill. "We have decided to
change our interview process -- we're going to ask
all of our job candidates to see if they
can write a decider which takes as input a string of
0's and determines whether the number of 0's present is a power of 2."
You sigh, realizing that this would have made for a much less stressful interview than you'd had, what with the complete rewrite of the company's "Vasta" operating system you'd had to build... .
"Here's what I need from you," continues Gill. "I need a program which we'll call a Power of Two Decider Tester (POTDT). The POTDT takes as input a program. The POTDT then decides whether P is a legitimate decider for strings whose length is a power of 2. That is, the POTDT eventually halts and says yes if the program it received was a correct submission for this competition and otherwise the POTDT halts and says no. I need this POTDT program written by tomorrow at 6 AM."
Prove to Gill that this cannot be done, not by 6 AM and not EVER! You may use diagrams to help explain your proof, but your proof must be clear, precise, and rigorous. Your submission on this and the following problem will be graded on clarity and precision of explanation.
Here is a link to an example write-up of the proof we did in class, that the blank-tape halting problem is undecidable.
- "Drat!" says Gill upon hearing the news. "OK, then, in that case,
I'd like you to
write a program called a Regularity Checker (RC). The Regularity
Checker takes as input a program P (e.g., a Turing Machine) and it
needs to determine
whether or not the set of strings accepted by P is a
regular language. The RC must always halt with an answer of yes
or no!" Prove to Gill that this too is impossible. Again, you
may use pictures to help you explain your proof, but your proof
must be clear, precise, and rigorous.
Note that if a turing machine runs forever on an input, that input is considered REJECTED for the purposes of defining the language that the TM accepts. This might help!
Note: the idea in both of these problems is similar to the examples we did in which we reached a contradiction by creating a halt-checker out of the program that we hope to prove uncomputable. In this case, you'll want to create a halt-checker from a POTDT and a RC. Keep in mind that you can build any function/program/machine you like in order to coax the POTDT and RC into deciding whether a program P halts on an input w.
For this reason, simply citing Rice's theorem isn't allowed for this problem :-)
Algorithm analysis
Through this part of the assignment, you will be analyzing the running time of algorithms. We will be interested in worst-case analysis. (The best case isn't interesting and the average case is often quite difficult to quantify.) You will need to express the worst-case running time using big-O notation. Finally, make sure to show all of your work in each written problem. Explain each step carefully.
This problem involves finding the big-O running-time analysis of both iterative (looping) and recursive code.
-
What is the big-O running time of this portion of code, in
terms of n? Explain your analysis clearly and carefully.
(Notice how i is increasing!)
for (int i=1 ; i≤n ; i *= 2) for (int j=0 ; j<i ; ++j) // constant time work here -
What is the big-O running time of this portion of code, in
terms of n? Explain your analysis clearly and carefully.
(Notice how j is increasing!)
for (int i=1 ; i≤n ; ++i) for (int j=1 ; j<i ; j *= 2) // constant time work here - Consider a directed graph represented as a prolog list
of edges, with each edge a [source, destination] pair.
For example, G = [ [a,b], [b,a] ] is a two-node
graph, with each node connected to the other.
The reachability problem asks whether it is possible to get from one node to another particular node within a given graph. The following is one possible prolog solution, named reach to this reachability problem:
reach(A,A,_). % any node is reachable from itself % below we ask you to explain what this next line is "saying" reach(A,B,[[X,Y] | R]) :- reach(A,B,R) ; (reach(A,X,R), reach(Y,B,R)).?- reach( b, a, [[a,b],[b,c],[c,d],[d,e],[e,f],[f,g],[g,a]]). Yes ?- reach( b, h, [[a,b],[b,c],[c,d],[d,e],[e,f],[f,g],[g,a]]). No
In this problem we consider the problem of multiplying two n-bit numbers, x and y. For simplicity, we will assume that n is a power of 2. This is generally the case in any real-world computer architecture, but it's also true that relaxing this assumption does not change the results of the analysis.
- Explain briefly why the running time of the standard multiplication algorithm -- the one learned in grade school, but in base 2 instead of base 10 -- has a running time which is O(n^2). Remember that n is the length, in bits, of the two inputs to the multiplication.
-
Professor Dee Videnconker has proposed the following alternative approach to multiplying two n-bit numbers x and y.
Notice that x has n/2 "upper bits" which we'll call "a" and n/2 "lower bits" which we'll call "b". Similarly, dividing y in two parts gives us the upper n/2 bits, which we'll call "c", and the lower n/2 bits, which we'll call "d". So, x = a 2^{n/2} + b and y = c 2^{n/2} + d. What's going on here? Notice that multiplying "a" by 2^{n/2} "shifts" it by n/2 positions. The number "a" by itself is a n/2 bit number. After the multiplication by 2^{n/2}, the bits of "a" have been "promoted" so that we now have a n-bit number in which the first n/2 bits are the bits of "a" and the last n/2 bits are all 0's. Now, adding "b" to this gives us a n-bit number in which the first n/2 bits are "a" and the second n/2 bits are "b". That is, we now have written x in terms of "a" and "b". We do the analogous thing for expressing y in terms of "c" and "d".So, back to Professor Videanconker's algorithm! The algorithm works like this: Divide x into two n/2-bit numbers "a" and "b" and similarly divide y into two n/2 bit-numbers "c" and "d". Now, xy = (2^{n/2}a + b)(2^{n/2}c + d) = 2^{n}ac + 2^{n/2}(ad + bc) + bd. We compute "ab" using a recursive call (now on numbers that are n/2 bits long!) and similarly we compute "ad", "bc", and "bd". After the recursive calls are complete we do the multiplications by 2^{n} and 2^{n/2} followed by some addition.
Notice that multiplying by 2^{k} is just the same as adding k 0's to the end of the number. This can be done in k time steps. Similarly, adding two j-bit numbers can be done in j time steps.
- Write down a recurrence relation for this algorithm.
- Solve the recurrence relation using the recurrence-unwinding method. Show your work in complete detail. Give your running time in big-O notation. Your final answer should be O(n^k) where k is some real number.
- How does the running time compare to the standard algorithm for multiplying two n-bit numbers?
- That wasn't great! To do better,
some fast multiplication circuits use the
following more clever divide-and-conquer algorithm.
Again, divide x and y
in half. Thus, x = a 2^{n/2} + b and y = c 2^{n/2} + d
where
a, b, c, d are n/2-bit numbers.
The product of x and y, call it z, can now be computed
by the following steps:
temp1 = (a+b)(c+d) temp2 = ac temp3 = bd z = temp2 2^{n} + (temp1 - temp2 - temp3) 2^{n/2} + temp3Nothing for you to do here! This is just the description of the algorithm. - Explain why z is in fact the product of x and y.
- Observe that the terms (a+b) and (c+d) may have either n/2 or n/2 + 1 bits each. For simplicity, assume for now that they each have exactly n/2 bits (the case of n/2 + 1 bits isn't hard to deal with, but let's not worry about it here). Notice that the above algorithm performs 3 multiplications of n/2 bit numbers plus some additions and shifts. (Multiplying a binary number by a number of the form 2^k can be accomplished by simply performing k bit shifts to the left! This takes just k units of time.) Now, just write down the recurrence relation (an expression for T(n), including a base case) for this algorithm.
- Find the big-O running time of the divide-and-conquer algorithm by unwinding this recurrence relation and then obtaining a solution. For full credit, be sure to express your final answer as O(n^k) where k is some real number.
- How does this algorithm's running time compare to the running time of the standard O(n^2) algorithm?
This problem provides a chance to exercise your own algorithm-design skills, to estimate the big-O complexity of your algorithm, and then to try out your code to see how quickly it runs in practice on problems of increasing size.
The problem
Wally is unicycling back to Mudd (@ the southwest corner of the map) after spending the
summer in New England (@ the northeast corner). A square grid has been overlaid on the
map, with each cell containing a positive number -- namely, the number of
strawberry-filled DonutMan donuts that Wally will need to consume in order
to have enough energy to pass through that cell.
Your task is to minimize donut consumption. And for this problem specifically, you should write
- a class named Wally in a file named Wally.java
- a method whose signature is
This method should return the minimum number of donuts needed to get from the NE corner of the input map to the SW corner.public static int minDonuts(int[][] map)
The rest is up to you... the algorithm, the software structure (other classes, other methods), and the testing you do.
Example
For example, here is an image of a 5x5 donut-consumption grid and the correct minimum answer. Note that the start cell will be in the final spot in the first row, or
map[0][N-1], and that the destination cell is in the final
spot of the first column, or map[N-1][0], where N is the
length of a side of the square map.
Below it is the path that produced that answer:
The write-up
You should comment your code in order to explain how your algorithm works, as usual.
However, you should also include a comment at the top of your file that includes
- a paragraph on the overall approach you took and the algorithm that resulted
- a sentence or two on how you tested your algorithm
- a sentence or two on the big-O running time of your algorithm, with justification.
- [optional] any modifications you made to speed the code up beyond algorithm design (or otherwise creative modifications you might have made to the code...)
You may cite any results from class to justify your claim to a particular big-O running time, but you may also need to supplement those results with additional analysis of your own.
For uniformity, we ask that everyone define the problem size, N, to be the length of ONE SIDE of the square donut-consumption grid.
Submission
Submit Wally.java in the usual way, under assignment #12.
Scoring
Your solution will receive full correctness credit if it runs in "reasonable" time (under ten seconds on a 6x6 grid) and it works correctly, i.e., it computes the true minimum donut cost. Slow correct solutions will receive almost all of the points (unless they are bogosort-slow). Incorrect solutions, fast or slow, will receive almost no points.
The other half of the credit will be for your algorithm deisgn (not speed, just thoughtfulness), explanation, program design, and commenting.
Extra Credit Options
- The need for speed We will measure the fastest algorithms to determine which has the best real running time for large input sizes. Fame, fortune, or glory (as well as bonus points) are all possibilities for exceptional entries...
- Elegance or eccentricity Unusual and creative extentions in terms of code functionality, formatting, or any other facet you might want to pursue are welcome. Please explain in your top-of-file comment what you've done! Prizes are identical as in the previous option. artistic formatting, poetic Java code, palindromic programs, ASCII images of Wally, ... - the possibilities are endless!