0:00

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

Â example, a traditional algorithms course?

Â So, in my opinion,

Â the traditional algorithms course have the following structure.

Â Okay, here is the problem, write an algorithm for it.

Â Analyze the, the, the, 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 and

Â 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

Â design this course is to try to, to tie all these things together and put it in

Â the broader theme which is what is a computer science used for in many domains.

Â So the way I, I look at, 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 is, if the, 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 friend with person b, and b is friends with person c,

Â okay, c my friend as well?

Â Okay, it's a question of interest to, to social scientists and even beyond that.

Â Not necessarily in terms of friendship, but, you know, 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 to, want back from me?

Â 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 social scientist is going to, to need back from me?

Â And other thing is, I need to start understanding if there

Â are multiple possible solutions, which one does the social scientist prefer?

Â So I go back to the social scientist and

Â say, okay, what is the data that you are going to give me?

Â 2:40

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

Â they say, okay, 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 is also a friend with c, okay.

Â So the first part is that I went back and forth with the social scientist.

Â I understood what they want from me.

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

Â What I'm 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

Â then to analyze 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, it's very important to use our mathematical skills and

Â use knowledge of, of representations to represent the data.

Â So in the case of, again, this friendship question, it makes sense that once the,

Â once the social scientist give me the data that I represent,

Â I represent the data as follows.

Â For every individual, and this is individual 1,

Â individual 2, individual 3, individual 4, individual 5.

Â For example, the social scientist has given me information about

Â five individuals.

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

Â I want to know which pairs of individuals have friendship relationships.

Â 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:22

to my problem like this.

Â And this kind of structure where I have these nodes, circles that I call nodes,

Â and lines between them.

Â This is what we call graph, okay?

Â So graph is a powerful representation.

Â In this case it consists of a set of nodes and a set of edges where every edge

Â corres, links two nodes together to tell me if they are friends or not.

Â This would be the, 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 write this formally, right?

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

Â I have to encode it somehow.

Â And then what, what is the output?

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

Â how many triplets of nodes that have two edges in them,

Â also have a third edge, because this is what transitivity is.

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

Â So here, I need to basically say, I need a quantity q that

Â corresponds or

Â quantifies transitivity in the graph, in the input graph.

Â [SOUND] Okay.

Â Now we have to write this formally.

Â Right?

Â I mean, what is that?

Â Because if I tell a, a, a computer scientist,

Â quantity q that corresponds to transitivity in the input graph.

Â I still haven't described it really well, right?

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

Â that an algorithms 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 an input,

Â will give us that as output.

Â Okay?

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

Â different algorithmic techniques that will help us solve these kinds of problems.

Â 6:46

Okay? And

Â when we write that algorithm we have to reason about it's correctness,

Â we have to reason about it's computational requirement.

Â How fast, how slow, is it feasible to run on, on such a graph?

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

Â What if someone has curated the entire Facebook network?

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

Â If I come up with an algorithm,

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

Â If not, I have to start thinking about these things.

Â 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 and 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,

Â when you are writing the code.

Â The algorithm can be efficient and you might turn it

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

Â But also at the same time 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 skills 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, you know, 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 where did this all started.

Â It started from a, 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 scientists that in 78% of the cases where a is a 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 they 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 and

Â the data and answering the original question.

Â