Tutorial 5: Applying the Master Theorem

Today I will write about my thinking and problem-solving steps for question 1 of tutorial 5.

Question: A non-empty array A with integer entries has the property that no odd number occurs at a lower index than an even number. Devise a divide-and-conquer algorithm for nding the highest index of an even number element, or -1 if A has no elements that are even numbers. Use the Master Theorem to bound the asymptotic time complexity of your algorithm.

I start by parsing through the question to understand it:

If A has the property that no odd number occurs at a lower index than an even number, then all even numbers are gathered at the front of A, followed by all odd numbers.

I list some examples:

n = 1:  [3], [2]
n = 2: [4, 1], [1, 3], [6, 4]
n = 3: [2, 6, 5], [2, 6, 8], [5, 3, 7]
n = 4: [4, 3, 1, 7]

Now I reason about what the algorithm should roughly look like based on some scratch work with the examples.

If we do the question by brute force, we would simply be checking each element in the array until we reach an odd number. Then the index of the element before the first odd number is the one we want(*). The worse case for this approach is n, when we would have to check every element in the array.

Using the divide-and-conquer process:

We first have to divide the array into smaller pieces. I decide to divide it into two halves from the middle because for now, I don't see any reason to divide it into more than two pieces. Call the first half L1 and the second half L2.

Check the middle element.
(I): If it's odd, we know that all even numbers come before this element, so we recurse on L1.
(II): If it's even, we know that there could potentially be more even numbers in L2, so we recurse on L2.

Now I think about the base case. The least number of elements a non-empty array can have is 1. There are two cases for this array:

Case 1: the element is odd. Then we should return -1 since there are no even numbers in the array. But because we have to think about how the base case relates to recursion, instead of -1, generally we return the index of the element before the first odd number, as metioned above in (*).

Case 2: the element is even. Then we should return the element's index.

So in pseudo-code, we have:
(# A is a non-empty array, b is the beginning index, e is the end index)

evenIndex(A, b, e):                                   
    if b == e:
        if A[b] is odd:                        # case 1
            return b - 1
        else:                                         # case 2
            return b
    else: (b < e)
        mid = floor[(b + e) /2]
        if A[mid] is odd:
            return evenIndex(A, b, mid + 1)                   # corresponding to (I)
        else:
            return evenIndex(A, mid + 1, e)                   # corresponding to (II)

Everything other than the recursion takes constant time, so the tight bound for those parts is big-theta(1). The recursive part of the algorithm takes max{ T[floor(n/2)], T[ceiling(n/2)]}.

So T(n) = { 1                                   if n = 1
                    1 +  T[ceiling(n/2)]     if n > 1}

Then by Master Theorem,
a = 1, b = 2, d = 0.
So a = b^d.

Therefore T(n) = big-theta(log n).
                                                     
                                                                       

A Split Between Mathematical and Complete Induction

I've always thought that if a predicate can be proven with mathematical induction, then it can be proven using complete induction just as easily and vice versa. It turns out I was wrong. Although there is a cycle for believing in well-ordering, mathematical induction, and complete induction as in WO => MI => CI => WO, the cycle is at the top level. At the working level where we have to do the actual proof using induction, sometimes the trasfer between MI <=> CI is not so smooth.

Such is the case for the quiz question in tutorial 3. For a given recurrence, we are supposed to prove using MI that for every positive natural number n, T(n) >= c lg(n), for some positive real constant c. I noticed that in all of the lecture slides about proving big-O or big-Omega, we use CI. The reason is clear to see, since working with floors or ceilings of n over some nautral number means we can use the induction hypothesis to eliminate the floor or ceiling; ceiling(n/k) is less than or equal to n for a large enough n. Then we can break up lg(n/k) to get lg(n). But how about MI? How do we prove that [T(n) >= c lg(n)] => [T(n + 1) >= c lg(n + 1)]? Logarithms do not work well with addition, because it cannot be broken up easily. When I saw the question, I was at a loss. Eventually I couldn't resist the temptation to use the induction hypothesis for CI on n + 1 for a MI proof, which is definitely not the right way to approach it. But hey, I had a limited amount of time on the quiz! It is interesting and useful to discover that choosing the right induction technique paves the way for presenting a clear proof.

The first test

First of all, I'm really thankful that the term test questions looked familiar to me when I first opened the test paper. For some reason, I always have butterflies in my stomach right before a test. The calmness only comes after I start writing the test and discover that: Hey! I don't have a blank out on this question! I can actually do it!

When preparing for the test, I was a bit thrown off by the principle of well-ordering. I can follow the two examples provided on the lecture slides about well-ordering; but if it were up to me, I would have used Mathematical Induction or Complete Induction to prove the claim. Perhaps it's because we have been exposed to MI and CI longer and have done more proofs using these two techniques in tutorials and A1. Or perhaps the idea of somehow re-wording the claim I want to prove so that it becomes related to a subset of natural numbers seems strange to me. Anyhow, it is probably a good idea to get more practice on well-ordering in order to get better at it.

The sample test really helped me focus on what I should study for. Before, I was looking at the closed form of Fibonacci sequence and got very nervous about deriving something similar to phi. But after doing the sample test, I decided to direct more attention to familiarizing myself with the techniques of induction, which turned out to be the core of the term test.

A1 accomplished!

11:59 pm. Somehow it sounds like an omnious foreshadowing that only we, the students, who depend on the minute-hand of the accurate MarkUs clock know about. Having fought an intense battle against that clock last year in CSC165, I am quite pleased to have finished A1 well before its deadline. From what I remember in CSC165, it was not because of procrastination that led my partners and I to race against time, but because we were always unsure of the solutions that we had generated, and thus the urge to change what we have written until the last minute. Having experienced that, I found this first assignment to be much clearer (of course, after leaving myself a good amount of time for discussion and question).

Surprisingly, the inequality question was not as easy as I thought it would be.  When I first looked at the question, I thought of it as just consisting of purely mathematical reasoning that gets from the left side of the equation to the right side. However, getting there is not as simple as 1 + 1. I had to go back to the 165 Big-O section to review the techniques to tackle these inequalities. But even then, there was no elegant way that lets me solve the problem without assuming in some part of the proof that n >= a certain natural number. The following lecture that talked about inequalites cleared my doubt.

Another question that yielded a different type of uncertainty was question 4. I was pretty sure that I was on the right track after discussing with my friends and digging into the hint provided in 4) about using a stronger claim to prove the desired claim. However, the proof just looked longer than it should be because of the large number of cases that it needed to be divided into. Thanks to the professor's office hours and my friend who continued waiting in-line when I had to go to another class, I was assured that sometimes, a proof needs to be a bit longer in order to be convincing.