Tag: Artificial Intelligence

Big-O Notation

Hello again. Today, let’s take a look at a fundamental part of algorithms – run time. The question that big O notation tries to figure out is ‘How long will it take for something to happen?’ What you’re trying to achieve with big O notation is to get an estimate of how long it will take to accomplish a certain task that the program is trying to do based on how big the data it is handling is. Let’s imagine it this way-

Suppose my friend and I live close to each other.

Yeah the neighborhood sucks, but the rent is pretty nice.

Suppose one day I find a pirated movie online, and I want to send him the file (sure). Both of our internet connections are really, really slow cause it’s cold and somehow that seems to affect the router. Now, if the movie is really long, like upwards of 90 minutes, sending it over the internet is going to be really slow. Both of us have stuff to do later, so we can’t wait that long. How will we both enjoy pirated movies together then? Obviously we can’t watch it separately.

One solution to this is that I could simply get the movie on a USB, and then start walking along the convenient path apparently made only to connect my house to my friend’s house.

Gotta go fast.
(For anyone confused, the thing in my hand is the USB)

Our houses are about 15 minutes apart if I walk fast. That way, I can get the movie to him in time, and we can both enjoy watching it at the same time (right after I run back to my own house).

Here, we say that the data transfer of the movie file itself takes ‘O(n)’ runtime. Here, this is just saying that the bigger the movie file is, the longer it takes to transfer, which is obvious. If I was just sending my friend a 5 second clip, then it would be done much quicker than if I was sending him a 2 hour movie.

However, the second trick of me running to his house will take ‘O(1)’ or constant runtime. In this case, it doesn’t matter how big the movie is. It’s on a USB, so even if it was a 50 hour documentary, the time it takes for me to grab the USB and run to my friends house will be the same. We can see that if the data file is big enough, it is almost always faster for me to run to my friend instead of waiting to send the file, as the time it takes is constant (not affected by input size).

Now let’s look at this in terms of computer commands. Let’s say we have a line of code like this:

int x = 5 + (12*18);

int y = 12+90001;

System.out.print(x+y);

We say that this is constant runtime again, as this will always take the same amount of time to do. There is no variable input here, as each step is decided in constant time. The actual runtime comes out to O(1) for each step, or 3*O(1) in total. However, we drop any constant multiple as it doesn’t affect the final result, meaning the actual runtime is O(1).

Now, I have another line of code that says:

for x in range (0,n) { System.out.print(x);}

We can’t say that this is constant anymore. Sure, the printing step takes constant time, but how many times is that step carried out? According to the loop, it is carried out ‘n’ times, so the runtime is n*O(1), or O(n). This means that the bigger that the variable ‘n’ gets, the longer it will take to finish this task. Even if I add to the code, say :

for x in range (0,n) { System.out.print(x);}

int y = 12+90001;

System.out.println(y);

This does not affect the runtime, as the final runtime is still (2*O(1)) + O(n). Here, the 2*O(1) is irrelevant, and when calculating runtime, we look at the biggest value to find the final runtime. So the runtime for that block of code is still O(n).

There’s many other versions of runtime algorithms that take different amounts of time to finish, but let’s look at one final one.

If I have this line of code:

for x in range (0,n) { for y in range (o,n) { System.out.print(x*y); }}

Here, the loop is not only carried out once, but once for an ‘n’ number of times. The runtime here is literally O(n) * O(n), or O(n^2). This is slower than both of the previous steps, meaning that this last one gets really, really slow as the input is larger.

Image result for graph of runtime
Look at that line grow. Everything above the purple line is dangerously slow.

Take a look at this video by HackerRank to understand more about big O notation. This is a pretty basic overview. There are other cases to consider, like what if you have an ‘if’ statement where one condition takes constant time, and the other takes quadratic time? Here, you would still say the runtime of the algorithm is quadratic, or O(n^2). While doing big O notation, we are always looking for the worst-case runtime of the code. It doesn’t matter how fast it usually is, it’s about how slow it can be. Also, unlike I said earlier, even if for the official runtime, we consider the biggest value in the runtime as the number, the constants and multiples matter in real life. Just make sure you know that big O gives you a worst case scenario.

If you want a best case, look up ‘big omega notation‘, and if you want an average case, look up ‘big theta notation‘. Runtime just helps you get a feel for how long a task will take. Of course, if you work in CS, you’re job is to make sure that the runtime is as fast as possible, so work on improving it piece by piece. On a side note, don’t run with a USB stick in your hand. It looks suspicious. Next week, we’ll look at another concept, maybe sorting. Until then, good luck.

Neural Networks

With AIs developing as fast as they are, today let’s look at how a well-made AI can make a decision. In the end, the goal of the AI is to take an input, run whatever process it wants on the data and use the data to make a decision. Neural networks try to emulate actual thinking in the computers (Very Terminator-esque, right?) and can be used to play games or even predict illnesses in hospitals. To do this, the network tries to learn about whatever task by taking in as much input as possible. This input (Whatever you want to tally, from age, to SAT scores, to handwriting) becomes a ‘node’ in the network. Try to imagine actual human neurons. Meet Nathaniel.

Now Nathaniel is a special guy. He’s got a lot of friends who like to tell him stuff. Whenever he gets a signal from some of the other neurons, and the signal is strong enough, he passes it on to his own friends.

These are Nathaniel’s friends. They like to keep in touch.

In the brain, the connections in the neurons can be weaker or stronger than others, and the stronger the connection between any two neurons, the stronger the signal is passed between them. Similarly, neural networks “pass on” strong data and values, until they arrive at a result that the user likes.

So let’s visualize a fully developed network. In essence, if you’ve ever tried to make a family tree for yourself, imagine that tree, but on its side. Basically, it is layer after layer of nodes that each connect to the next ‘layer’ and so on, until at the end, the network can have output.

When the network gets any input in the input layer (These are the values that we know), it can use them in value functions, called “Activation Functions”, to try and get a value for the input, which is then passed on through the rest of the layers. The function can be either really simple (Kind of a bad AI if it is though…) or extremely complicated. Each node gets a value, and uses the function to get a number. It then passes the number to each connected node, and on the way, it is multiplied by the ‘weight’ of the connection, or the strength of that particular connection.

So, now that we have a design in mind, we can talk about how the network runs. The network basically works backwards, and tries to figure out what it got wrong. The network checks to see what connection made the output wrong, and then tries to avoid that the next time it runs. As a result, it may take multiple runs for the desired output. There also exist multiple types of neural networks. One kind is the “Feed Forward Neural Network” shown here, passing each value through the rest of the network. However, other types of networks, called “Recurrent Neural Networks” pass the data back into themselves. With Recurrent Networks, you can run programs to make sentences or even write books! (The previous word used matters a lot in a sentence, as it decides what the next word will be).

Well that’s pretty much a general summary of networks. If you want, check out Brandon Rohrer’s video explaining Deep Neural Networks. Also check out Code Bullet on youtube to see flash games made easy with AIs. Neural Networks make it so that the computer can make decisions for itself. As a result, we get swarms of numbers and values that would be too big for humans, which the computer deals with by itself. So let’s see where Neural Networks take us in the future. Until then, good luck.

Resources : towardsdatascience.com, askabiologist.asu.edu