=== 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 [14:27] anybody here? === nhandler_ is now known as nhandler [16:47] !Q [16:47] Factoid 'Q' not found [17:00] Welcome to the third Ubuntu Algorithm Classes. === 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 [17:00] 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:01] 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] Of course, if you don’t understand something, please ask. [17:02] Algorithm Classes Notes are avaliable here: https://docs.google.com/document/d/1Okbul4AIzQTR4CVGLcx-dmIXkdToNvLiJkIZurxNB8Q/edit [17:02] 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:03] For example, we need to calculate 3^1000000. [17:04] We can do it using naive algorithm, but to this, we need to do 999999 multiplications. [17:04] With exponentiation by squaring, we need only about 20 multiplications. [17:04] You can see that it’s really faster. [17:05] How does it work? It’s quite simple. [17:06] 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] We need only to compute x^(n/2) and then square our result. [17:09] Sorry for that, something was wrong. I'll continue now. [17:09] We need only to compute x^(n/2) and then square our result. [17:10] We can also notice that we can do the same thing with x^(n/2). [17:10] In summary, we need to divide our problem to two smaller problems and do this until they aren’t very small. [17:11] Is that clear? [17:11] This method is called “divide and conquer” and you can use it to solve plenty of problems quickly. [17:12] Another example is binary search - this algorithm was explained during last classes. [17:13] How can we write this algorithm as a code in your favourite programming language? Have you got any ideas? [17:16] We can write this algorithm as a recursive function. [17:17] Our function will receive two variables - x and n. Of course we want to compute x^n. [17:18] I will call this function power(x, n). [17:18] After starting a function, we need to check if n = 0. If it does, power function should return 1. [17:19] If n is odd, we should return x * power(x, n - 1). It means that x^n = x * x^(n - 1). [17:19] Else, if n is even, we create another variable. I will name it a. [17:20] Value of a will be: power(x, n / 2). [17:20] After calculating a, function should return a * a. [17:21] If something isn't clear, you can ask: #ubuntu-classroom-chat [17:22] 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] Here is an example of C++ code for this algorithm: http://j.mp/KyQ4SC [17:25] I'm very, very sorry about this, but I have no idea why it's disconnecting me. [17:26] I explained almost everything, but there is still one thing about this algorithm. [17:26] When you see this code, you probably notice “% Q” at the end of some lines. In C++, ‘%’ is an operator for modulo. [17:27] Why we need modulo here and what is Q? [17:28] We need modulo, because numbers computed by this functions will be probably very big - probably bigger than long long’s range. [17:28] Q should be a very big prime number, for example 100000007. [17:29] 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] Of course if our result is smaller than Q, it will be correct. [17:31] 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:32] I won’t explain it now, but you can read its code in notes. [17:32] 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:35] I don't see any questions there. [17:35] So I'll start explaining adjacency lists. [17:35] 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:39] 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] 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:44] 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:45] An example is shown in algorithm classes notes as a table. [17:45] Here is an example of simple C++ program: http://j.mp/KyWL7a [17:46] It reads a list of edges and creates an adjacency list for this graph. [17:46] Do you have any questions about using adjacency lists? Or maybe about anything else about Ubuntu Algorithm Classes Session 3? [17:49] Nothing? [17:50] There are 10 minutes remaining in the current session. [17:51] 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:52] Thank You Lerhond [17:55] There are 5 minutes remaining in the current session. [18:00] Time is over. Thank you again for taking part in the classes. [18:00] Logs for this session will be available at http://irclogs.ubuntu.com/2012/05/25/%23ubuntu-classroom.html === 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 || [18:07] ¡