PK iA[ [ 3 Problem_Set_6/01-Recursive_Grammars_Solution.en.srt1
00:00:00,000 --> 00:00:05,000
For this question, we need to determine if the given grammar generates
2
00:00:05,000 --> 00:00:10,000
infinitely many strings starting from the nonterminal word.
3
00:00:10,000 --> 00:00:12,000
So we can start from either substitution rule.
4
00:00:12,000 --> 00:00:16,000
If we start from the first one, then we end up with 1 possible word.
5
00:00:16,000 --> 00:00:20,000
If we start from the second word, then we get the letter a,
6
00:00:20,000 --> 00:00:21,000
and then we can insert another word.
7
00:00:21,000 --> 00:00:25,000
This can be udacity, so then we end up with audacity.
8
00:00:25,000 --> 00:00:28,000
We can do the same thing but twice.
9
00:00:28,000 --> 00:00:33,000
So we have a, then instead of going to udacity, we do a again,
10
00:00:33,000 --> 00:00:35,000
and then we do udacity.
11
00:00:35,000 --> 00:00:38,000
The way this is breaking down kind of looks like this.
12
00:00:38,000 --> 00:00:42,000
It should be pretty clear that we can continue this forever and eventually end
13
00:00:42,000 --> 00:00:43,000
with udacity.
14
00:00:43,000 --> 00:00:46,000
So we can have an arbitrary number of a's, followed by udacity.
15
00:00:46,000 --> 00:00:51,000
This inidicates that this grammar generates an infinite number of possible words.
16
00:00:51,000 --> 00:00:56,000
In this grammar, we can see that every word begins with a root and then a tail.
17
00:00:56,000 --> 00:00:59,000
So what we're going to do to see how many strings this generates is,
18
00:00:59,000 --> 00:01:05,000
go through every possible root there can be and then every tail there can be.
19
00:01:05,000 --> 00:01:09,000
So root can be uda and also boda.
20
00:01:09,000 --> 00:01:14,000
Tail can go directly to cious and city.
21
00:01:14,000 --> 00:01:19,000
But we should also look at this substitution rule that has root going directly to tail.
22
00:01:19,000 --> 00:01:24,000
So you could have a word that's really the same as tail tail,
23
00:01:24,000 --> 00:01:28,000
which adds 2 more possible combinations to what root can be.
24
00:01:28,000 --> 00:01:33,000
This gives us 4 possibilites for root and 2 possibilities for tail,
25
00:01:33,000 --> 00:01:35,000
which means 8 possibilities all together.
26
00:01:35,000 --> 00:01:38,000
This grammar can generate 8 different words.
27
00:01:38,000 --> 00:01:47,000
We know that 8 < infinity, so this grammar does not generate an infinite number of words.
28
00:01:47,000 --> 00:01:51,000
So here we have a grammar that looks a lot like our first one.
29
00:01:51,000 --> 00:01:55,000
However, let's still work it out to see if there's an infinite number of words.
30
00:01:55,000 --> 00:01:57,000
So according to problem, we start with word.
31
00:01:57,000 --> 00:02:00,000
And there's only 1 substitution rule for word.
32
00:02:00,000 --> 00:02:02,000
From pre udacious, we have 2 options.
33
00:02:02,000 --> 00:02:07,000
We could go to super udacious, which gives us one complete word,
34
00:02:07,000 --> 00:02:09,000
or we can do pre super udacious.
35
00:02:09,000 --> 00:02:14,000
You might have already noticed that we can keep substituting the pre with pre super,
36
00:02:14,000 --> 00:02:16,000
and we can keep doing this forever,
37
00:02:16,000 --> 00:02:20,000
and stopping at any point and ending with some number of supers
38
00:02:20,000 --> 00:02:22,000
followed by udacious.
39
00:02:22,000 --> 99:59:59,000
This grammar generates an infinite number of strings.
PK iAzM 4 Problem_Set_6/02-Rabbits_Multiplying_Solution.en.srt1
00:00:00,000 --> 00:00:05,000
In lecture, we said the number of rabbits in a given month was = to
2
00:00:05,000 --> 00:00:11,000
the number of rabbits the previous month + the number of rabbits 2 months ago.
3
00:00:11,000 --> 00:00:15,000
In the new model, we have the same number of growth of rabbits,
4
00:00:15,000 --> 00:00:21,000
but instead we're going to subtract the number of rabbits that are 5 months old
5
00:00:21,000 --> 00:00:24,000
to account for them dying.
6
00:00:24,000 --> 00:00:31,000
Astute readers will know that this doesn't actually model death correctly of rabbits,
7
00:00:31,000 --> 00:00:35,000
but it's a good example for coding a recursive function.
8
00:00:35,000 --> 00:00:38,000
So with this in mind, let's get to the programming.
9
00:00:38,000 --> 00:00:41,000
So the first thing I've done is at our base case,
10
00:00:41,000 --> 00:00:43,000
which was defined in the problem statement.
11
00:00:43,000 --> 00:00:46,000
And if it's not the base case, we're just going to plug in the formula
12
00:00:46,000 --> 00:00:47,000
that we got from the problem statement.
13
00:00:47,000 --> 00:00:50,000
So this may look like it's finished, but there's one issue,
14
00:00:50,000 --> 00:00:57,000
and that is, what we'd do and say n = 3, when 3 - 5 is a negative number,
15
00:00:57,000 --> 00:00:59,000
and we don't have anything to account for that.
16
00:00:59,000 --> 00:01:01,000
We're just going to continue forever, basically,
17
00:01:01,000 --> 00:01:04,000
because we're never going to hit the base case of 1 or 2.
18
00:01:04,000 --> 00:01:06,000
So we need to actually add a second base case.
19
00:01:06,000 --> 00:01:12,000
And our second base case, basically, says if we had a number that's not 1 or 2,
20
00:01:12,000 --> 00:01:18,000
or below a 1 or 2, then we're going to return 0 and not effect the count
21
00:01:18,000 --> 99:59:59,000
of the number of rabbits alive for that month.
PK iAu u 7 Problem_Set_6/03-Spreading_Udaciousness_Solution.en.srt1
00:00:00,000 --> 00:00:07,000
So in this problem, we start out with n number of people with big heads and happy smiles.
2
00:00:07,000 --> 00:00:13,000
And after every hexamester, each one of our happy udacians goes out and asks
3
00:00:13,000 --> 00:00:17,000
spread number of their friends to also take the course.
4
00:00:17,000 --> 00:00:23,000
This process continues as long as the number of udacians is less than the target.
5
00:00:23,000 --> 00:00:27,000
With a little bit of math, you can solve this pretty straightforward,
6
00:00:27,000 --> 00:00:29,000
and you might have done it in middle school or high school,
7
00:00:29,000 --> 00:00:33,000
but we're going to use recursion to solve this problem very easily.
8
00:00:33,000 --> 00:00:39,000
Remember what we're looking for is the number of hexamesters this process goes through
9
00:00:39,000 --> 00:00:41,000
until we reach the target.
10
00:00:41,000 --> 00:00:44,000
I saw on the forms a couple of people were trying to use global variables
11
00:00:44,000 --> 00:00:46,000
that counted recursive calls,
12
00:00:46,000 --> 00:00:51,000
but really that kind of defeats the purpose in the power that we can use in the recursion.
13
00:00:51,000 --> 00:00:54,000
I'm going to show you how to do that right now.
14
00:00:54,000 --> 00:01:01,000
So our base case says that if we've met our target, then we don't need any time to spread
15
00:01:01,000 --> 00:01:05,000
in order to reach the target because we're already there.
16
00:01:05,000 --> 00:01:11,000
Now here I have a + 1 because we're going to say that we're doing 1 iteration
17
00:01:11,000 --> 00:01:14,000
of the udacian spreading process.
18
00:01:14,000 --> 00:01:16,000
Now for the recursive call.
19
00:01:16,000 --> 00:01:18,000
The first thing we need is n.
20
00:01:18,000 --> 00:01:23,000
Well, n is going to be the same thing as last time + how many new people we've gotten,
21
00:01:23,000 --> 00:01:25,000
which is spread x n.
22
00:01:25,000 --> 00:01:30,000
A more succinct way of writing this would be simply (n x (1 + spread).
23
00:01:30,000 --> 00:01:34,000
The spreading rate doesn't change, so we're going to leave that alone.
24
00:01:34,000 --> 00:01:35,000
Our target doesn't change.
25
00:01:35,000 --> 99:59:59,000
And that's it. We're done.
PK iA- - + Problem_Set_6/04-Deep_Count_Solution.en.srt1
00:00:00,000 --> 00:00:05,000
In this problem, given a list that possibly contains lists,
2
00:00:05,000 --> 00:00:08,000
we want to count all of the elements in all of the lists.
3
00:00:08,000 --> 00:00:12,000
So to go through an example, the black list has 2 elements.
4
00:00:12,000 --> 00:00:20,000
This blue list has 3 elements, and the pink list has 2 more elements,
5
00:00:20,000 --> 00:00:22,000
leaving us with the total of 7 elements.
6
00:00:22,000 --> 00:00:26,000
So this is what we want to compute, and we can take a second to think about
7
00:00:26,000 --> 00:00:27,000
how we're going to do that.
8
00:00:27,000 --> 00:00:30,000
We're basically going to start with the length of this list,
9
00:00:30,000 --> 00:00:33,000
and then we're going to iterate through each element
10
00:00:33,000 --> 00:00:36,000
and repeat the process for every sublist.
11
00:00:36,000 --> 00:00:37,000
Let me show you how that works.
12
00:00:37,000 --> 00:00:39,000
We're going to start with our sum at 0,
13
00:00:39,000 --> 00:00:41,000
and then we're going to iterate through each element.
14
00:00:41,000 --> 00:00:44,000
For every element we see, we increase the sum by 1,
15
00:00:44,000 --> 00:00:49,000
and if it's a sublist, we're going to do deepcount on the sublist.
16
00:00:49,000 --> 00:00:52,000
Once we've gone through every list, we're going to return the sum.
17
00:00:52,000 --> 99:59:59,000
[Mouth sound mimicing explosion] I've got to get like a catch word, like pow!
PK iAN . Problem_Set_6/05-Feeling_Lucky_Solution.en.srt1
00:00:00,000 --> 00:00:02,000
In the lucky search problem, we have 3 inputs.
2
00:00:02,000 --> 00:00:08,000
The index, which is a hash table of all the keywords in the pages in which they appear.
3
00:00:08,000 --> 00:00:13,000
We have the ranks, which rank each page based on the URank algorithm
4
00:00:13,000 --> 00:00:15,000
that we discussed in lecture.
5
00:00:15,000 --> 00:00:18,000
And then we have the keyword we are searching for.
6
00:00:18,000 --> 00:00:21,000
The output is going to be the highest ranking page with that keyword.
7
00:00:21,000 --> 00:00:25,000
The steps to solve this can briefly be summarized as follows.
8
00:00:25,000 --> 00:00:29,000
We're going to go through every page that contains the keyword,
9
00:00:29,000 --> 00:00:33,000
and we're just going to find the page with the maximum rank.
10
00:00:33,000 --> 00:00:35,000
So we're going to find a maximum.
11
00:00:35,000 --> 00:00:37,000
It sounds pretty simple, but it's actually a few lines of code.
12
00:00:37,000 --> 00:00:38,000
So let's go right to the ID.
13
00:00:38,000 --> 00:00:43,000
So the first thing we're going to do is get the pages from the index with that keyword.
14
00:00:43,000 --> 00:00:46,000
If there aren't any pages, then we're going to return none,
15
00:00:46,000 --> 00:00:51,000
and if there's at least 1 page, we're going to say for now the bestpage is the first one.
16
00:00:51,000 --> 00:00:55,000
And we're going to iterate through each page in the pages list,
17
00:00:55,000 --> 00:00:57,000
updating our bestpage accordingly.
18
00:00:57,000 --> 00:01:02,000
So if the rank of the candidate page, the page that we're iterating through,
19
00:01:02,000 --> 00:01:07,000
is greater than the rank of our bestpage, we're going to update our bestpage.
20
00:01:07,000 --> 99:59:59,000
Once we're done, we're going to return the bestpage.
PK iA[ [ 3 Problem_Set_6/01-Recursive_Grammars_Solution.en.srtPK iAzM 4 Problem_Set_6/02-Rabbits_Multiplying_Solution.en.srtPK iAu u 7 Problem_Set_6/03-Spreading_Udaciousness_Solution.en.srtPK iA- - + Problem_Set_6/04-Deep_Count_Solution.en.srtPK iAN . 7' Problem_Set_6/05-Feeling_Lucky_Solution.en.srtPK Q/