| === mintos is now known as mintos_out | ||
| === mintos_out is now known as mintos | ||
| === VGoff is now known as VGoff_afk | ||
| === VGoff_afk is now known as VGoff | ||
| weelity | anybody here? | 14:27 |
|---|---|---|
| === nhandler_ is now known as nhandler | ||
| Lerhond | !Q | 16:47 |
| ubot2 | Factoid 'Q' not found | 16:47 |
| Lerhond | Welcome to the third Ubuntu Algorithm Classes. | 17:00 |
| === ChanServ changed the topic of #ubuntu-classroom to: Welcome to the Ubuntu Classroom - https://wiki.ubuntu.com/Classroom || Support in #ubuntu || Upcoming Schedule: http://is.gd/8rtIi || Questions in #ubuntu-classroom-chat || Current Session: Ubuntu Algorithm Class 2 - Instructors: bdfhjk, Lerhond | ||
| ClassBot | Logs for this session will be available at http://irclogs.ubuntu.com/2012/05/25/%23ubuntu-classroom.html following the conclusion of the session. | 17:00 |
| Lerhond | Today I’ll explain an algorithm - exponentiation by squaring and adjacency list, which is a way to store a graph in computer’s memory. | 17:01 |
| Lerhond | Of course, if you don’t understand something, please ask. | 17:01 |
| Lerhond | Algorithm Classes Notes are avaliable here: https://docs.google.com/document/d/1Okbul4AIzQTR4CVGLcx-dmIXkdToNvLiJkIZurxNB8Q/edit | 17:02 |
| Lerhond | Ok, I will now start explaining exponentiation by squaring. It’s a very simple algorithm, but it’s also very useful and quite fast. | 17:02 |
| Lerhond | For example, we need to calculate 3^1000000. | 17:03 |
| Lerhond | We can do it using naive algorithm, but to this, we need to do 999999 multiplications. | 17:04 |
| Lerhond | With exponentiation by squaring, we need only about 20 multiplications. | 17:04 |
| Lerhond | You can see that it’s really faster. | 17:04 |
| Lerhond | How does it work? It’s quite simple. | 17:05 |
| Lerhond | It’s easy to notice that each time we need to compute x^n, we can divide it to two smaller problems - we’ll calculate x^(n/2)*x^(n/2). | 17:06 |
| Lerhond | We need only to compute x^(n/2) and then square our result. | 17:06 |
| Lerhond_ | Sorry for that, something was wrong. I'll continue now. | 17:09 |
| Lerhond_ | We need only to compute x^(n/2) and then square our result. | 17:09 |
| Lerhond_ | We can also notice that we can do the same thing with x^(n/2). | 17:10 |
| Lerhond_ | In summary, we need to divide our problem to two smaller problems and do this until they aren’t very small. | 17:10 |
| Lerhond_ | Is that clear? | 17:11 |
| Lerhond_ | This method is called “divide and conquer” and you can use it to solve plenty of problems quickly. | 17:11 |
| Lerhond_ | Another example is binary search - this algorithm was explained during last classes. | 17:12 |
| Lerhond_ | How can we write this algorithm as a code in your favourite programming language? Have you got any ideas? | 17:13 |
| Lerhond | We can write this algorithm as a recursive function. | 17:16 |
| Lerhond | Our function will receive two variables - x and n. Of course we want to compute x^n. | 17:17 |
| Lerhond | I will call this function power(x, n). | 17:18 |
| Lerhond | After starting a function, we need to check if n = 0. If it does, power function should return 1. | 17:18 |
| Lerhond | If n is odd, we should return x * power(x, n - 1). It means that x^n = x * x^(n - 1). | 17:19 |
| Lerhond | Else, if n is even, we create another variable. I will name it a. | 17:19 |
| Lerhond | Value of a will be: power(x, n / 2). | 17:20 |
| Lerhond | After calculating a, function should return a * a. | 17:20 |
| Lerhond | If something isn't clear, you can ask: #ubuntu-classroom-chat | 17:21 |
| Lerhond | This is the end of out function power. If we need to calculate x^n, we simply need to call power(x, n); and everything will work. | 17:22 |
| Lerhond | Here is an example of C++ code for this algorithm: http://j.mp/KyQ4SC | 17:22 |
| Lerhond_ | I'm very, very sorry about this, but I have no idea why it's disconnecting me. | 17:25 |
| Lerhond_ | I explained almost everything, but there is still one thing about this algorithm. | 17:26 |
| Lerhond_ | When you see this code, you probably notice “% Q” at the end of some lines. In C++, ‘%’ is an operator for modulo. | 17:26 |
| Lerhond_ | Why we need modulo here and what is Q? | 17:27 |
| Lerhond_ | We need modulo, because numbers computed by this functions will be probably very big - probably bigger than long long’s range. | 17:28 |
| Lerhond_ | Q should be a very big prime number, for example 100000007. | 17:28 |
| Lerhond_ | If every time we will do something modulo Q, we will never get a negative number and our result will be always correct (of course modulo Q, not a full result - it may be too big to be stored in integer variable). | 17:29 |
| Lerhond_ | Of course if our result is smaller than Q, it will be correct. | 17:29 |
| Lerhond | There is also an iterative version of this algorithm. It’s faster and it’s uses less memory that recursive one, but it’s harder to understand. | 17:31 |
| Lerhond | I won’t explain it now, but you can read its code in notes. | 17:32 |
| Lerhond | This is the end of part about exponentiation by squaring. If something isn’t clear, ask now. In a minute I’ll start explaining adjacency lists. | 17:32 |
| Lerhond | I don't see any questions there. | 17:35 |
| Lerhond | So I'll start explaining adjacency lists. | 17:35 |
| Lerhond | On last Ubuntu Algorithm Classes, another instructor explained how to use an adjacency matrix. It’s a very simple way to store a graph, but is uses a lot of memory and sometimes can be slow. | 17:35 |
| Lerhond | Here is an example of a simple, undirected graph: http://j.mp/KyQ45a I will use it to explain how adjacency lists work. | 17:39 |
| Lerhond | We can see the graph, so we’ll start creating an adjacency list. In the picture we can see that vertex 1 is adjacent to vertices 2 and 5, vertices 1, 3 and 5 are adjacent to vertex 2, etc. | 17:39 |
| Lerhond | This is an idea of doing an adjacency list. We create n lists and list E[i] will contain all nodes adjacent to vertex i. | 17:44 |
| Lerhond | An example is shown in algorithm classes notes as a table. | 17:45 |
| Lerhond | Here is an example of simple C++ program: http://j.mp/KyWL7a | 17:45 |
| Lerhond | It reads a list of edges and creates an adjacency list for this graph. | 17:46 |
| Lerhond | Do you have any questions about using adjacency lists? Or maybe about anything else about Ubuntu Algorithm Classes Session 3? | 17:46 |
| Lerhond | Nothing? | 17:49 |
| ClassBot | There are 10 minutes remaining in the current session. | 17:50 |
| Lerhond | This is everything for today. Thank you for taking part in the classes. Of course, there are 10 minutes left - it's time to ask your qeustions on #ubuntu-classroom-chat ;) | 17:51 |
| bdfhjk | Thank You Lerhond | 17:52 |
| ClassBot | There are 5 minutes remaining in the current session. | 17:55 |
| Lerhond | Time is over. Thank you again for taking part in the classes. | 18:00 |
| ClassBot | Logs for this session will be available at http://irclogs.ubuntu.com/2012/05/25/%23ubuntu-classroom.html | 18:00 |
| === ChanServ changed the topic of #ubuntu-classroom to: Welcome to the Ubuntu Classroom - https://wiki.ubuntu.com/Classroom || Support in #ubuntu || Upcoming Schedule: http://is.gd/8rtIi || Questions in #ubuntu-classroom-chat || | ||
| kimura_cl | ¡ | 18:07 |
Generated by irclog2html.py 2.7 by Marius Gedminas - find it at mg.pov.lt!