Experienced Computer Scientists analyze and solve computational problems at a level of abstraction that is beyond that of any particular programming language. This two-part class is designed to train students in the mathematical concepts and process of "Algorithmic Thinking", allowing them to build simpler, more efficient solutions to computational problems. In part 2 of this course, we will study advanced algorithmic techniques such as divide-and-conquer and dynamic programming. As the central part of the course, students will implement several algorithms in Python that incorporate these techniques and then use these algorithms to analyze two large real-world data sets. The main focus of these tasks is to understand interaction between the algorithms and the structure of the data sets being analyzed by these algorithms. Once students have completed this class, they will have both the mathematical and programming skills to analyze, design, and program solutions to a wide range of computational problems. While this class will use Python as its vehicle of choice to practice Algorithmic Thinking, the concepts that you will learn in this class transcend any particular programming language.
What is Algorithmic Thinking?
Loading...
Из курса от партнера Rice University
Algorithmic Thinking (Part 2)
139 оценок
Из урока
Module 3 - Core Materials
Sorting, searching, big-O notation, the Master Theorem
Познакомьтесь с преподавателями
Luay NakhlehAssociate Professor
Computer Science; Biochemistry and Cell Biology
Scott RixnerProfessor
Computer Science
Joe WarrenProfessor
Computer Science
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?
Today, in today's age, the social scientist might say,
I have curated some data, some Facebook data, on thousands of individuals.
Okay?
So they're going to give me some Facebook data you know, accounts for
users, and also there's going to be some information about if user a and
user b are friends on Facebook.
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.
Then, what I have done now, is that I have formulated the input
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.
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.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
