So here I am writing my last slog post. I just want to say I have enjoyed the course this semester. It was very interesting learning new material that expanded on what little we knew coming from 165 and overcoming the challenges I've faced in this course. Through the semester I found that the tutorials and assignments were directly tested on the midterms and that I could have done a little better on my tests by reviewing these a little more. The assignments were tricky because we had too explain what we knew in a concise format without skipping any step and without making the proof too long. It was great practice for writing and communicating thoughts clearly, which I think is a very important skill anywhere. Also I felt like the assignments really made us think critically about the course material and helped us gain insight and draw connections and although I didn't like the assignments because of the grading, I still enjoyed doing them. All in all it was a great learning experience, I can definitely say I walked out learning something.
Lastly I just want to thank Heap for being a great instructor, in fact the best of my 6 instructors this semester. He made the lectures well worth going to and enjoyable thanks to his jokes.
I'd also like to thank my TA who was very helpful explaining the tutorial problems.
And so here's to an end of a great course!
Wednesday, 5 December 2012
Problem solving post part 2
Okay time to pick up on the problem again after giving my brain a rest and then thinking about it some more. So going back I only looked at the case when the lists were exactly the same length and contained the same songs in different order. But what if the lists contained elements that didn't exist in the other list or what would happen if the lists were of different length?
Consider the example that takes both cases into consideration.
L1 = [A, B, C, D, E, F] and
L2 = [L, P, A, M, C, E, Q, R]
Notice that if the same algorithm for finding the closeness of the 2 lists was applied we'd find that there's only 3 swaps needed, but the list that results from the swaps, [A, P, C, M, E, L, Q, R], is still much different from the list L1. And if L2 was L1 reversed like I did in the previous post, the answer was also 3 swaps. But the L2 in the first post should be closer to L1 since its the same length and includes all the elements of L1.
This is a contradiction! So this is where things get hairy and my algorithm breaks down. Instead of scoring by swaps, I should score by comparisons made till a swap has been made. But things will get a little complicated when dealing with elements that are not in L1 that are in L2 when trying to track indices.
I have re-thought the problem using a tweaked version of recursive binary search (RBS). So now I'll assume the data given is 2 lists sorted based on preference ( [favourite .... least-favourite]) and that the 2 lists can be of different length and include unique elements. Will also assume that neither set is empty.
I will use the fact that L1 and L2 being lists (or arrays in java, but I'll stick with my python terminology) have indices that we can use. So the algorithm will be as follows for a sample data set bellow.
index 0 1 2 3 4 5
L1 = [A, B, C, D, E, F]
L2 = [A, F, L M, B, D, J, K, Q]
index 0 1 2 3 4 5 6 7 8
Take the first element of L1, at index 0, L1[0] is A. Now use A in a recursive binary search to find where it lies in L2. The call will be ModifiedRBS(L2, L1[0], 0, 9 -1), so it will search in L2 for L1[0] (ie. A) and the start index is 0 and the end index is 8. Now this is where I'd like to tweak the RBS to return the absolute difference between the index of L1 given (in this case 0) and the index at which L1[0] was. So in this case it will return 0.
Now it will move to the next element in L1, at index 1, L1[1] is B. ModifiedRBS(L2, L1[1], 1, 9 - 1) will return 3 since B is at index 4 in L2 and the difference between 4 and the index B is in L1 is abs(4-1) = 3.
Moving to the next element, L1[2] is C and C is not in L2 so typically a RBS would return -1 for value that is NOT in the list. In my tweaked version ModifiedRBS will return the length of L2, which is 9.
So the algorithm in summary:
Loop through L1 and for each element call ModifiedRBS(L2, L1[i], i, n-1), where 'i' is the index of the current element in L1 and 'n' is the length of L2. Then add this returned value to an accumulator to track the score.
and in summary ModifiedRBS(L2, L1[i], i, n-1) will have 2 cases on what is returned
IF L1[i] is found somewhere in L2 at index P, then return abs(i - P)
IF L1[i] is not in L2, then return n.
Once the scores are accumulated the lower the score means the closer the lists are since it means the indices of the elements in L1 are closer to the elements in L2 since the difference ModifiedRBS returns will be smaller. If there is a score of 0, being the lowest score, then the lists are exactly the same length and contain the same elements ranked in the same order. The highest score being len(L2)*len(L1) since for ever element in L1, the length of L2 is returned.
Now that the scoring system is figured out, let me talk about complexity.
Know that RBS is O(logn) and in this algorithm we are looping through L1 and calling RBS that many times in L2. So let n = len(L2) and m = len(L1) then the complexity is O(mlogn). The reason I used 2 variables is because the size of L1 and L2 can change independently of one another so the growth in time will be different if only L1 increases or if only L2 increases.
I will simplify the complexity to O(nlogn) assuming the list sizes of L1 and L2 are the same always so I can compare it with my old 2 methods back from the first post.
Notice how I had to graph it from 0 to 50 because when I attempted 0 to 100,000 the nlogn was on the x axis and not even visible. This is finally some great news and relief. I've found an nlogn solution to this problem!
Solving this problem was quite challenging because I didn't know where I was going, I just found a starting point and worked from there not knowing where I was going with it. At first when I heard this problem, it excited me in class because it's a real life application of something that we must have been exposed to in class. But in the lecture I remained clueless, progress only made it's when when I first sat down to attempt the problem! Now I'm glad I've found a solution that has satisfied me because I just can't sleep at night knowing I've only found a O(n^2) solution.
Well that just about does it, I'm done my problem solving adventure slog! It was fun, interesting, and challenging to see myself solve a problem using things I've learned in class to a real life problem. I'll be writing up a closing blog to wrap my thoughts on this course later today (at night).
Consider the example that takes both cases into consideration.
L1 = [A, B, C, D, E, F] and
L2 = [L, P, A, M, C, E, Q, R]
Notice that if the same algorithm for finding the closeness of the 2 lists was applied we'd find that there's only 3 swaps needed, but the list that results from the swaps, [A, P, C, M, E, L, Q, R], is still much different from the list L1. And if L2 was L1 reversed like I did in the previous post, the answer was also 3 swaps. But the L2 in the first post should be closer to L1 since its the same length and includes all the elements of L1.
This is a contradiction! So this is where things get hairy and my algorithm breaks down. Instead of scoring by swaps, I should score by comparisons made till a swap has been made. But things will get a little complicated when dealing with elements that are not in L1 that are in L2 when trying to track indices.
I have re-thought the problem using a tweaked version of recursive binary search (RBS). So now I'll assume the data given is 2 lists sorted based on preference ( [favourite .... least-favourite]) and that the 2 lists can be of different length and include unique elements. Will also assume that neither set is empty.
I will use the fact that L1 and L2 being lists (or arrays in java, but I'll stick with my python terminology) have indices that we can use. So the algorithm will be as follows for a sample data set bellow.
index 0 1 2 3 4 5
L1 = [A, B, C, D, E, F]
L2 = [A, F, L M, B, D, J, K, Q]
index 0 1 2 3 4 5 6 7 8
Take the first element of L1, at index 0, L1[0] is A. Now use A in a recursive binary search to find where it lies in L2. The call will be ModifiedRBS(L2, L1[0], 0, 9 -1), so it will search in L2 for L1[0] (ie. A) and the start index is 0 and the end index is 8. Now this is where I'd like to tweak the RBS to return the absolute difference between the index of L1 given (in this case 0) and the index at which L1[0] was. So in this case it will return 0.
Now it will move to the next element in L1, at index 1, L1[1] is B. ModifiedRBS(L2, L1[1], 1, 9 - 1) will return 3 since B is at index 4 in L2 and the difference between 4 and the index B is in L1 is abs(4-1) = 3.
Moving to the next element, L1[2] is C and C is not in L2 so typically a RBS would return -1 for value that is NOT in the list. In my tweaked version ModifiedRBS will return the length of L2, which is 9.
So the algorithm in summary:
Loop through L1 and for each element call ModifiedRBS(L2, L1[i], i, n-1), where 'i' is the index of the current element in L1 and 'n' is the length of L2. Then add this returned value to an accumulator to track the score.
and in summary ModifiedRBS(L2, L1[i], i, n-1) will have 2 cases on what is returned
IF L1[i] is found somewhere in L2 at index P, then return abs(i - P)
IF L1[i] is not in L2, then return n.
Once the scores are accumulated the lower the score means the closer the lists are since it means the indices of the elements in L1 are closer to the elements in L2 since the difference ModifiedRBS returns will be smaller. If there is a score of 0, being the lowest score, then the lists are exactly the same length and contain the same elements ranked in the same order. The highest score being len(L2)*len(L1) since for ever element in L1, the length of L2 is returned.
Now that the scoring system is figured out, let me talk about complexity.
Know that RBS is O(logn) and in this algorithm we are looping through L1 and calling RBS that many times in L2. So let n = len(L2) and m = len(L1) then the complexity is O(mlogn). The reason I used 2 variables is because the size of L1 and L2 can change independently of one another so the growth in time will be different if only L1 increases or if only L2 increases.
I will simplify the complexity to O(nlogn) assuming the list sizes of L1 and L2 are the same always so I can compare it with my old 2 methods back from the first post.
Notice how I had to graph it from 0 to 50 because when I attempted 0 to 100,000 the nlogn was on the x axis and not even visible. This is finally some great news and relief. I've found an nlogn solution to this problem!
Solving this problem was quite challenging because I didn't know where I was going, I just found a starting point and worked from there not knowing where I was going with it. At first when I heard this problem, it excited me in class because it's a real life application of something that we must have been exposed to in class. But in the lecture I remained clueless, progress only made it's when when I first sat down to attempt the problem! Now I'm glad I've found a solution that has satisfied me because I just can't sleep at night knowing I've only found a O(n^2) solution.
Well that just about does it, I'm done my problem solving adventure slog! It was fun, interesting, and challenging to see myself solve a problem using things I've learned in class to a real life problem. I'll be writing up a closing blog to wrap my thoughts on this course later today (at night).
Monday, 3 December 2012
Problem solving post part 1
One of my older posts had a long somewhat long problem solving style, but this is the official problem solving post!
Now going back and counting the number of swaps there was exactly 3 swaps and the score for how similar these 2 music preferences were could be calculated by [(number of songs)-3]/(number of songs) as a generic way, it's not too important how we calculate the score. Repeating this for a list of length 10 can quickly draw a connection to the number of swaps that much be preformed for the WORST CASE scenario since best case is 0 swaps (happens when the lists are exactly the same). Thinking about it conceptually exactly half (in case of odd (n-1)/2, ie value to the left of the middle) of the elements will need to be swapped since if the swap happens it will be swapping with another element which will take its place and both will be in order. So if it's an even length is this would be n/2 swaps happening. An odd length list will behave similarly except the number of will be floor(n/2) since the middle element will be untouched. So in either case we have floor(n/2) swaps as the worst case.
However what is important is trying to figure out the complexity of such an algorithm (number of comparisons) . First must decide how the 2nd list is going to be searched. A really naive way of searching for a matching value from L1 is by scanning all the values in L2, which means we are looking at elements that are already 'sorted' according to L1. This is right off the bat a O(n^2) algorithm since we are comparing every value in L1 (n values) with every value in L2 'n' amount of times.
A better way I can think of is starting the search to the right of the array of the current index, so if I was comparing the value at index 2 in L1 then I would start the search at L2[2] and search towards the right instead of starting at the beginning of the list in L2. This means I would be making in total n + n-1 + n-2 +... comparisons since the left side of the list (which we ignore since it's sorted) will grow by 1 each iteration of picking the next value in L1 meaning the right side will shrink by 1.
Adding the sum of this series find that it's n(n+1)/2 comparisons which is really 1/2(n^2 + n) so this is another O(n^2) algorithm. Although it will run faster since n^2 > 1/2(n^2 + n), it's still not satisfying for me since we usually like to look for nlogn or logn or linear run-time complexities.
But here's a graph generated by wolfram alpha of the 2 functions for large values from [0, 100000] and clearly the first method is much slower, almost takes twice as long as the second method! So there is a significant difference over large lists.
Now this is too much work for one session, I must revisit this to try to find a better solution that can run faster and possibly consider the cases of lists being different lengths (L1 contains elements that are not in L2 and vise versa). But so far the progression is looking good, I found a solution to solving the problem by finding a scoring system to match the two people's song preferences and looked into the complexity of 2 different versions. I will revisit this Wednesday night!
The problem that I will attempt to solve is something that was mentioned at the end of class on Friday, October the 26th. Heap mentioned before class ended a problem of finding how close 2 people's list of favourite songs were. The application that was mentioned was recommending music to other people when they are shopping on itunes for example. What I'm going to be looking for is a algorithm to find how close the 2 lists of songs and by scoring the pair with a generic scoring system.
So the data presented presumably is a list of songs ranked from most favoured to least favoured (so in decreasing order). I will assume for simplicity sake at this point that the list of the second person I am comparing to is of the same size and no repetitions are included.
Here is some scratch work I did to get an idea of the problem and see if I can make a conjecture as to the complexity of the problem.
Suppose the sample list is of length 4 comprising of artists A, B, C and D in order of most favoured to least favoured. Now say the list of the second person is the reverse order D, C, B, A
The method I found useful for comparing how close the 2 lists were in terms of order was by determining the number of switches/swaps needed in the second list to get to the same order as the first list. In this case it's exactly 2 swaps required; swap D and A and then swap C and B. The reason these pairs were swapped was because D being at index 0 didn't match with A at index 0 in the first list and so the list was searched to find A and then swapped with D. Then similarly C in list 1 didn't match the item at index 1 in the first list, B, and so the second list was searched for B and then swapped with C.
Let me try a larger list of length 6 to see more swaps and see how it can compare with the above list.
Let L1 = [A, B, C, D, E, F] and L2 = [F, E, D, C, B, A] and notice how I'm simulating the worst case scenario where the lists are total opposites.
So just like before start at index 0, L1[0] is A in this case and compare it to L2[0] right bellow, they are not the same so compare it to L2[1], L2[2],.. and so on till a match is found. A match is found at the end so F and A (in red) are swapped.
Now move the next song by increasing the index by 1, so L1[1] in this case is B and repeat the same
method as above. So at the end E and B are swapped.
Now move the next song by increasing the index by 1, so L1[1] in this case is B and repeat the same
method as above. So at the end E and B are swapped.
Repeat above again for L1[2] which is C. After the swap is done, moving to the next index L1[3] which is a D and comparing L1[3] to L2[3] they are the same! If this is the case then we are done and now the lists are the same.
Now going back and counting the number of swaps there was exactly 3 swaps and the score for how similar these 2 music preferences were could be calculated by [(number of songs)-3]/(number of songs) as a generic way, it's not too important how we calculate the score. Repeating this for a list of length 10 can quickly draw a connection to the number of swaps that much be preformed for the WORST CASE scenario since best case is 0 swaps (happens when the lists are exactly the same). Thinking about it conceptually exactly half (in case of odd (n-1)/2, ie value to the left of the middle) of the elements will need to be swapped since if the swap happens it will be swapping with another element which will take its place and both will be in order. So if it's an even length is this would be n/2 swaps happening. An odd length list will behave similarly except the number of will be floor(n/2) since the middle element will be untouched. So in either case we have floor(n/2) swaps as the worst case.
However what is important is trying to figure out the complexity of such an algorithm (number of comparisons) . First must decide how the 2nd list is going to be searched. A really naive way of searching for a matching value from L1 is by scanning all the values in L2, which means we are looking at elements that are already 'sorted' according to L1. This is right off the bat a O(n^2) algorithm since we are comparing every value in L1 (n values) with every value in L2 'n' amount of times.
A better way I can think of is starting the search to the right of the array of the current index, so if I was comparing the value at index 2 in L1 then I would start the search at L2[2] and search towards the right instead of starting at the beginning of the list in L2. This means I would be making in total n + n-1 + n-2 +... comparisons since the left side of the list (which we ignore since it's sorted) will grow by 1 each iteration of picking the next value in L1 meaning the right side will shrink by 1.
Adding the sum of this series find that it's n(n+1)/2 comparisons which is really 1/2(n^2 + n) so this is another O(n^2) algorithm. Although it will run faster since n^2 > 1/2(n^2 + n), it's still not satisfying for me since we usually like to look for nlogn or logn or linear run-time complexities.
But here's a graph generated by wolfram alpha of the 2 functions for large values from [0, 100000] and clearly the first method is much slower, almost takes twice as long as the second method! So there is a significant difference over large lists.
Now this is too much work for one session, I must revisit this to try to find a better solution that can run faster and possibly consider the cases of lists being different lengths (L1 contains elements that are not in L2 and vise versa). But so far the progression is looking good, I found a solution to solving the problem by finding a scoring system to match the two people's song preferences and looked into the complexity of 2 different versions. I will revisit this Wednesday night!
Saturday, 17 November 2012
FSA's
The course just took a big turn from talking about program correctness to a new direction and introducing us to FSA's. I liked proving correctness of programs because it was material we have been exposed to 165 last year and it was more familiar to us. We knew what pre-conditions and loop invariants were and it was very easy for us to follow the lectures and understand what was going on. I felt like the course was becoming more manageable in terms of doing minimal work outside of class. But now that the course has moved into talking about finite state automata, it's a new challenge to understand the lectures completely on first exposure. But so far form what I'm seeing, FSA's are pretty cool. Looking at the transition functions δ*(q, s) they do incorporate some neat computer science since the transition from some state q will depend on the alphabets of s so the call will be recursive till s is an element of the alphabet and not a string. At this point there is a state to transition to and to start from on the back going back down the call stack. So they do allow computer scientists to model some complex problems that are too tricky to work out on paper which is subjected to mistakes. Also I really like the diagrams in this section of the course, the diagrams are "worth a thousand words" and really help me understand quickly the content we are learning. Hope things continue to make sense in the coming lectures.
Saturday, 10 November 2012
Program Correctness - Termination
The way we have gone about proving termination was a little interesting since we have used the principle of well ordering. I've never thought we would actually use this and it definitely helps in my understanding of well -ordering since at first I couldn't really think of a nice example where well-ordering is absolutely clear and makes intuitive sense. For example proving termination of an iterative binary search program meant that we had to show the difference between the last element's index and the first element's index in the array/sub-array was a decreasing finite set and so it must have a smallest element. Indeed it is true that when F >= L can only happen if F = L happens first since either F or L changes in each loop iteration decreasing by 1 (never both changing). And so F = L implies L - F = 0 where 0 is the smallest element in a natural numbers set. And we know L - F is always decreasing by one as was shown in lecture so that Li+1 - Fi+1 < Li - Fi where i is the ith iteration of the loop assuming i + 1 iterations happen (in other words either F or L decrease by one in each iteration and so L - F continually decreases). So since Li -Fi is a decreasing sequence of natural numbers (since L and F were natural numbers and decreasing either by 1 each iteration keeps them as natural numbers) then it must have the smallest element 0 and so the loop will terminate. It's neat to see induction playing a role in everything we are doing now and seeing this it seems to be a very fundamental computer science concept. I guess we'll be seeing again in 263!
Saturday, 3 November 2012
Test tomorrow!
After doing A2, it forced me to look over the relevant notes and sections in the book and gave me a good understanding of what we've been doing in class. I found question 1 on A2 to be quite long as we first need to analyse some binary strings and find a pattern for OMCOFs, establish a recursive definition, explain why it's true, then unwind it using repeated substitution and express it in terms of the golden ration (Phi and Phi hat), and then finally using complete induction prove the close form is correct. That is a lot of work and I'm hoping on the test the questions won't be this long and be more reasonable like the length of test 1. Test 1 had 2 very easy brief questions (1 and 3) and question 2 was the longer one as it needed some well written explanations for what was going on inside the induction step. I feel like A2 Q1 format will be simulated in an easier way in the midterm since in A1 we had a question similar to our test 1 Q2. I am really hoping it will be easier since question 1 didn't take 1/3 of 50 minutes to solve, it took much longer than that plus the time it took to reread the proof and correct it. At least now with exposure to the type of questions in A2 it is fair game on the test!
So to prepare for this test I must review the tutorial problems by doing all the questions and checking my answers with the solutions and then search for some past midterm questions to get even more practice. It sounds like a lot, but I must also read the lecture notes on correctness of recursive algorithms since it might be on the test. I did miss the lecture when we started covering this so I will defiantly skim the 2nd chapter of the book since the lectures really require you to be there to understand the notes posted up.
So tutorial problems + past test questions + reading on the new unit will hopefully get me ready for tomorrow's midterm.
Sunday, 28 October 2012
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.
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.
Sunday, 21 October 2012
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.
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!
Sunday, 7 October 2012
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!
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!
Subscribe to:
Posts (Atom)