Assignment: Introduction to the Theory of Computation
Note that this is an assignment and can be submitted in groups. In fact, it is highly encouraged. This is long and designed for a group. But, keep in mind that if you divide the problems up and each person only does their share, you will be in big trouble during the midterm and final exams, when something similar comes up and you have no idea how to solve it. Do yourself a big favour and actively participate in the development of solutions to all problems.
Being aware of the fact that you have an exam in the middle your allotted time for this assignment, we subtracted 1 problem from the usual load (of 5 problems for each assignment). Still, we strongly encourage you not to postpone this to a point that you will stress yourself over finishing it in time for the deadline. Keep in mind that we cannot grant extensions. According to the rules of "arts and science", we cannot change the due date of an assignment unless it is put to a vote in all 3 classes, which is practically impossibility.
1. Suppose we are given n coins, all of which are identical, except one which is a counterfeit. Further, assume that the counterfeit coin has a different weight compared to the genuine coins. Consider the problem of determining which of the coins is the counterfeit, by using a balance scale. In a single weighing, we are allowed to place some coins on one side and some on the other, and compare the weights. There are 3 possible results: the scale balances, the left side is heavier, or the right side is heavier. We are interested in solving the problem using the fewest number of weighings (imagine you have to pay per weighing and you are trying to spend the least amount of money on this).
(a) For this part, assume that you know (as a fact) that the counterfeit coin is heavier than a genuine coin. Propose a divide and conquer algorithm that would find the counterfeit coin with the minimum possible number of weighings.
(b) Write a recurrence relation for the function C(n) that determines how many weighings your algorithm performs for an instance of size n (that is when the total number of coins is n), and then provide a closed form answer for the recurrence.
Note: we are not after the running time. we are after the number of times you need to use the scale, so we are not looking for an approximate answer (big-O) here. We are looking for an exact answer. But, keep in mind that this exact answer refers to the worst-case scenario for the number of weighings the algorithm requires. You don't have to prove your closed form, but show your work on how you got the answer.
(c) Repeat part (a), but now with the assumption that you don't know whether the counterfeit coin is heavier or lighter than the genuine coins. Think carefully about your base case. It may be tempting to go with a simple variation of your answer from (a) for this. Resist the temptation, because there is a better algorithm.
(d) Similar to part (b), write a recurrence relation for the function C(n) that determines how many weighings your algorithm from (c) performs for an instance of size n, and then provide a closed form answer for the recurrence.
For simplicity, assume n = 2k (is a power of 2) for parts (a) and (b) and assume n = 3k for parts (c) and (d). Note that this is also giving you a hint at what the algorithms should look like. Think about the hint. Present your algorithms in a simple pseudo code style (as in the style of the other algorithms given to you in this assignment, and also the algorithms you have in your course notes).
2. Consider the following pseudo code for a function Hop, where the input n ≥ 1 is an integer. We are interested in understanding what the function will print. As you can see there are 4 different print statements in the pseudo code and the code prints through these statements. For each of the strings "eeny", "meeny", "miny", and "moe" (hmmmm!), we would like to know how many times the string is printed if a call is made to Hop(n), for all n. So, again, we are interested in an exact number of printed statements and not the runtime or its asymptotic complexity. As a programmer, you may be interested in measuring things other than execution time about your program: for example, memory consumption.
There are several ways of doing this. You can solve this problem one string at a time, ignoring the rest of the print statements. That is a valid solution. Or, you can be a little smarter about it, and do less recurrence- solving type of work. Let's do that! For the purposes of this problem, you may assume that every n is a (non-negative) power of 2.
Hop(n) {
1 print("eeny")
2 if (n == 1) { return }
3 for (i = 1 to i ≤ n) {
4 print("meeny")
5 if (i is even) {
6 print("miny") 7 }
8 if (i == |n/3|) {
9 Hop(n/2)
10 print("moe")
11 } else if (i == |2n/3|) {
12 Hop(n/2)
13 print("moe") 14 }
15 }
}
(a) Write a recursive function definition for the function E(n), where E(n) stands for the number of times "eeny" is printed when we call Hop(n).
(b) Give a closed-form for E(n). You don't have to prove anything, but show your work. The closed-form answer cannot drop from the sky.
(c) Let O(n) stand for the number of times "moe" is printed when we call Hop(n). Provide and equality that defines O(n) based on E(n). Justify your answer.
(d) Write a recursive function definition for the function M (n), where M (n) stands for the number of times "meeny" is printed when we call Hop(n).
(e) Give a closed-form for M (n). You don't have to prove anything, but show your work. The closed-form answer cannot drop from the sky.
(f) Let I(n) stand for the number of times "miny" is printed when we call Hop(n). Provide an equality that defines I(n) based on M (n). Justify your answer.
This problem is much easier than it seems. If you feel a bit lost, then try running the code (carefully so that you don't miss anything) over a few small inputs (such as 1, 2, . . . ) so that you get a sense of how things are working, and have a few concrete numbers to test your answers on after you are done. Just be careful when you count things, and about what your base cases are in each case. Keep in mind that the point of doing (c) and (f) is not to compute these in the same manner (through solving a recurrence) as (a) and (d). But, to use the code structure to relate these two numbers together using simple expressions.
3. Consider an array A with integer elements. The following algorithm recursively finds and returns the smallest element in A[b . . . e].
Min(A, b, e)
1 If (b = e)
2 return A[b] 3 m = [(b + e)/2]
4 x = Min(A, b, m)
5 y = Min(A, m + 1, e)
6 If (x < y)
7 return x
8 else
9 return y
(a) Write the appropriate precondition and postcondition that specify the correctness of this function.
(b) Prove that the function is correct by showing that your specification from part (a) is inductive (which is not the same as asking for a complete induction proof of the correctness statement).
4. For two strings u, v, we say that v = uR if string v is the reverse of the string u. Formally,
|u| = |v| ∧ ∀ 0 ≤ i < |u|, u[i] = v[|u| - 1 - i]
where |u| stands for the length of string u, and u[i] is referring to the character that is in the ith position of the string (assuming that the positions start from 0 and go to |u| - 1, similar to arrays).
For example, abcde = (edcba)R. Also, if u = abcde, then |u| = 5 and u[3] = d. Consider the algorithm below that reverses a string u ∈ Σ∗:
algorithm REV(u)
2 l := |u|
3 if l ≤ 1
4 return u
6 m := l div 2
7 v := REV(u[0 . . . m - 1])
8 w := REV(u[m . . . |u| - 1])
9 return wv
where u[i . . . j] is the substring of u from position i to position j (both inclusive). We also assume that strings are indexed from 0 to the length of the string. The goal is to prove that algorithm REV correctly reverses a string.
(a) Write pre and post conditions for REV .
(b) Prove that REV is correct by proving that your specification from (a) is inductive (which is not the same as asking for a complete induction proof of the correctness statement).
Hint: be careful with part (b). You may find yourself using a fact in your proof that needs a proof. You may want to prove that fact as a separate lemma.
Note: the following problem is extra. You can skip it and only do the 5 problems above and get a full mark on your assignment. So, this is not officially part of your assignment 2. But, if you do it, any extra marks you gain will count towards your final grade. For example, if you get a full mark on assignment 2 and do B2 as well, then the extra 10 points will get you approximately an extra 1.36 mark towards your final course grade. Think of this as a way for you to do more work to compensate for some lost mark from somewhere else.
There is a catch. This problem will be marked harshly. You either have a perfect solution and get the full 10 points, or you make a mistake somewhere (no matter how small it is) and get nothing (i.e. zero). This only applies to the marking of B1. Since this is a bonus problem, we will demand perfection. Also, bonus problems should not be discussed on Piazza or during the office hours or the tutorials. You should do this on your own (i.e. within your group).
(B2) Given a sorted array of distinct integers (i.e. no two different array cells hold the same value), we would like to find out whether there is an index i for which A[i] = i. Assume indices start from 0.
(a) Give a divide-and-conquer algorithm that runs in time O(log n). You do not need to justify the runtime for us. Just convince yourself that your algorithm is fast enough.
(b) Prove that your algorithm is correct by providing the relevant correctness specification for it and proving that that specification is inductive.