0:01

So I want to thank you, for taking the algorithmic think thinking course with us,

Â you know Joe, Scott and I are all very happy to have had you in the course, and

Â we hope that you learned interesting stuff from the course, we truly believe in

Â the significance and the importance of the material we delivered in this course.

Â As we had mentioned, we had offered this course at Rice University for

Â four years now, and it has been very successful.

Â We offered you a version of that course here and

Â we hope that you also got the same type of material and

Â the same type of experience, that we also offered to Rice students.

Â And I want to summarize briefly what we have,

Â what is this process of algorithmic thinking, that we have been following.

Â And what is it that we have done throughout this course.

Â And as a reminder, you know, I defined algorithmic thinking from the beginning of

Â the course, as a five step process.

Â And that five step process, is really motivated by the way I look at research

Â and the, the, my research involving, domains outside computer science.

Â In particular biology.

Â So the first step in the problems when I'm dealing with a biologist or

Â when I'm working on a problem from biology.

Â Is to understand the problem.

Â What is it that, what is that the biologists wants from me?

Â What is that input, that they're going to provide me.

Â Are they going to give me DNA sequences?

Â Are they going to give me homgeno sequences?

Â Are they going to give me some information about gene expression?

Â Are they going to give me a interaction network?

Â So what is it that they are going to give me, and what is it that they want from me?

Â One, the first, when I understand all these details,

Â what is it that they want to give, what is it that they want to, to get back?

Â Now I formulate the problem, and this is where math, comes into the picture.

Â The formulation, the problem formulation, which is the second step in

Â algorithmic thinking, is really mathematics, more than algorithms.

Â Here we have to use our skills,

Â in mathematics to represent the problem cleanly.

Â For example, if the biologist has given me DNA sequences, I have to say,

Â that these sequences can be best represented as strings, right, which

Â are basically mathematical structures, that we have talked about, okay?

Â We will present these as strings.

Â I have to define some sort of a mathematical criterion that says,

Â what are the, the constraints on these strings to make them DNA strings,

Â what are the constraints on the output, in terms of what the biologist wants,

Â as a feasible solution, and what is an optimal criterion.

Â If a biologist wants a good, solution, what makes a solution good, right?

Â We have to define that mathematically, so that an algorithm can run,

Â 3:03

We can, the first thing that we think about,

Â is, okay what algorithmic strategies are out there.

Â Are, is the problem we are dealing win, I mean,

Â with amenable to some of these strategies, or

Â do we need to come up with a new algorithm or a new strategy to solve the problem.

Â And this usually one of the most challenging steps in algorithmic thinking,

Â because coming up with an algorithm for

Â a problem from scratch, is not a trivial task.

Â Okay?

Â So, we have see, some of algorithmic techniques.

Â But beyond this course, there are many more advanced courses.

Â Whether they're like traditionally combinatorial, algorithms, or

Â more modern algorithms that deal with statistical inference problems, and so.

Â There are lots of courses out there, that we highly recommend that you take and

Â explore algorithms, beyond what you have seen in algorithmic thinking.

Â Once we come up with an algorithm.

Â 3:54

We make sure it is correct, we analyze its correctness, we analyze its efficiency.

Â We have talked about, running time and asymptotics to make sure that we can,

Â reason about how efficient an algorithm is before we even move to

Â the implementation fees, because as we have discussed in this course,

Â if the running time of an algorithm grows.

Â A symptotic like two to the N, where N is the input size, and

Â you know that the size of the input is going to be on the order of thousands or

Â tens of thousands, you know that that algorithm is not going to be worth,

Â implementing because it's going to, be unfeasible in practice.

Â So, once we have come up with an algorithm, reasoned about it's

Â efficiency and correctness, the fourth step is implementing the algorithm.

Â You have done implementation throughout the, the course with us.

Â Where every algorithm was implemented in a, in a programming language.

Â You had to test it and you have to, to go back and

Â forth between the pseudo code, and the actual implementation.

Â As I said from the beginning.

Â 4:52

One of the interesting things of going from the pseudocode, to the,

Â to the actual code, to the actual implementation, is that that step,

Â presents us with opportunities, but also presents some dangers there.

Â The opportunities, in, in the,

Â in the form that you can actually use your implementation or coding skills to take

Â pseudocode and make, actually, a more efficient implementation of it.

Â Because when we present through the code it's basically we

Â are describing what the algorithm does.

Â Not how it does every step in detail.

Â When we want to present how things are done in detail that's when we

Â go to the actual implementation.

Â And you have seen I hope, throughout the course,

Â is that when we present pseudo code in the homework or wherever.

Â And you are writing the implementation of that pseudo code.

Â In many, many situations, you even made the, the pseudo code more, more efficient.

Â Okay?

Â But the second thing also as I said, there is the danger of

Â going from a correct pseudo code, to an incorrect implementation.

Â And again, you have noticed that in this course that sometimes when

Â you implemented the, the piece of code.

Â Even though the pseudo code is correct, you notice that you had to go through many

Â iterations, of that implementation phase until you got it right, okay?

Â So, the first, the fourth step is, is that implementation of the pseudo code, but

Â it's not a trivial step by any means right?

Â Because, you have to make the implementation efficient.

Â You have to make sure it is correct.

Â And there are, there is a lot of room for efficiency, and there's a lot of room for

Â in-correctness, as well that you have to avoid.

Â After we are done with that, the fifth step in our algorithmic thinking is to

Â take that code, run it on the data and reason about it.

Â And I would say, this is really what distinguishes our course,

Â from a traditional algorithms course, where we had that application part.

Â Where we try to emphasize this notion that,

Â an algorithm is not just a mathematical object that we implement, for fun.

Â Some people do have fun, with coming up with algorithms or implementing them.

Â But usually they are part of a larger application that we are trying to solve or

Â to develop.

Â And the application component in, in the algorithmic thinking.

Â Was designed, to illustrate this notion.

Â So, we wanted you to take that implementation,

Â apply it to actual data set, get an output, and reason about it.

Â And every now and then even make connection to the symptotic analysis and

Â so on that you have done in the theoretical part.

Â Okay?

Â So, again, this is the five step process of algorithmic thinking.

Â Where, we basically understand the problem, formulate the problem,

Â come up with an algorithm, implement the algorithm, and then analyze the,

Â the original data that we were presented with, so that we give solutions.

Â Okay.

Â Algorithmic thinking is a very powerful technique, especially these days when,

Â when computer science is spreading,

Â in terms of applications way beyond traditional computer science.

Â So now we, the community talks about X plus CS, or

Â X plus computer science where X can be any domain.

Â Biology plus computer science,

Â physics plus computer science, social sciences plus computer science.

Â So, algorithmic thinking, is actually everywhere in this fields.

Â Okay?

Â And we highly recommend that, this is just the beginning, that you start if you

Â enjoy it or you like algorithmic thinking, that you start, honing more skills, that

Â will allow you to practice this kind of pro process in practice, which basically

Â means, you need to take more mathematic courses, more algorithm courses and so on.

Â