The Final Proof

Well, after a few well spent hours trying to figure out the complete proof for the algorithm in the previous post, I've come up with a solution which seems correct to me (and I hope it actually is). The way I went about solving was writing a rough sketch of the proof with all the main ideas and then going through the course notes to figure out how to make it formal.

So, here's the final proof:

Collecting misplaced bits

I was slightly incorrect with my last code. According to the example posted by Danny on Piazza (which is a really helpful discussion board), I've managed to fix my code.

Here's the updated version:
   binSearch(x, A):
       b = 0
       e = length(A) - 1
       while b <= e:
            m = (b+e) // 2
            if A[m] <= x:
                b = m + 1
            else:
                e = m - 1
       return e

I've traced it with quite a few examples and also tried running the code in Java/Python and it satisfies every condition.

Since the assignment still has a few hours before its due, I can't really post how I went about finding my solution.But I'll post a few more posts regarding how I went about actually proving my algorithm.

Connecting bits together to form pieces

So, after a good hour of reading (also included the trip to subway to get a sandwich) through the lecture slides and the course notes, I understand what the question is asking and I arrived at a probable solution. So, far it seems to be correct but I can't be totally sure until I write a proof to backup my algorithm.

Here's the code:
    binSearch(x, A):
        b = 0
        e = length(A) - 1  # e = n - 1
        while b <= e:
            m = (b+e) // 2
            if A[m] >= x:
                e = m - 1
            else:
                b = m + 1
        if A[b] == x:
            return b
        else:
            return -1

I've traced the code using a few examples and it seems to work (also the code is almost exactly the same as the lecture slides, just minor changes). But that isn't enough to prove correctness, and now I'm going to try to come up with a proof. And when I do come up with a proof , I'll post how I went about it.

Breaking down into bits

So, I'm working on the final assignment of the semester. And like always, its challenging but not to the point of flipping tables. Right now, I'm stuck on the 4th question of the assignment (I haven't completed the others, its just that I'm working on this problem for now).
 The question asks me to design an algorithm for binary search with the pre-condition being that the list has elements comparable with type of 'x', and the list at least has 1 element. The algorithm is supposed to return the index of 'x' in the list or -1 if 'x' is not in the list. I'm brainstorming ideas on how to do it. The hint suggests that I follow the approach from lecture notes and develop the code using pictures or something similar.
I don't really follow that approach and I guess, I need to go over the slides more than a few times to get what's going on. Hopefully, I'll be able to crack this problem soon.

And I think, this would problem would be my mathematical proof post (the following posts would contain the mathematical/proof part).

Proving algorithms

So, we have started proving the correctness of algorithms and devising algorithms following some conditions.

As far as proving the correctness of algorithms goes, I like the fact that we can prove that our algorithm works by following certain steps. The reason why I like that is if I can prove that my algorithm works, then I don't need to write test cases to convince someone that my code works fine.

But what interests me more is devising an algorithm by following the given conditions that our algorithm needs to satisfy and get to a working solution. It prevents us from making mistakes like being off by 1 which I tend to make sometimes.

I'm looking forward to seeing how this technique could turn to be more helpful when I see some more examples. And I feel bad that I tend to forget to post in this slog every week.

Assigning of Timings

So,  after the end of the first midterm wave, the second one awaits. But during that time we have an assignment due for 236. I find this assignment really interesting. Especially the first question. The way things get linked always excite me. While finding the solution for it, thought I'm not done completely, I found that the algorithm behaves very closely to a fibonacci series. I couldn't see it when I read the problem a first few times but after trying for a few hours and working with a friend (we worked separately, but were at the same location), we both arrived at the same solution which he said is what he saw on Danny's board. So, I guess we are on the right path.

I forgot to post on this blog for a week I guess, and I feel sorry for that. As the requirements of this slog state that we are supposed to post a mathematical/logical proof/problem solution, I will do that soon enough when I encounter some really interesting problem and hopefully, be able to derive the solution.

The Time Has Come

So, after a well formed midterm, which increased my grasp on proofs, we have started time analysis.
I don't like time analysis as such and I'd have to work on it so that I can keep up with the course. So far, I've been able to do that.

Complete induction make more sense to me now. In this week's tutorial, we had to prove a lower bound using mathematical induction. I wasn't able to do that because it didn't occur to me how to go from the nth term to n+1th term. I plan to work on trying to use mathematical induction to solve the time analysis questions so that it increases my understanding of both mathematical induction and time analysis.