PK iA2 % Problem_Set_1/01-Eulerian_Path.en.srt1
00:00:00,000 --> 00:00:02,000
For this problem, we have a social network.
2
00:00:02,000 --> 00:00:04,000
Tyrone is connected to Marcie.
3
00:00:04,000 --> 00:00:07,000
Marcie is connected to Javier. Javier is connected to Christian. And so on.
4
00:00:07,000 --> 00:00:11,000
We want to know if we started with a Eulerian path
5
00:00:11,000 --> 00:00:14,000
where will it end? Pick the correct answer.
PK iAT . Problem_Set_1/02-Eulerian_Path_Solution.en.srt1
00:00:00,000 --> 00:00:02,000
The correct answer is Marcie.
2
00:00:02,000 --> 00:00:05,000
To answer this question, we first want to look at the number of degrees of each node.
3
00:00:05,000 --> 00:00:07,000
A degree is the number of edges coming in and out.
4
00:00:07,000 --> 00:00:09,000
Tyrone is a node with degree 2.
5
00:00:09,000 --> 00:00:11,000
Marcie a node with degree 3.
6
00:00:11,000 --> 00:00:13,000
Sayo is a node with degree 2.
7
00:00:13,000 --> 00:00:15,000
Christian is a node with degree 2.
8
00:00:15,000 --> 00:00:18,000
Javier, our starting node, is a node with degree 3.
9
00:00:18,000 --> 00:00:20,000
Hubert is a node with degree 2.
10
00:00:20,000 --> 00:00:23,000
As we showed in lecture, in order for there to be an Eulerian path
11
00:00:23,000 --> 00:00:26,000
every node in the network needs to have even degree,
12
00:00:26,000 --> 00:00:28,000
except for the starting and ending nodes, which are odd.
13
00:00:28,000 --> 00:00:31,000
In this example, Javier was our starting node and it had degree 3.
14
00:00:31,000 --> 00:00:34,000
All the other nodes are even, except for Marcie, which has degree 3,
15
00:00:34,000 --> 00:00:37,000
which is odd. Marcie will be our end node.
PK iA> / Problem_Set_1/03-Counting_Eulerian_Paths.en.srt1
00:00:00,000 --> 00:00:02,000
For this question, we have our example social network.
2
00:00:02,000 --> 00:00:08,000
We want to know how many Eulerian paths does the graph have if we start at Javier.
PK iAɔd 8 Problem_Set_1/04-Counting_Eulerian_Paths_Solution.en.srt1
00:00:00,000 --> 00:00:02,000
Fortunately, this graph is small enough
2
00:00:02,000 --> 00:00:05,000
that we can enumerate through all the possible Eulerian paths.
3
00:00:05,000 --> 00:00:09,000
Starting at Javier, we can go through Christian to Sayo,
4
00:00:09,000 --> 00:00:15,000
over to Marcie to Tyrone to Hubert, back to Javier, Marcie--for one.
5
00:00:15,000 --> 00:00:18,000
We can co Javier to Christian to Sayo to Marcie back to Javier
6
00:00:18,000 --> 00:00:22,000
to Hubert to Tyrone finishing at Marcie for our second one.
7
00:00:22,000 --> 00:00:25,000
We can go Javier to Hubert to Tyrone to Marcie to Javier to Christian
8
00:00:25,000 --> 00:00:28,000
to Sayo to Marcie for our third one.
9
00:00:28,000 --> 00:00:31,000
There's a fourth path through, and there's a fifth path.
10
00:00:31,000 --> 00:00:33,000
Finally, there's a sixth path.
11
00:00:33,000 --> 00:00:37,000
That is all the Eulerian paths through the graph starting with Javier.
PK iAA( ( 7 Problem_Set_1/05-Create_Graph_With_Eulerian_Tour.en.srt1
00:00:00,000 --> 00:00:03,000
With this assignment, we want you to write a function createtour
2
00:00:03,000 --> 00:00:05,000
that takes as input a list of nodes and outputs a graph
3
00:00:05,000 --> 00:00:08,000
as a list of tuples representing edges between nodes
4
00:00:08,000 --> 00:00:10,000
that have an Eulerian tour.
5
00:00:10,000 --> 00:00:12,000
For example, if nodes was 1, 2, 3,
6
00:00:12,000 --> 00:00:15,000
one possible solution is a graph that has an edge between 1 and 3,
7
00:00:15,000 --> 00:00:18,000
and edge between 1 and 2, and an edge between 2 and 3.
8
00:00:18,000 --> 00:00:20,000
We've also provided some simple testing code,
9
00:00:20,000 --> 00:00:23,000
which you can use to see if you're function is working properly.
PK iA+
@ Problem_Set_1/06-Create_Graph_With_Eulerian_Tour_Solution.en.srt1
00:00:00,000 --> 00:00:02,000
One simple solution is to take our list of nodes—
2
00:00:02,000 --> 00:00:04,000
let's say we have four of them—
3
00:00:04,000 --> 00:00:06,000
and connect the first one with the second one, the second one with the third one,
4
00:00:06,000 --> 00:00:09,000
the third one with the fourth one, and the last one with the first one.
5
00:00:09,000 --> 00:00:12,000
Then we have, trivially, and Eulerian Tour through this graph.
6
00:00:12,000 --> 00:00:15,000
Here is my code to do what I just described.
7
00:00:15,000 --> 00:00:17,000
I wanted to create a graph that was a little bit more fun
8
00:00:17,000 --> 00:00:19,000
but still had an Eulerian Tour.
9
00:00:19,000 --> 00:00:21,000
Here's another version that introduces a little bit of randomness.
10
00:00:21,000 --> 00:00:23,000
Let's say we start off with 8 nodes.
11
00:00:23,000 --> 00:00:26,000
In the first step, I pick two random nodes and connect them
12
00:00:26,000 --> 00:00:29,000
and choose a random node among the nodes that are connected—say this one—
13
00:00:29,000 --> 00:00:32,000
and connect them and repeat this process until all the nodes are connected.
14
00:00:32,000 --> 00:00:35,000
Then classify all the nodes as being odd or even.
15
00:00:35,000 --> 00:00:38,000
All the nodes in orange have odd degree, and the other two are even.
16
00:00:38,000 --> 00:00:42,000
We then pick a node in the set of nodes with odd degree—say this one—
17
00:00:42,000 --> 00:00:44,000
and connect it with another node that has odd degree.
18
00:00:44,000 --> 00:00:47,000
We'll connect it to that one. These both now have even degree.
19
00:00:47,000 --> 00:00:50,000
We repeat this process—pick this node, connect it with that node.
20
00:00:50,000 --> 00:00:53,000
Now we have two nodes left that have odd degree.
21
00:00:53,000 --> 00:00:55,000
Unfortunately, they're already connected.
22
00:00:55,000 --> 00:00:57,000
What we can do is pick one of the nodes with odd degree
23
00:00:57,000 --> 00:00:59,000
and then randomly pick another node with even degree
24
00:00:59,000 --> 00:01:02,000
that it's not already connected to and connect them. So, maybe this one down here.
25
00:01:02,000 --> 00:01:05,000
Now this new node has odd degree. The one node no longer does.
26
00:01:05,000 --> 00:01:08,000
Now we have two nodes with odd degree that we can connect.
27
00:01:08,000 --> 00:01:11,000
Just to verify that there's an Eulerian tour,
28
00:01:11,000 --> 00:01:16,000
we can go through here over to here connecting up with this guy and there.
29
00:01:16,000 --> 00:01:18,000
Here's my code that does what I just described.
30
00:01:18,000 --> 00:01:22,000
In the first step, we pick two random nodes and add them to the graph.
31
00:01:22,000 --> 00:01:25,000
While we still have unconnected nodes we continue connecting everything.
32
00:01:25,000 --> 00:01:28,000
While we still have odd nodes, we continue connecting the odd nodes.
33
00:01:28,000 --> 00:01:31,000
One question that I'd like you to think about and answer on the forums
34
00:01:31,000 --> 00:01:33,000
is whether this loop is guaranteed to end.
35
00:01:33,000 --> 00:01:35,000
If so, why?
36
00:01:35,000 --> 00:01:37,000
There's a link below in the instructor's comment where I'd like you to post your answer
37
00:01:37,000 --> 00:01:40,000
and read what some other people have to say as well.
PK iA'b4 4 , Problem_Set_1/07-Representing_A_Graph.en.srt1
00:00:00,000 --> 00:00:03,000
In our last question, we used a list of tuples to represent a graph
2
00:00:03,000 --> 00:00:06,000
where each tuple represented and edge between nodes.
3
00:00:06,000 --> 00:00:09,000
We have an edge between node 1 and 2, an edge between node 2 and 4,
4
00:00:09,000 --> 00:00:11,000
and edge between node 5 and 9, etc.
5
00:00:11,000 --> 00:00:13,000
I want you to think about and write a couple sentences
6
00:00:13,000 --> 00:00:16,000
about what are the advantages and disadvantages of representing a graph
7
00:00:16,000 --> 00:00:18,000
as a list of tuples.
8
00:00:18,000 --> 00:00:20,000
There aren't any right or wrong answers to this question.
9
00:00:20,000 --> 00:00:23,000
Just fill in a couple sentences explaining your response.
PK iA9 6 Problem_Set_1/08-Naive_Multiplication_Algorithm.en.srt1
00:00:00,000 --> 00:00:03,000
In this problem we're going to look at the naive multiplication algorithm from lecture.
2
00:00:03,000 --> 00:00:06,000
Let's say we're computing naive( 63, 12).
3
00:00:06,000 --> 00:00:08,000
At some point in the executionâso we'll pause hereâ
4
00:00:08,000 --> 00:00:11,000
we'll have x = 20 and y = 12.
5
00:00:11,000 --> 00:00:14,000
The question is, what is z?
PK iA P P ? Problem_Set_1/09-Naive_Multiplication_Algorithm_Solution.en.srt1
00:00:00,000 --> 00:00:04,000
In lecture we showed that a b = xy + z.
2
00:00:04,000 --> 00:00:06,000
We need to solve for z, substituting in values
3
00:00:06,000 --> 00:00:12,000
for a = 63, b = 12, x = 20, and y = 12, plus z.
4
00:00:12,000 --> 00:00:17,000
Finishing the rest of the math, we get that z = 516.
PK iA5% % ' Problem_Set_1/10-Recursive_Naive.en.srt1
00:00:00,000 --> 00:00:04,000
For this problem, we've written a recursive version of the naive multiplication algorithm.
2
00:00:04,000 --> 00:00:08,000
We want to know how many additions does it take to compute recnaive
3
00:00:08,000 --> 00:00:11,000
of (17, 6) = 102.
PK iA4nQY Y 0 Problem_Set_1/11-Recursive_Naive_Solution.en.srt1
00:00:00,000 --> 00:00:02,000
The answer is 17.
2
00:00:02,000 --> 00:00:04,000
The first time we call recnaive a is 17.
3
00:00:04,000 --> 00:00:06,000
We make one addition and call recnaive again
4
00:00:06,000 --> 00:00:08,000
with 16 as its argument.
5
00:00:08,000 --> 00:00:12,000
We make another addition and call recnaive with 15 as the argument.
6
00:00:12,000 --> 00:00:16,000
This process continues, doing one addition and another call 14 more times
7
00:00:16,000 --> 00:00:20,000
until a = 0, and so we will have made 17 additions.
PK iAk k 8 Problem_Set_1/12-Russian_Multiplication_Algorithm.en.srt1
00:00:00,000 --> 00:00:03,000
For this problem, we'll look at the Russian multiplication algorithm.
2
00:00:03,000 --> 00:00:06,000
Let's say we're computing russian(63, 12).
3
00:00:06,000 --> 00:00:10,000
Let's pause the execution at some point where we have x = 7, z = 84,
4
00:00:10,000 --> 00:00:13,000
and we want to know what y equals.
PK iAŴx A Problem_Set_1/13-Russian_Multiplication_Algorithm_Solution.en.srt1
00:00:00,000 --> 00:00:02,000
To answer this question it was shown in lecture
2
00:00:02,000 --> 00:00:05,000
that a b = x y = z.
3
00:00:05,000 --> 00:00:09,000
Solving for y, we get that 96 = y, and that's our answer.
PK iAv v Problem_Set_1/14-Clique.en.srt1
00:00:00,000 --> 00:00:02,000
For this problem we have a function clique,
2
00:00:02,000 --> 00:00:05,000
and we want to know how many units of time does it take to execute clique(4).
3
00:00:05,000 --> 00:00:09,000
To count the time, count each print statement as 1 unit
4
00:00:09,000 --> 00:00:13,000
and count each time range is evaluated as 1 unit.
PK iAox x ' Problem_Set_1/15-Clique_Solution.en.srt1
00:00:00,000 --> 00:00:03,000
To answer this question, we can just list off each operation in clique
2
00:00:03,000 --> 00:00:05,000
that takes 1 unit of time.
3
00:00:05,000 --> 00:00:11,000
First, we print. Second, we evaluate range of 4, which returns (0, 1, 2, 3)
4
00:00:11,000 --> 00:00:14,000
Then since j is 0 the first time,
5
00:00:14,000 --> 00:00:18,000
we evaluate range of 0 and nothing gets printed.
6
00:00:18,000 --> 00:00:20,000
Next, we loop through again and j = 1,
7
00:00:20,000 --> 00:00:22,000
so we evaluate range of 1, and we print once.
8
00:00:22,000 --> 00:00:26,000
Now, j = 2, and we evaluate range of 2.
9
00:00:26,000 --> 00:00:28,000
In range of two, we print twice.
10
00:00:28,000 --> 00:00:31,000
Going through the loop again, now j = 3.
11
00:00:31,000 --> 00:00:34,000
So, we evaluate the range of 3.
12
00:00:34,000 --> 00:00:36,000
In the inner loop we print 3 times.
13
00:00:36,000 --> 00:00:44,000
We can count this up 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 operations.
14
00:00:44,000 --> 00:00:47,000
So, our answer is 12 units.
PK iAf[ &