week 7

Thankfully, q4 in the assignment does not deal with complexity, and is on correctness, which I find much easier.  I'm finding q1 to be difficult, everytime that I think I'm close to coming up with a formula, I end up stuck (and frustrated).  I'm also finding it difficult to express q3 in the assignment without using the stats combination formula, but I think that its fine that I use it, even if it isn't the model solution.  For q2, I think I have an answer, but it seems almost too easy.  We'll just have to wait and see...

As I mentioned, program correctness looks to be much easier (at least for now).  Rather than having to find induction formulas, or manoeuvre through some tricky proof in complexity, its more like providing an analysis of an already complete algorithm.

week 6

Right now I'm currently busy with assignment #2.  In general, I'm finding divide and conquer recurrences kind of tricky.  Proving a conjecture based upon a more simply defined function such as Fibonacci sequence looked to be much more straightforward.  Trying to deal with complexity, as well as the ceilings and floors looks to add a new degree of difficulty.  But I suppose its a matter of working through it.  The last question on the assignment looks tough, and deals with a divide and conquer recurrence.  I imagine it will be a lot of work to tackle proving a tight asymptotic bound.  I'll write up another post later in the week, after I really get into the assignment.  

after test 1

Well, I found out that the reason q3 was so troubling for me was because of an error in my math.  It was a simple arithmetical error that gave me -phi for n3/n4.  And as a result, I thought that n4 was negative.  I now see (and it makes perfect sense) that the cycle of natural numbers will proceed indefinitely, and that a contradiction can be found by trying to find a smallest number.  I guess the only thing that can be learned from this is to be more careful, and double check all my results.  Also, more time (and help sought) for the next assignment would be advisable.

I had just went through test 1 last week, and found it to be fair, yet challenging.  My last question, was where, if I remember correctly, I had to show that a set of natural numbers {1, ..., n}, which was missing either 1 or 2, or both, had 3*2^(n-2) subsets.  I initially took the wrong approach, where, for some reason, I tried to directly prove this.  I realized, with 5 minutes left, that this question was exactly like the ones seen in the PS and assignment.  I didn't need to show that it works for P(n), but only show that P(n)=>P(n+1).  I will probably get part marks for this, but again, lesson learned.  Hopefully, or eventually, I'll get quicker at seeing what kind of problem is in front of me, and then taking the right approach :).