0:00

So what is algorithmic thinking?

Â And how does it differ from, for example, a traditional algorithms course?

Â So in my opinion, traditional algorithms course have the following structure.

Â Here's a problem, write an algorithm for it.

Â 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?

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

Â it, that problem is mathematically formulated.

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

Â But who formulated that problem?

Â Where did that problem come from?

Â And why am I solving that problem?

Â 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 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.

Â So if I'm friend with person b, and

Â b is friend with person c, is c my friend as well?

Â It's a question of interest to social scientist 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 scientists 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?

Â So input, output.

Â This is crucial when we develop a 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 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?

Â 3:25

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 representations to represent the data.

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

Â the social scientists 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 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 relationship.

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

Â these two are friends, and so on.

Â These two are friends.

Â 4:59

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 I2 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 transitively in

Â the graph in the input graph.

Â 6:46

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 graph?

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

Â as we're going to run on a graph with billion nodes.

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

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

Â The fourth step, after we have designed algorithm, made sure it is correct,

Â it is efficient and so on, we have to implement it.

Â 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 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.

Â So going from the algorithm to the implementation is not the 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 algorithm correctly.

Â But you also to 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 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%.

Â What does that number mean?

Â I'm telling the social scientist 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.

Â So this is algorithmic thinking, 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.

Â