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