All language subtitles for 01 - Introduction to Algorithms - Strategies Matter.en

The primary focus here is on intuition. There will be some math and formulas, but focus in the course is on

understanding the main concepts, so you should be able to follow along, even if math is not among your primary interests.

Before I explain anything about the course, let's head straight into a demo, which sole purpose is to

illustrate that the way we implement a solution to a problem can have quite a bit of effect on how the solution performs.

So, consider a popular website and assume that we are provided with a chunk of a log file from the web

servers and are asked to report the number of unique visitors seen in that log file.

In our case, visitors are identified solely by their IP address, so in order to find the answer, we will need

to traverse the log and count the number of different IP addresses.

We will try two approaches.

In the first approach, we will solve the problem on a modern laptop produced in the year of this recording.

I have put some specs in the table here. The lowest Geekbench 3 is a benchmark that I downloaded and

executed on the machine, and the benchmark runs a large variety of tests and produces a final score,

which can be used to measure the actual performance of the machine.

And that machine is going to compete against a relatively old mobile phone equipped with much less capable

hardware, and as you can see, it didn't score nearly as good in the Geekbench test.

So, judging by the numbers, the mobile phone should have no chance in solving our challenge faster than a laptop.

It seems like an unfair competition. Let's see if we can do something about that.

In this example, I have implemented a solution for the iPhone and laptop using the languages Swift and C# respectively.

In pseudo code, the solution looks like this. First, I read the whole log in order to be able to time that part separately.

Next, I run the real solution, which in addition to the log traversal, also counts the IP addresses.

So, first, let's look at how to traverse the log file in Swift. I create an instance of LogReader,

which can provide me with all the log lines from the log file. I set a counter to 0, and then traverse all

lines provided by the LogReader. For each logLine, I extract the IP address without using it, but then this

action be measured as well, and increase the counter, which is returned after the loop.

Here's the C# imitation. Consider to pause the video to convince yourself that these two implementations are practically identical.

One subtle difference, however, is how all the logLines are returned, but as we shall see in a moment,

that difference is insignificant in the total picture. Let's proceed to the actual solution that also counts

the number of unique IP addresses. As you can see, the two methods are very alike.

After creating a logReader, I initialize the container in which I will store all the different IP addresses

I have seen so far. In this case, I use a container called NSMutableSet, which is an implementation of a

so-called HashSet. If the IPs extracted are not already present in the container, they are added,

and otherwise we just proceed with the next logLine. Finally, the function returns the number of elements in the container.

Here is the C# implementation. Again, consider to pause the video to convince yourself that the two

implementations are practically identical. One difference, however, is the choice of container.

Even though that C# also supports HashSets, I have chosen to use a List in C#, which is basically an array

with non-static size. The two containers are very different and we will dive deeper into both of them later

on, but for now, just notice that the only practical difference between the two solutions is the choice of container.

Okay, here are two frames, which in a moment will execute our two solutions simultaneously,

the iPhone app in the left frame, and with Visual Studio loaded with the implementation in the right frame.

Let's start the experiment. Both solutions finished reading the log file very quickly, but the modern

machine won using only 0.02 seconds. The iPhone, however, won the counting using only 5.0 seconds.

I'll pause the recording and return once the laptop finishes.

36.6 seconds.

So the iPhone won this competition, despite being much less capable in terms of hardware.

We used an NSMutableSet on the iPhone, and a List on the laptop.

If we, however, use a HashSet on the laptop instead, which is equivalent to the NSMutableSet on the iPhone,

the laptop solves the problem using only 0.04 seconds. So the main point here is that the choice of

container or data structure really matters when designing a problem solution.

Data structures are structures in which we organize data, and we have just seen how the choice of data

structures can affect performance quite drastically. The term data structure is often mentioned in

conjunction with the term algorithms, which covers ways to do things.

Data structures and algorithms are heavily linked. Data structures typically use some sort of algorithm to

perform their inner organization, and algorithms typically use data structures to store internal states.

In the remainder of this course, we will spend a moment on establishing a kind of language to describe how

data structures and algorithms will perform and to help compare different performance characteristics without

having to actually implement and execute the solutions to compare.

Next, we will take a look at some essential data structures that are good to know, and proceed with

discussing some essential algorithms, and I'll end the course by introducing you to an interesting category

of problems that may seem simple at first, but that are really hard to solve, no matter how clever algorithms

or data structures we use.