Divide and Conquer

The concept of divide and conquer is part of the backbone in computer science and it's a thought process many of us are starting to adopt as we are exposed to more and more problems dealing with recursion. This school of thought is very handy because it allows us to move away from thinking in big O(n^2) - or even worse!

One neat example we saw in class was how to multiple 2 n-bits. We could just multiply the 2 using the method we do by hand when doing normal multiplication of integers. This means making n copies of n-bit numbers and adding these n-bit numbers n times. Which boils down to big O(n^2) complexity. When it comes to very large n-sized bits, we'll have to leave the machine running and go for lunch to wait for it to finish running. It's just not practical, especially in the sense of encryption as Heap mentioned. RSA has something like 2000 bit encryption and handing these bits doing multiplication using the above method won't work. So divide the problem, do something with the pieces and recombine it. We divided each of the 2 n-bits into roughly half, to end up with 4 n/2-sized bits. Then used Gauss's magical trick of only doing 3 different multiplications (a=3) and after that doing some shifts and adds, which only take big O(n) time. So in the end we have a = 3, b = 2 (break point is 2 because any bit of size 2 can be broken into 1-size bits and doing this multiplication is trivial), and d = 1 since our 'f(n)' being the recombining step only takes 0(n) time. This means we end up with big O(n^1.5) which is way better than O(n^2) for very large numbers as shown in class using Heap's dinosaur plotting software. Also means no lunch break, hit run and it'll be done in a jiffy. I discovered there's also the fast fourier transform algorithm (FFT), which is much more complex but turns out to be much much faster since it's a big O(nlogn) algorithm.


In class we also saw the problem of n-scattered dots on a 2-D plane and finding the closest pair of points. Again the brute force method, which would be comparing each point to all the other points and tracking the distances, is big O(n^2). Now our intuition now should be to divide and conquer this problem. Divide the plane into half vertically and do so again for each half until you have a base case where you only have 1 or 2 points on the plane. Find the size of the 2 points or return 0 if there was only 1 point. Then compare it with the other half and figure out which side had the smallest pair and return that and so on so forth (essentially recursively finding the closest pair on the left and right and comparing them and returning that). But this solution wasn't so simple since we had to consider that there could be a pair whose connection crosses the imaginary vertical line and it's distance could be smaller than the closest pair on the left and right. The trick to solving this was a little hard to follow at first, but after re-reading it a few times and drawing out my own example by hand the solution became a little obvious. We just had to draw out our boundary for this possible pair, being D/2 (D = distance of closest pair from left or right) all over the vertical line. Then pick a point and compare it to it's surround points within a D radius, but we said 15 points. So traverse through the points inside the smaller plane along the vertical searching for a closer pair, which takes big O(n). So together it looks like a O(nlogn) algorithm since it behaves almost like merge sort if you look at the big picture.

I find that doing these kinds of analysis is really cool, you can think of different solutions to a problem and be able to work out the time complexity without programming it and testing how long they take. This is what I was looking forward to learning in this course and it looks like we only brushed the surface. I'll be re-reading these and paying more attention in class to absorb this material better and hopefully become a better computer scientist. But I can't wait till 263, it's going to be a mind blowing course.

Woche Zwei

So it has been 2 weeks since my last slog since I started early when Heap emailed us during thanksgiving weekend saying we should start during that week. Anyways there's a lot to recap on during this course since my last slog.

 Friday's lecture we got our midterms back and I was surprised to see I did so well. I looked through the marking scheme for the midterm and our proof structures and layout of our proof was worth a lot and the tricks inside the induction step weren't worth as much. I think this attributed to my higher mark since I think my induction step was a little too long and not precise for question 2 and for question 3 as well. I examined my midterm carefully I believe the 2 marks I lost were from the conclusion statements at the end of each question. My conclusion was very brief since I basically wrote "for all n, P(n)" and this is exactly what Heap said he would be deducting a mark for. I must avoid this mistake and state a clear conclusion that shows my understanding of the structure of the proof and why the conclusion holds. Also for the induction steps I should definitely avoid writing a paragraph explaining everything like I did in question 2. At the time I was just quickly racing along writing down all my thoughts and reasoning on that paper without thinking twice about details that might not have been necessary and obvious. Then the complete opposite on question 3, I barely wrote any guts inside the induction step and it was more structure than proof (except for a terrible conclusion I believe). I think I did skip or 2 that could have added more clarity for a reader at our level, I felt the time squeeze on that question and was forced to skip some steps there. Overall I'm glad I did well and hope I can avoid these mistakes, by knowing the marking scheme and my mistakes, so on the next midterm I can get a perfect!

Before writing this slog I was also looking at tutorial #3 from last week and tried the problems since I didn't have any time to do it last week and the TA didn't have time for question 2 and 3. Doing the 3rd problem seemed the most fun because unwinding a recurrence is tricky and sometimes can be unexpected as to what the closed form is.

The question was find the closed form of G(n) = 1  if n < 2, G(n) = 1 + G(n-1) + G(n-2)   if n >= 2

So carefully unwinding the function as suggested I a series of equivalences of the same form as above for n >= 2, except with 2 coefficients in front of each G(n-i). Expanding the recurrence and collecting like terms each time allowed me to see that the coefficients in front of the initially G(n - 1) started at 1 and then went to 2G(n - 2), 3G(n - 3), 5G(n - 4), 8G(n - 5), 13G(n - 6).... and so on. Looking at just this term the pattern became obvious and surprising initially since it was a Fibonacci sequence of coefficients. The form followed exactly fib(i + 1)G(n - i) and similarly for the 2nd term which was initially G(n - 2) the form became fib(i)G(n - i -1). Now this is still not in closed form, so working through till (n - i) = 0 so that i = n, we see that G(n - n + 1) = 1 and G(n - n) = 1. This then simplifies our equivalence to 2 fib(n + 1) + 2 fib(n) - 1. The lonely constant wasn't so lonely after all since it was the result of the coefficients on both terms minus 1, fib(i + 1) + fib(i) - 1. Now remembering the closed form of the Fibonacci sequence from our notes it can be rewritten as G(n) = 2/sqrt(5)[(Φ^n+1 - (φ)^n+1) + (Φ^n - (φ)^n)] - 1. This seems like a plausible answer since initially the G(n) function looks almost similar to the recursive definition of the Fibonacci sequence except with an added - 1. Gosh who knew counting rabbits would extend all the way here! I felt like this kind of problem was something like the other tutorial problems, similar to the notes except with a little tweak or additional trick. It might be something we can expect on a midterm or exam, although it is a little tedious and a time killer!

I don't want to make this blog entry too long, I'll be writing up another one soon! 

First Impressions

First entry here we go!

It's been a satisfying month since the start of the course, it's been everything I've been expecting after csc165 last year. It's bringing the challenges that were presented last year except on a higher level. We started off with our old simple/mathematical induction we all knew and grew comfortable with in 165 and dove right into complete induction, well ordering, and structural induction with recursive functions. Upon first learning them, I didn't absorb everything in the lecture and I'm guessing it will take me some time to "master" these new flavours and to apply them efficiently. Practicing writing more and more well thought out and incrementally challenging proofs will set me up to shoot down anything on the midterms or exam, just like in 165.

Looking at the assignment 1, it was a great place to start practicing writing up proofs after doing some from the tutorial problem sets. After writing it up I felt like I was understanding complete induction much better than I had before from the lectures and tutorials because I wrote the proof and didn't toss it away, but instead took another hard look at it and tried poking holes in the proof and evaluating it's structure. It took some time to realize that we weren't being evaluated purely on our ability to solve the proof, but the coherency and elegance of our proof. I recall Heap in one of our lectures mentioning that a good proof is a proof that can be absorbed in "one gulp" - by that he meant keeping proofs to one page. Maximum one page proofs meant we had to consider the audience and assume they can follow our proof if we skipped explaining a few obvious steps and proving nontrivial lemmas we used.

The only thing now I must do is study for the midterm on Wednesday. The structural induction isn't so bad after trying out a few proofs with it, but well ordering is the weird one for me! It's not hard to follow the proof step by step, but in the scope of the entire problem it's a little weird how we have to use proof by contradiction that some number is the least element. I'm starting to read the section in the book, although there doesn't seem to be a lot on it I'll try re-reading the notes and finding some problems to practice on, which helps me out the most.

Still remaining hopeful that I can do just as well as I did in 165, except not learning everything last minute!