0:00

So what does algorithmic thinking, and how does it differ from, for example,

Â a traditional algorithm score?

Â So in my opinion, traditional algorithm scores have the following structure, okay.

Â Here's the problem, write an algorithm for it and

Â analyze the algorithm, its correctness, its complexity and so on.

Â But the question is, the broader question is, for us, in computer science,

Â where do we come up with these problems, okay?

Â So, when someone gives me a problem, say, write an algorithm for

Â it, that problem is mathematically formulated,

Â all I need to do is just come up with an algorithm for it.

Â But who formulated that problem?

Â Where did that problem come from, okay?

Â And why am I solving that problem, okay?

Â So algorithmic thinking is that the way we designed this course is to try to

Â tie all these things together and put it in the broader

Â theme which is what is our computer science used for in many domains?

Â So the way I look at algorithmic thinking is basically a five step process.

Â The first process or the first step, sorry.

Â The first step is about getting a problem from a domain expert and

Â trying to understand what that problem is.

Â Just to give you an example, suppose I'm talking to a social scientist and

Â that social scientist tells me that they want to understand if friendship is

Â transitive or in some sense, if it's always the case or

Â how often is it the case that the friend of my friend is also my friend, okay?

Â So if I'm friends with person B, and B is friend with person C,

Â is C my friend as well?

Â Okay, it's a question of interest to social scientists and

Â even beyond that, not necessarily in terms of friendship but

Â this kind of transitivity is of interest in biology for example and other domains.

Â So my first question going back to the social scientist in this case

Â is that what is it that you are going to give me and

Â what is it that you want back from me, right?

Â So input output, this is crucial when we develop an algorithm and

Â when we write a program.

Â What is it that the social scientist is going to give me?

Â What is it that the social scientist going to need back from me?

Â And the other thing is I need to start understanding if there are multiple

Â possible solutions which one does the social scientist prefer?

Â 2:40

And what they want to get back from me, after talking back to them,

Â they say I want you to quantify how often it is the case that if A is

Â a friend with B, and B is a friend with C, then is A also a friend with C?

Â Okay?

Â So the first part is that I went back and

Â forth with a social scientist, I understood what they want from me.

Â What is they're going to provide to me?

Â What am I going to provide to them?

Â Okay, the second step in algorithmic thinking

Â is going to be about formulating that problem, okay?

Â You know, saying Facebook network is basically,

Â this is not something that's well-defined for a computer.

Â If I'm going to write a computer program and enter analyzed data,

Â I cannot say the data is Facebook network.

Â I have to encode it somehow, right?

Â So the second step is going to be about formulating the problem in terms of input,

Â output.

Â So, in this case, its very important to use our mathematical skills and

Â use knowledge of representations to represent the data.

Â So, in the case of again, this friendship question,

Â it makes sense that once the social scientist give me the data

Â that I represent the data as follows, for every individual.

Â This is individual one,

Â individual two, individual three, individual four, individual five.

Â For example, the social signs is giving me information about five individual.

Â In addition I'll tell the social scientist in your data,

Â I want to know which pairs of individuals has friendship relationship.

Â So they can tell me that these two are friends, these two are friends,

Â these two are friends and so on.

Â Okay, these two are friends.

Â 4:35

So graph is a powerful representation,

Â in this case it consists of a set of nodes and a set of edges where

Â every edge links two nodes together to tell me if they are friends or not.

Â So this would be the input.

Â And then I have to say what is the output, okay?

Â Of course, when I say this is the input, in the course, in algorithmic thinking,

Â we will learn how to write this formally, right?

Â So this, I cannot input a drawing like this to the computer.

Â I have to encode it somehow.

Â And then what is the output?

Â Again, for example, they are telling me, quantify for me how many triplets

Â of nodes that have two edges and then also have a third edge?

Â Because this is what transitivity is.

Â If I1 and I 2 are friends, I2 and I4 are friends, are I1 and I4 friends as well?

Â So here, I need to basically say,

Â I need the quantity Q that corresponds or

Â quantifies transitivity in

Â the graph, in the input graph.

Â 5:50

Okay?

Â Now, we have to write this formally.

Â Right I mean, what is that?

Â Because if I tell a computer scientist, quantity Q that corresponds to

Â transitivity in the input graph, I still haven't described it very well, right?

Â So we will be learning in this course how to write this formally so

Â that an algorithm's person can understand exactly what we want.

Â And we will learn how to do this specifically as well, okay?

Â So the second step of algorithmic thinking is being able to formulate the problem in

Â terms of input, output.

Â The third step will be now that we understand how the problem is formulated

Â and structured mathematically, I need to come up with an algorithm for

Â solving this problem in the sense that the algorithm will take this as input

Â will give us that as output, okay.

Â In this course we will be learning about different algorithmic scales or

Â different algorithmic techniques that will help us solve this kind of problem, okay?

Â And when we write that algorithm, we have to reason about its correctness.

Â We have to reason about its computational requirement.

Â How fast?

Â How slow?

Â Is it feasible to run on such a ground?

Â This is a graph with two, four, five nodes.

Â What if someone has curated the entire Facebook network?

Â Today Facebook is estimated to have over a billion nodes.

Â If I come up with an algorithm,

Â is it going to run on a graph with a billion nodes?

Â If not, I have to start thinking about this thing, okay.

Â So the third step is about developing the algorithm to solve the problem,

Â the fourth step after we have designed the algorithm,

Â made sure it is correct, it is efficient and so on, we have to implement it, right?

Â So in this course you will be implementing algorithms in Python.

Â And when we do the implementation it's interesting,

Â because going from the algorithm that we developed in the third step

Â to the implementation is not a simple translation.

Â Because you have to be very careful, the algorithm can be correct, you might make

Â mistake when you are writing the code, the algorithm can be efficient and you might

Â turn it into inefficient implementation when you write the code and so on.

Â But also, at the same, there is a positive side for

Â going from the theoretical description of the algorithm to the implementation.

Â Is that you can even use your programming scales to make the implementation

Â even much faster than the theoretical guarantees of the algorithm, okay?

Â So going from the algorithm to the implementation is not a simple

Â task of someone knowing the syntax of a programming language and

Â translating the algorithm into it.

Â No, you have to use some skills to make sure that you implement the algorithm

Â correctly but you also try to make it even more efficient.

Â So this is the fourth step of writing the program.

Â Then, the fifth step which is the final step,

Â is that I need to remember that when did this all started.

Â It started from a social scientist asking me a question.

Â So now that I have written the computer program I will take that program,

Â take the data set that the social scientist has,

Â analyze it using the program and then give back the scientist the answer.

Â So, in this case, for example, I might say, 78%.

Â Okay? What does that number mean?

Â I'm telling the social scientist that in 78% of the cases where A is friend with B,

Â B is a friend with C.

Â You also have A and C friends, okay?

Â So this is algorithmic thinking in my, the way I define it for

Â this course and the way we'll be using it in this course.

Â Again it's five steps.

Â Understanding the problem is the first formulating the problem is the second.

Â Developing an algorithm is the third.

Â Implementing the algorithm is the fourth.

Â And then the fifth one is running it on the data and

Â answering the original question.

Â