0:00

Hi again.

Â And last time when we talked about brute force algorithms,

Â we discussed how the issue of that it is easy to implement a brute force algorithm.

Â Is usually the first type of algorithm we come up with for a problem, and it is easy

Â probably sometimes to, to reason about the correctness of a brute force algorithm.

Â But, to recall the issue, the serious issue of brute force algorithm,

Â which we call it the Achilles hill of this algorithms.

Â Is their efficiency.

Â Okay? So, what do we mean by efficiency?

Â How do we measure efficiency and so on?

Â 0:32

So the, the main point I would like to make now is that,

Â not all correct algorithms are born equal.

Â We can have many algo correct algorithms for the same problem, and

Â they will be different in terms of what we call efficiency.

Â And we usually would choose the most efficient of all algorithms.

Â I say usually because sometimes we are willing to

Â sacrifice a little bit of efficiency for ease of implementation, for example.

Â We can have two algorithms, four of the same problem A and B.

Â A is more efficient than B, a little bit more efficient than B.

Â But B is much easier to implement.

Â Then we might choose, go for b, okay?

Â So, again not all correct algorithms are born equal.

Â They can differ in terms of efficiency.

Â And efficiency plays an important role in algorithm design.

Â So, imagine that you are doing a Google search.

Â Everyone probably has done at least one Google search query.

Â And imagine that when you type the, the term, the,

Â or terms that you are looking for.

Â Google takes three hours to, to give you back the results.

Â Would you use Google?

Â 1:41

The answer is probably no.

Â We are used today, to, to giving the time to Google.

Â Hitting enter or search and

Â it' will give us the results in fractions of a second, or a second.

Â And, if, every time we launch Google, or

Â we ask Google to give us results, search results for a certain term.

Â If it takes three hours, I can guarantee you that Google wouldn't exist today,

Â as a company.

Â At least the way the we know it.

Â Right?

Â So, underlying this technology of Google, the Google search engine.

Â 2:11

Are efficient algorithms that make it useful and applicable in today's life.

Â Because again if underlying google, the Google search engine.

Â If underlying that search engine are algorithms that take forever.

Â To search, to, conduct a search every time we used it,

Â no one would use it and Google wouldn't be the successful company we know it today.

Â So, the question is, what is efficiency, what do we mean by that and again.

Â We had the one of the brute force algorithms that we have introduced,

Â the question is how efficient or inefficient it is.

Â To, to address the issue of efficiency we have to talk about what is efficiency?

Â What do we mean by efficiency?

Â The second thing is how, how do we measure it?

Â In terms of algorithms.

Â And the third question is, how do we use it broadly?

Â We don't want a framework that is very tedious, and

Â very hard to apply, because it's not going to be useful, so

Â we would want some sort of methodology that would allow us.

Â To do efficiency analysis broadly for any algorithm we get,

Â we would want to be able to, to analyze its efficiency very quickly.

Â 3:23

So in our case, in this course, we will focus on two types of efficiency.

Â Or we will measure efficiency of an algorithm in two manners.

Â One is time, the other is space.

Â The first one is that when we have an algorithm, for our

Â specific implementation of the algorithm, how long does that algorithm take?

Â The second one is for

Â that specific implementation of the algorithm, how much memory does it take?

Â OK? Now.

Â 3:52

Both, both concepts are probably easy to understand.

Â When you run the algorithm, or

Â if you have an algorithm, how long it takes in terms of time.

Â But that's not sufficient, it's not sufficient to say my algorithm takes

Â five minutes and it is deficient, because it might take five minutes, but

Â also it might consume terabyte of memory, which does not exist.

Â On any of the laptops or the desktops that we use today.

Â So time itself,

Â is a good metric to measure in terms of efficiency of an algorithm.

Â But also, there is, we have to keep an eye on the amount of memory, or

Â the memory footprint of an algorithm because that's also a crucial issue.

Â If we cannot load the data into the memory.

Â If the, if the algorithm cannot deal with the data all in the memory.

Â That's going to be a crucial issue for

Â the algorithm that will probably trump the, the time efficiency.

Â 4:46

Now, notice that I said, we talk about the time, and

Â memory requirements of a specific implementation of an algorithm.

Â What do I mean by specific implementation?

Â I do not mean.

Â The actual code written in Python or in Java or in C plus plus of the algorithm.

Â No, when we discuss efficiency of algorithms,

Â we do not touch programming languages.

Â We do not touch the actual implementation in a programming languages.

Â What I mean by by implementation, specific implementation of an algorithm is.

Â 5:18

We need to start thinking about what kind of details are assumed in the algorithm.

Â For example, we have seen so far algorithms that run on graphs.

Â We say the input is a graph.

Â But how was the graph represented?

Â Is it an adjacency list?

Â Is it an adjacency matrix?

Â Is it the set of nodes and the set of edges?

Â We will see that the choice of this representation, whether you choose to

Â represent the graph as an adjacency list, or an adjacency matrix, is going to make

Â a big difference sometimes in terms of the amount of time that the algorithm takes.

Â So, here, what I mean by specific implementation is, in this case,

Â for example.

Â When you are, when the input is a graph, the algorithm,

Â is it represented as an adjacency list, or is represented in an adjacency matrix.

Â Still, I am not saying anything about how you are going to

Â implement it using python.

Â However, if you assume an adjacency list, and

Â you analyze running time of the algorithm using an adjacency list.

Â When you write the code, when you implement that algorithm in Python,

Â you need to use a data structure in Python that resembles the adjacency list or

Â corresponds to the adjacency list.

Â Otherwise, the results that we get, or obtain from analyzing running time

Â of the algorithm assuming adjacency list are not going to necessarily translate.

Â To what we will see when we implement the code.

Â Because we have change the representation okay?

Â So to, to repeat.

Â 6:47

When we analyze the running time of an algorithm,

Â we have to make assumption about representations of the data.

Â About implementation details and so on,.

Â That are not necessarily how we are going to do things, or

Â what is the actual syntax in Python, or any programming language we use.

Â But these are necessary,

Â necessary details that we have to know in order to be able to analyze running time.

Â I cannot say just make a,

Â make a blanket statement about how long algorithm is going to take on a graph.

Â Regardless of how it is represented.

Â So, we have to talk about these things, and

Â this is what I mean by a specific implementation of an algorithm.

Â Okay, the as I, as I mentioned there is, there are two kinds of or

Â two metrics for measuring the efficiency of an algorithm at least in our case.

Â Time and memory.

Â Or time and space.

Â How much time does the algorithm take?

Â How much space does the algorithm take?

Â There is often a trade off between the two.

Â You can get the algorithm to become more efficient in terms of time,

Â if you make use of more memory.

Â Or, you can make use of less memory.

Â But it's going to come at expense of losing on the time efficiency.

Â So, this is what we mean when we say there is trade off between time, and

Â space often, okay?

Â In this course, we will focus mostly on the time efficiency.

Â In fact, most of the, most of the course is on algorithms.

Â Most of textbook's on algorithms.

Â Focus on time efficiency of algorithms, because we are having more and

Â more memory today with the, with the, with the computers even with the laptops and

Â desktops that we use.

Â Memory tends to be not the, the issue with many applications.

Â But, at the time or time efficiency is going to be a crucial issue.

Â For example, we have seen now brute force algorithms where memory is

Â not the issue in these algorithms, but time is the issue.

Â So we will, we will never run out of memory by trying to

Â compute the distances between, between pairs of notes in a graph.

Â You're even using our own laptops.

Â But if we don't do an, an, an efficient or an intelligent algorithm for computing

Â these distances, we will, it will, our algorithms will easily take years and

Â tens of years and sometimes even more than that.

Â So, in this course we will focus more on time efficiency and we will.

Â Get the tools, we will focus on how to measure time efficiency,

Â we will use mathematical tools that will give us and

Â idea on how to apply this methodology broadly without having to

Â go through tedious details about how long each line in the algorithm is.

Â