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.
Subscribe to:
Posts (Atom)