PK iA - Problem_Set_61_Starred/01-Family_Trees.en.srt1
00:00:00,000 --> 00:00:05,000
In this problem, we're given a dictionary where the keys are children
2
00:00:05,000 --> 00:00:08,000
and the values are a list of parents,
3
00:00:08,000 --> 00:00:12,000
and given a person, we want to go through the dictionary,
4
00:00:12,000 --> 00:00:17,000
and calculate a list that contains all of that person's ancestors.
5
00:00:17,000 --> 00:00:19,000
So let's go over the plan.
6
00:00:19,000 --> 00:00:21,000
We're going to use recursion.
7
00:00:21,000 --> 00:00:24,000
We're going to find the person that we're searching for in the dictionary.
8
00:00:24,000 --> 00:00:29,000
We're going to add that person's parents, their direct relatives, to the output list,
9
00:00:29,000 --> 00:00:33,000
and then we're going to recurse on the parents to find the ancestors,
10
00:00:33,000 --> 00:00:36,000
adding the result of this recursive call to our output list.
11
00:00:36,000 --> 00:00:37,000
This should be enough to get started,
12
00:00:37,000 --> 00:00:39,000
so let's go right to the editor.
13
00:00:39,000 --> 00:00:42,000
If the person we're searching for is in the genealogy dictionary,
14
00:00:42,000 --> 00:00:45,000
we're going to do what we described previously.
15
00:00:45,000 --> 00:00:47,000
If they're not in the dictionary, we're going to return an empty list
16
00:00:47,000 --> 00:00:50,000
because we don't know any of their ancestors.
17
00:00:50,000 --> 00:00:53,000
So for each parent, we're going to add their ancestors to the result list,
18
00:00:53,000 --> 99:59:59,000
and once we're done, we're going to return the result list. And that's it.
PK iA>qs s : Problem_Set_61_Starred/02-Khayyam_Triangle_Solution.en.srt1
00:00:00,000 --> 00:00:07,000
So in this problem, we're going to try to build up a given row of Pascal's triangle.
2
00:00:07,000 --> 00:00:11,000
So you could solve this problem recursively, and that's what I did my first time,
3
00:00:11,000 --> 00:00:16,000
but I feel that the iterative solution is a bit simpler and more intuitive to understand.
4
00:00:16,000 --> 00:00:20,000
This isn't always the case, but this is how I'm going to explain this problem.
5
00:00:20,000 --> 00:00:25,000
What we're going to do is, we're going to start with a list that's row 1,
6
00:00:25,000 --> 00:00:29,000
and then we're going to build the next list by adding the 2 numbers above it.
7
00:00:29,000 --> 00:00:35,000
More precisely, let's say we're doing the last row, and we have the previous row
8
00:00:35,000 --> 00:00:38,000
already made, we're going to start an invisible 0 here,
9
00:00:38,000 --> 00:00:43,000
and we're going to say, 1 is going to be the sum of the 0 number that I just made up
10
00:00:43,000 --> 00:00:49,000
and the 1 that's the first element of the previous row.
11
00:00:49,000 --> 00:00:52,000
We're going to update our pointers to move over by 1,
12
00:00:52,000 --> 00:00:55,000
and we get to the element 4 by adding 1 and 3.
13
00:00:55,000 --> 00:00:58,000
I'm going to repeat this process all the way through.
14
00:00:58,000 --> 00:01:04,000
6 is 3 + 3. 4 is 3 + 1. 1 is 1 and 0.
15
00:01:04,000 --> 00:01:08,000
So that's pretty easy to explain, and that's basically how you would do it
16
00:01:08,000 --> 00:01:10,000
if you were building it out by hand,
17
00:01:10,000 --> 00:01:15,000
but putting it in a code may be a little bit more complicated and have alluded you.
18
00:01:15,000 --> 00:01:16,000
So let's see how it's done.
19
00:01:16,000 --> 00:01:21,000
So if I initialize the first row in the triangle to 1.
20
00:01:21,000 --> 00:01:24,000
We don't have anything for a result yet, so that's an empty list.
21
00:01:24,000 --> 00:01:30,000
I'm then going to iterate through the process of building each row 1 at a time, n times.
22
00:01:30,000 --> 00:01:33,000
That way we can get to the nth row.
23
00:01:33,000 --> 00:01:37,000
We're going to append the row that we just discovered onto the result list.
24
00:01:37,000 --> 00:01:41,000
The first time around it will just be the list of 1 because that's how the triangle starts.
25
00:01:41,000 --> 00:01:44,000
We're then going to find the next row, which I haven't defined yet,
26
00:01:44,000 --> 00:01:48,000
and then repeat this process appending the current row onto the result list.
27
00:01:48,000 --> 00:01:51,000
Once we're done, we're going to return the result.
28
00:01:51,000 --> 00:01:55,000
So this is a good outline of what we're doing, but we're missing the most important part,
29
00:01:55,000 --> 00:01:57,000
and that is the makenextrow.
30
00:01:57,000 --> 00:02:00,000
So a row is going to start as an empty list.
31
00:02:00,000 --> 00:02:03,000
As I had the 2 pointers before, we're going to have the previous one
32
00:02:03,000 --> 00:02:05,000
and then we're going to have one that I'm going to call e.
33
00:02:05,000 --> 00:02:10,000
So as I said in the description, we're going to start out with 0.
34
00:02:10,000 --> 00:02:14,000
That way when we add 1, we get 1, which is the sides of the triangle.
35
00:02:14,000 --> 00:02:18,000
We're going to calculate the new entry in the current row
36
00:02:18,000 --> 00:02:25,000
by adding e--that's our right pointer--with the previous one that we start at 0
37
00:02:25,000 --> 00:02:26,000
so that we get 1.
38
00:02:26,000 --> 00:02:29,000
We're going to update the values in previous and then the next iteration,
39
00:02:29,000 --> 00:02:32,000
e will update to the next value in row.
40
00:02:32,000 --> 00:02:36,000
This last line basically includes the 1 on the right-hand side.
41
00:02:36,000 --> 99:59:59,000
Once we return result, triangle can use makenextrow accordingly, and we're done.
PK iA2P P = Problem_Set_61_Starred/03-Only_A_Little_Lucky_Solution.en.srt1
00:00:00,000 --> 00:00:05,000
Unlike the previous problem called Feeling Lucky, where we wanted to modify
2
00:00:05,000 --> 00:00:10,000
the search engine such that it returned the highest ranking result,
3
00:00:10,000 --> 00:00:17,000
we want to create a new function that orders the results according to the ranking.
4
00:00:17,000 --> 00:00:22,000
Now in order to do this, what we need to solve is sorting.
5
00:00:22,000 --> 00:00:27,000
We need to be able to sort the pages according to the ranking.
6
00:00:27,000 --> 00:00:29,000
This is a very well-studied problem.
7
00:00:29,000 --> 00:00:32,000
and a canonical example of algorithms.
8
00:00:32,000 --> 00:00:36,000
For the purposes of this course and a kind of reinforced recursion,
9
00:00:36,000 --> 00:00:39,000
we're going to use the quicksort algorithm.
10
00:00:39,000 --> 00:00:42,000
Quicksort is interesting because it's incredibly elegant.
11
00:00:42,000 --> 00:00:47,000
It's recursive, and it happens to be one of the fastest ways you can do sorting,
12
00:00:47,000 --> 00:00:49,000
and we're going to do it in just a few lines of code.
13
00:00:49,000 --> 00:00:54,000
Before we get started, I'll go quickly over how quicksort works.
14
00:00:54,000 --> 00:00:57,000
Let's say we have this list of 5 elements,
15
00:00:57,000 --> 00:00:59,000
and we're going through the quicksort algorithm.
16
00:00:59,000 --> 00:01:02,000
The first thing we need to do is to choose a pivot point.
17
00:01:02,000 --> 00:01:06,000
A lot of implementations use a random one, but it really doesn't matter
18
00:01:06,000 --> 00:01:09,000
if we assume that the data we're given is randomly distributed.
19
00:01:09,000 --> 00:01:12,000
So let's just choose the first element as our pivot point.
20
00:01:12,000 --> 00:01:15,000
That makes coding it simpler, and it's also a little simpler to go through.
21
00:01:15,000 --> 00:01:20,000
What we're going to do now is divide the rest of the elements according to things
22
00:01:20,000 --> 00:01:26,000
that are smaller than the pivot point and things that are greater than the pivot point.
23
00:01:26,000 --> 00:01:27,000
So let's do that.
24
00:01:27,000 --> 00:01:30,000
So we have our pivot point 2, and now we're going to go through the rest of the elements
25
00:01:30,000 --> 00:01:33,000
and decide whether or not they're greater than or less than 2.
26
00:01:33,000 --> 00:01:35,000
A pretty simple operation.
27
00:01:35,000 --> 00:01:37,000
So 1 is less than 2. We're going to add it to this list.
28
00:01:37,000 --> 00:01:39,000
8 is greater than 2.
29
00:01:39,000 --> 00:01:44,000
0 is less than 2. Notice how I didn't bother with the ordering of the sublist.
30
00:01:44,000 --> 00:01:50,000
We're going to take care of that by recurring quicksort onto the sublist of each side.
31
00:01:50,000 --> 00:01:53,000
9 is greater than 2, and we're done.
32
00:01:53,000 --> 00:01:55,000
What we have is a partially-sorted list.
33
00:01:55,000 --> 00:01:58,000
Everything that is less than 2 is on the left side of this,
34
00:01:58,000 --> 00:02:01,000
and everything that's greater than 2 is on the right side.
35
00:02:01,000 --> 00:02:05,000
So what we're going to do is, we're going to redo the same thing to the left side,
36
00:02:05,000 --> 00:02:07,000
the same thing to the right side,
37
00:02:07,000 --> 00:02:11,000
and in the end, once we sorted everything, we combine them all together,
38
00:02:11,000 --> 00:02:13,000
and we have a sorted list.
39
00:02:13,000 --> 00:02:15,000
So let's go through that real quick.
40
00:02:15,000 --> 00:02:18,000
So here 1 is the pivot point. We get 1.
41
00:02:18,000 --> 00:02:19,000
0 is less than 1.
42
00:02:19,000 --> 00:02:23,000
Here 8 is the pivot point. 9 is greater than 8.
43
00:02:23,000 --> 00:02:25,000
And we're done here. We're also done here.
44
00:02:25,000 --> 00:02:28,000
Now we're left with single element lists.
45
00:02:28,000 --> 00:02:34,000
We do quicksort on each of these, and a list of 1 element is sorted,
46
00:02:34,000 --> 00:02:36,000
so we're done sorting at the bottom.
47
00:02:36,000 --> 00:02:39,000
We now append on the way up.
48
00:02:39,000 --> 00:02:44,000
So the end result of all of these appendings will be our sorted list.
49
00:02:44,000 --> 00:02:48,000
And just to finish our list, let's just say we called it conquer.
50
00:02:48,000 --> 00:02:50,000
Hopefully this gives you an idea of what we're doing.
51
00:02:50,000 --> 00:02:54,000
So let's go to the code, and it might become a little clearer if you're confused.
52
00:02:54,000 --> 00:02:56,000
So our orderedsearch takes in 3 parameters:
53
00:02:56,000 --> 00:03:01,000
the index, the ranking of the pages, and the keyword that we're searching for.
54
00:03:01,000 --> 00:03:05,000
I'm going to look up the pages that are associated with that keyword,
55
00:03:05,000 --> 00:03:09,000
and then I'm going to quicksort the pages according to the rankings that it was passed
56
00:03:09,000 --> 00:03:10,000
into ordered search.
57
00:03:10,000 --> 00:03:13,000
This is another function that we'll have to define.
58
00:03:13,000 --> 00:03:16,000
So I'm taking in 2 lists--
59
00:03:16,000 --> 00:03:21,000
the url's and the rankings of those url's which is stored as a dictionary.
60
00:03:21,000 --> 00:03:25,000
So if I didn't get any pages passed in, or it was an empty list or whatnot,
61
00:03:25,000 --> 00:03:28,000
then I'm just going to not do anything and stop right here.
62
00:03:28,000 --> 00:03:33,000
This saves some cases that add a little bit of complexity later on if we take care of it now.
63
00:03:33,000 --> 00:03:36,000
So the first thing I'm going to do is find the pivot point,
64
00:03:36,000 --> 00:03:38,000
which is the ranking of the first page.
65
00:03:38,000 --> 00:03:41,000
That's, basically, how we did it in the example I went through.
66
00:03:41,000 --> 00:03:45,000
We initialized our 2 lists, the better list and the worst list.
67
00:03:45,000 --> 00:03:50,000
Now we're going to go through each page and put them in the correct list accordingly.
68
00:03:50,000 --> 00:03:53,000
One thing you might notice is that I didn't go through every page.
69
00:03:53,000 --> 00:03:54,000
I skipped the first page.
70
00:03:54,000 --> 00:03:58,000
That makes the code a little bit simpler because I've already included the page
71
00:03:58,000 --> 00:03:59,000
as the pivot point.
72
00:03:59,000 --> 00:04:03,000
Once we put the pages in the correct list, we're going to recur.
73
00:04:03,000 --> 00:04:06,000
In order to get the list concatenation to work appropriately,
74
00:04:06,000 --> 00:04:10,000
you need to put this pages into another list.
75
00:04:10,000 --> 00:04:17,000
This is the appending that I showed at the end, and this is the recurring that I showed earlier.
76
00:04:17,000 --> 00:04:18,000
This is all quicksort is.
77
00:04:18,000 --> 00:04:22,000
We got--what is it--14 lines of code,13 lines of code,
78
00:04:22,000 --> 00:04:25,000
and we can even save a little bit here and there if we wanted to,
79
00:04:25,000 --> 00:04:29,000
but we're just going to recur, and we're done.
80
00:04:29,000 --> 00:04:34,000
To go through it real quickly, if we have 1 page on our list or if there are no pages in our list,
81
00:04:34,000 --> 00:04:38,000
then it's considered sorted, and we return it right away.
82
00:04:38,000 --> 00:04:42,000
Otherwise, we find our pivot point, which we want to use as the first element,
83
00:04:42,000 --> 00:04:47,000
and for the rest of them, we're going to put them in the appropriate worse or better list,
84
00:04:47,000 --> 00:04:49,000
if they're better or worse ranked.
85
00:04:49,000 --> 00:04:53,000
We're then going to recur on each of our sublists, and once that's done,
86
00:04:53,000 --> 99:59:59,000
we're going to append them all together.
PK iA - Problem_Set_61_Starred/01-Family_Trees.en.srtPK iA>qs s : Problem_Set_61_Starred/02-Khayyam_Triangle_Solution.en.srtPK iA2P P = Problem_Set_61_Starred/03-Only_A_Little_Lucky_Solution.en.srtPK . k8