| === delcoyot1 is now known as delcoyote | ||
| === raju is now known as ubucop | ||
| === bulldog98_ is now known as bulldog98 | ||
| Lilian | test | 15:52 |
|---|---|---|
| bdfhjk | test passed | 15:54 |
| khler_marcus | when does the workshop begin | 16:19 |
| bdfhjk | in 40 minutes | 16:19 |
| khler_marcus | oh, ok | 16:20 |
| khler_marcus | thanks | 16:20 |
| === 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 - Instructors: bdfhjk | ||
| ClassBot | Logs for this session will be available at http://irclogs.ubuntu.com/2012/04/13/%23ubuntu-classroom.html following the conclusion of the session. | 16:59 |
| bdfhjk | Welcome in the first Ubuntu Algorithm Classes! | 16:59 |
| bdfhjk | Please don’t be afraid to ask questions. | 17:00 |
| bdfhjk | if something isn't clear | 17:00 |
| bdfhjk | I like active participants and questions are the important part of classes. | 17:00 |
| bdfhjk | Classes will be splitted into 3 topics. | 17:01 |
| bdfhjk | During first 20 minutes, I will talk about binary search, one of the basic algorithms. | 17:01 |
| bdfhjk | Next 20 minutes we will spend on learning hashing methods, a more advanced topic. | 17:01 |
| bdfhjk | Then, we are changing topic to introduction to artificial intelligence and usage of FANN library in practise | 17:02 |
| bdfhjk | Let’s start with simple example. | 17:02 |
| bdfhjk | Your friend has chosen randomly a number between 0 and 100. You have to guess it. If you tell him a number and this number isn’t same as his one, he tells you if the number you tried is greater or lower than his one | 17:03 |
| bdfhjk | How many questions do You have to ask to guess your friend’s number in the worst case? | 17:03 |
| khler_marcus | 50 | 17:03 |
| Lilian | no | 17:03 |
| bdfhjk | that isn't correct | 17:03 |
| obounaim | log 100 | 17:03 |
| aANKOo | 100 ? | 17:03 |
| Lilian | log100 | 17:03 |
| Lerhond | 100, if you're an idiot | 17:03 |
| bdfhjk | The correct answer is 7. Each correct, smart question will reduce the set of possible answers to a half. | 17:04 |
| bdfhjk | so, In general case, we need only log2K questions to guess | 17:04 |
| Lilian | 100* log 100 | 17:04 |
| khler_marcus | such an small number? how could this be | 17:04 |
| bdfhjk | where k is the upperbound limit to number | 17:04 |
| bdfhjk | This is an idea of binary search | 17:04 |
| bdfhjk | We can use it to solve each problem, where it is easy to test, if correct answer is below tested value or above it. | 17:05 |
| bdfhjk | Every time we ask about state of the element in the middle | 17:05 |
| bdfhjk | Depending on in which half the correct value is, we call this algorithm recursively in suitable range of initial set | 17:05 |
| bdfhjk | How it work? | 17:06 |
| bdfhjk | Below I’m presenting algorithm | 17:06 |
| bdfhjk | int p := 0 (number of first element) | 17:06 |
| bdfhjk | int k := n-1 (number of last element) | 17:06 |
| bdfhjk | while(p<k) { | 17:06 |
| bdfhjk | int sr = (p+k)/2; | 17:06 |
| bdfhjk | if (try(sr) = success) p := sr; | 17:06 |
| bdfhjk | else k := sr-1; | 17:07 |
| bdfhjk | if (k-p = 1 && try(p+1) = success) p++; | 17:07 |
| bdfhjk | else k--; | 17:07 |
| bdfhjk | } | 17:07 |
| bdfhjk | Please pay attention to line | 17:07 |
| bdfhjk | if (k-p = 1 && try(p+1) = success) p++; else k--; | 17:07 |
| bdfhjk | This fragment prevents the infinite loop | 17:07 |
| bdfhjk | It is clear now, how it work? | 17:08 |
| bdfhjk | On notes, we have also a another algorithm | 17:08 |
| bdfhjk | Shorter, but may be more difficult fo understand | 17:09 |
| bdfhjk | where we can forget about infinite loop | 17:09 |
| bdfhjk | This algorithm work, when value is an integer | 17:10 |
| bdfhjk | so what if this is a float number? | 17:10 |
| Lilian | harder to find | 17:10 |
| bdfhjk | If You plan to use binary search to find a float variable | 17:10 |
| bdfhjk | choose an EPS value, a very small number (typical 0,000001) and break loop when k-p < EPS | 17:11 |
| khler_marcus | so sometimes it is impossible? | 17:11 |
| bdfhjk | it depend, if we can ask questions | 17:11 |
| bdfhjk | "One the which side of number x is answer" | 17:12 |
| bdfhjk | if we can ask this type of questions | 17:12 |
| bdfhjk | then it is always possible | 17:12 |
| bdfhjk | if answer is a float | 17:12 |
| bdfhjk | then we can reduce set of possible answer | 17:12 |
| bdfhjk | for example | 17:12 |
| bdfhjk | 0-1 | 17:13 |
| bdfhjk | 0 - 0.5 | 17:13 |
| bdfhjk | 0 - 0.25 | 17:13 |
| bdfhjk | .... | 17:13 |
| bdfhjk | 0.1345 - 0.1346 | 17:13 |
| bdfhjk | and then we know | 17:13 |
| bdfhjk | that the correct answer is about 0.1345 | 17:13 |
| bdfhjk | I hope that is clear enought | 17:14 |
| bdfhjk | it is a simple algorithm | 17:14 |
| bdfhjk | but need some time to understand how it work | 17:14 |
| bdfhjk | In the notes, I wrote about some practical usages of binary search | 17:14 |
| bdfhjk | Often on job interviews for programming, one of questions is to write binary search pseudocode | 17:14 |
| bdfhjk | and one of the common errors is infinite loop | 17:15 |
| bdfhjk | I saw, that we have questions on discussion room | 17:15 |
| bdfhjk | I wrote code as pseudocode | 17:15 |
| bdfhjk | it is used only in books or lecutres | 17:15 |
| bdfhjk | to present idea independent of language | 17:16 |
| ClassBot | jsjgruber-l84-p asked: Where will we find the ntes? | 17:16 |
| bdfhjk | https://docs.google.com/document/d/1CHU5TgXegp6IkRQhx7ok9HFNMPVONiWojbkIgfdFJrQ/edit | 17:16 |
| bdfhjk | here | 17:16 |
| ClassBot | raju asked: where we can use this / area of usage ? I am pretty new to this | 17:16 |
| bdfhjk | Please look at notes | 17:17 |
| bdfhjk | We can use this in finding value in sorted set | 17:17 |
| bdfhjk | but not only | 17:18 |
| bdfhjk | for example I often use binary search method in debugging | 17:18 |
| bdfhjk | trying to find where I have a bug | 17:18 |
| bdfhjk | I put assertsa | 17:18 |
| bdfhjk | 'asserts | 17:18 |
| bdfhjk | always in the middle of code, where I may find my bug | 17:19 |
| ClassBot | khler_marcus asked: Works this with characters too? | 17:19 |
| bdfhjk | Yes, it work for integers, floats, chars | 17:20 |
| bdfhjk | and any datatype | 17:20 |
| bdfhjk | with '>' operator - which we can compare, that the first is below/under the second | 17:21 |
| bdfhjk | I think that is all about binary search | 17:21 |
| bdfhjk | Do You have any questions? | 17:21 |
| bdfhjk | I don't see | 17:22 |
| bdfhjk | so | 17:22 |
| bdfhjk | The second topic is hashing methods | 17:22 |
| bdfhjk | In hashing, we are going to reduce amount of data (something like compressing it), in a determinist way | 17:22 |
| bdfhjk | We assume, that each equal part of data always have equal hash | 17:22 |
| bdfhjk | There is no return way. We can’t revert hashing. | 17:23 |
| bdfhjk | We lose our initial data, but we gain something more useful in some cases. | 17:23 |
| bdfhjk | A hash is usually a number like 1231432241 | 17:23 |
| bdfhjk | The most important thing is, that we can compare hashes and if they are equal - we know, that corresponding data is equal. | 17:23 |
| bdfhjk | There is a small issue, which I describe later | 17:24 |
| bdfhjk | but in the most cases we can assume that | 17:24 |
| bdfhjk | We may use hashing in many areas, but today we limit it to hashing words / sequence of chars . Also we may store different information in hashes. | 17:24 |
| bdfhjk | I will present hashes, which store information about letters and their position in word - so we will be able to compare words | 17:25 |
| ClassBot | raju asked: if we got enough time please explain more about bug finding by using this . | 17:25 |
| bdfhjk | I will answer this question after classes | 17:25 |
| bdfhjk | so please stay online here | 17:25 |
| bdfhjk | " QUESTION : " We lose our initial data, but we gain something more useful in some cases" If we are losting the data means its loss only na , please explain more ," | 17:26 |
| bdfhjk | To make it more visual | 17:26 |
| bdfhjk | think about beautiful landscape | 17:27 |
| bdfhjk | You can make a photo | 17:27 |
| bdfhjk | one or two | 17:27 |
| bdfhjk | then look at both | 17:27 |
| bdfhjk | and say - that is the same place | 17:27 |
| bdfhjk | but in photo | 17:28 |
| bdfhjk | you will lose the real beauty, that can not be captured | 17:28 |
| bdfhjk | but your photo is smaller than landscape | 17:29 |
| bdfhjk | and You are able to put it in the pocket | 17:29 |
| bdfhjk | or share with friends | 17:29 |
| bdfhjk | so You losed some 'data' | 17:29 |
| bdfhjk | but gained some capabilities | 17:29 |
| bdfhjk | We have a few possible ways to implement hashes. I will teach you about one of the most popular storing information about position of chars and their type. | 17:30 |
| bdfhjk | Words are combinations of chars, each char is represented by a small number (ASCII code). | 17:30 |
| bdfhjk | Our hash is defined as s[i] + s[i+1]*p^1 + s[i+2]*p^2 + ... + s[j]*p^(j-i) | 17:31 |
| bdfhjk | where s is the array which contain word | 17:31 |
| bdfhjk | and every element in it is a char | 17:31 |
| bdfhjk | noted as number in ASCII code | 17:31 |
| bdfhjk | p is a small prime number | 17:31 |
| bdfhjk | q is a big prime number | 17:31 |
| bdfhjk | It is quite complicated, why they should be a prime number | 17:32 |
| bdfhjk | I encourage you to think about it, but now I’m only saying, it reduces the probability of collision. | 17:32 |
| bdfhjk | What is the collision? | 17:32 |
| bdfhjk | Sometimes, two different parts of data can be represented by the same hash, and we may think, that parts are the same | 17:33 |
| bdfhjk | Is said, that we define hash as | 17:33 |
| bdfhjk | s[i] + s[i+1]*p^1 + s[i+2]*p^2 + ... + s[j]*p^(j-i) | 17:33 |
| bdfhjk | but this may be a very large number | 17:33 |
| bdfhjk | so we will store and calculate it modulo q | 17:34 |
| raju | ooooooooooooyyyyyyyyyyyyyyyyyy | 17:34 |
| bdfhjk | q is a large prime number | 17:34 |
| raju | bdfhjk: sorry for mis type | 17:35 |
| bdfhjk | The greater q, the more potential hashes we can use | 17:35 |
| bdfhjk | but also we need more memory to store it | 17:36 |
| bdfhjk | I ussualy use q = 10^9+33 | 17:36 |
| bdfhjk | we have only 1/q chance for that (if we choose q = 10^9+33, then we may have one collision per 10^9+33 comparation - it is small enough to forget about it in the most cases) | 17:36 |
| bdfhjk | two hashes are identical and parts of data are different | 17:37 |
| bdfhjk | Now, how to use it in practise | 17:37 |
| bdfhjk | For example, we have 10^6 big words, and we want to be able to fast compare lexicographically two of it in logarithmic time of length. We want to figure, which is bigger. That is useful eg. in sorting. | 17:38 |
| bdfhjk | The first step is preprocessing - calculate hashes for each suffix | 17:38 |
| bdfhjk | when we know value of hash for each suffix, we can use the formula h(s[i..j]) = (h(i) - p^(j-i+1)*h(j+1)) mod q to calculate hash of fragment starting at char number i, and ending at char number j | 17:39 |
| bdfhjk | It is clear, why this formula work? | 17:39 |
| gang65 | not really | 17:40 |
| gang65 | could you please explain this formula? | 17:40 |
| ClassBot | obounaim asked: what is q? | 17:40 |
| bdfhjk | sorry not this question | 17:41 |
| ClassBot | jsjgruber-l84-p asked: what do you mean by suffix, here? | 17:41 |
| bdfhjk | suffix is a last part of word, beginning at specified position | 17:41 |
| bdfhjk | for example | 17:42 |
| bdfhjk | word: algorithm | 17:42 |
| bdfhjk | sufix | 17:42 |
| bdfhjk | m | 17:42 |
| bdfhjk | hm | 17:42 |
| bdfhjk | thm | 17:42 |
| bdfhjk | gorithm | 17:42 |
| bdfhjk | and algorthm as the longest suffix | 17:42 |
| ClassBot | fasked asked: Why we calculate j+1 at finish, but not j | 17:42 |
| bdfhjk | That isn't true | 17:43 |
| bdfhjk | We calculate hash for part i..j inclusive | 17:43 |
| bdfhjk | but we store in h[i] hash for suffix starting on ith position | 17:43 |
| bdfhjk | so if we want suffix for i..j | 17:44 |
| bdfhjk | then from suffix i | 17:44 |
| bdfhjk | we must deduct suffix j+1 | 17:44 |
| bdfhjk | and we have i..j | 17:44 |
| bdfhjk | because suffix from i | 17:45 |
| bdfhjk | we can denote as | 17:45 |
| bdfhjk | i..j + (j+1)..end | 17:45 |
| bdfhjk | We also multiply the j+1-th suffix | 17:46 |
| bdfhjk | by p^(j-i+1) | 17:46 |
| bdfhjk | because we removing chars at positions starting (j-i+1) after | 17:47 |
| bdfhjk | i | 17:47 |
| ClassBot | Lilian asked: Can you explain if this is the only formula for hashes or we can create one ourselves(but the main idea it to calculate everywhere the hash the same way)? ;) | 17:47 |
| bdfhjk | No | 17:47 |
| bdfhjk | We can create our formula | 17:48 |
| bdfhjk | It depend, what informations we want to store | 17:48 |
| bdfhjk | for example | 17:48 |
| bdfhjk | if we are interested only in number of chars | 17:48 |
| bdfhjk | then we can simply add numbers of chars | 17:48 |
| bdfhjk | then words abc and cba | 17:49 |
| bdfhjk | will have the same hash | 17:49 |
| ClassBot | There are 10 minutes remaining in the current session. | 17:49 |
| bdfhjk | or for example use prefix than suffix | 17:49 |
| ClassBot | jsjgruber-l84-p asked: Does the suffix hash arithmetic work while it is all modulo q? | 17:49 |
| bdfhjk | Yes, we can multiply add and deduct in modulo arithmetic | 17:50 |
| bdfhjk | we can also divide, but we must use fermat's lemat | 17:50 |
| bdfhjk | I can say more after the classes | 17:50 |
| bdfhjk | about dividing hashes | 17:50 |
| bdfhjk | and for calculating p^x | 17:50 |
| bdfhjk | we can use fast_binary_power algorithm | 17:51 |
| ClassBot | fasked asked: everything which allows to access data for O(1) is hash function, isn't it? | 17:51 |
| bdfhjk | The definition of hash isn't strict | 17:52 |
| bdfhjk | Always, when we store informations with data loss, we can say about hashing | 17:52 |
| bdfhjk | when we only reduce size without data losss | 17:53 |
| bdfhjk | 'loss | 17:53 |
| bdfhjk | then we only making a compression | 17:53 |
| bdfhjk | Ok | 17:53 |
| bdfhjk | so to continue | 17:53 |
| bdfhjk | to compare two words, we use binary search to find first char, where there is a difference between two words. | 17:53 |
| bdfhjk | and to test, it two parts of word are the same | 17:54 |
| bdfhjk | we test it's hash | 17:54 |
| bdfhjk | which can be done in O(1) | 17:54 |
| bdfhjk | so overall to compare lexicographically two words | 17:55 |
| bdfhjk | we need O(log s) time | 17:55 |
| bdfhjk | where s is a size of the smallest word | 17:55 |
| bdfhjk | Do You have any questions about hashing methods? | 17:56 |
| ClassBot | gang65 asked: What will happen if we use too small p number (ex. 7), for formula: s[i] + s[i+1]*p^1 + s[i+2]*p^2 + ... + s[j]*p^(j-i) | 17:56 |
| bdfhjk | if we store chars as numbers in ASCII code | 17:57 |
| FeSludge | is hashing different than comparing the ASCII value of the characters? | 17:57 |
| bdfhjk | then they will may be between <65.97> | 17:57 |
| bdfhjk | If I remember this numbers correctly | 17:58 |
| bdfhjk | but at least > 50 | 17:58 |
| bdfhjk | I often use p=13 | 17:58 |
| bdfhjk | becasue if this number is prime | 17:59 |
| bdfhjk | then our hashes always will be different | 17:59 |
| bdfhjk | because if we split they into prime factors | 18:00 |
| bdfhjk | always will be different number of p there | 18:00 |
| bdfhjk | FeSludge : I don't understand your question, could You clarify? | 18:01 |
| bdfhjk | hashing allow us to make it faster | 18:01 |
| bdfhjk | Finally, the last but not the least topic : Introduction to the artificial intelligence | 18:02 |
| bdfhjk | This is not such a difficult subject (in practise usage), as it might seem at first time | 18:03 |
| bdfhjk | Artificial intelligence can be used in a simple way to identify the language of the text | 18:03 |
| bdfhjk | We can also guess the complicated patterns with a small number of possible outcomes | 18:03 |
| bdfhjk | I present, how to make the first mentioned task | 18:04 |
| bdfhjk | Firstly we must define the input and output of artificial neural network (ANN) | 18:04 |
| bdfhjk | The input can be for example the number of occurrences of a each character type in the text, so we have 26 input neurons | 18:05 |
| bdfhjk | Output neurons can be languages, that we are going to detect | 18:05 |
| bdfhjk | These data can be easily counted by a simple program and saved to a file | 18:06 |
| bdfhjk | Next step is to create the ANN - artificial neural network | 18:06 |
| bdfhjk | This can be done using FANN library, by calling | 18:06 |
| bdfhjk | struct fann *ann = fann_create(1, 0.7, 3, 26, 13, 3); | 18:06 |
| bdfhjk | where: | 18:06 |
| bdfhjk | 1 - connection rate (we aren’t pay attention to this argument now, for our purposes it should be 1) | 18:07 |
| bdfhjk | 0.7 - learning rate - defines how aggressive will be the learning algorithm. It depends on our learning data, for this example 0.7 is a good value for relative small amount of training data. | 18:07 |
| bdfhjk | 26, 13, 3 - our layers. First layer is the input. The last one is the output. | 18:07 |
| bdfhjk | What is a (lucky) number 13? | 18:08 |
| bdfhjk | This is the number of neurons in the hidden, middle layer. | 18:08 |
| bdfhjk | In every problem, we must guess, what will be the best amount of hidden neurons - there isn’t any strict rule. For some problems it is useful to make 2,3 or more hidden layers. | 18:09 |
| bdfhjk | The next step is to train our ANN using pregenerated file | 18:09 |
| bdfhjk | fann_train_on_file(ann, "frequencies.data", 200, 10, 0.0001); | 18:09 |
| bdfhjk | First two arguments are easy to guess | 18:09 |
| bdfhjk | Thrid represents the maximal number of epochs - how many times we ‘feed’ our ANN using data from file | 18:10 |
| bdfhjk | Fourth is only for debugging, after how many epochs we want to see report at console. | 18:10 |
| bdfhjk | The last one represent, what is maximal acceptable error on test data, so we can exit training after reaching it. | 18:10 |
| bdfhjk | At this state we have operational ANN | 18:11 |
| bdfhjk | ready for usage | 18:11 |
| bdfhjk | If we want to detect language of text, we must only : | 18:11 |
| bdfhjk | 1. Generate frequencies in this text | 18:11 |
| bdfhjk | float frequencies[26]; | 18:11 |
| bdfhjk | generate_frequencies(argv[1], frequencies); | 18:11 |
| bdfhjk | this function read input text and count frequencies of each char | 18:12 |
| bdfhjk | 2. Run our ANN on this data | 18:12 |
| bdfhjk | float *output = fann_run(ann, frequencies); | 18:12 |
| bdfhjk | 3. Print the best answer | 18:12 |
| bdfhjk | printf max{output} | 18:12 |
| bdfhjk | what represent the biggest number from output values in output layer | 18:13 |
| bdfhjk | remind: each value represents one language | 18:13 |
| bdfhjk | in output layer | 18:13 |
| bdfhjk | And that is all | 18:14 |
| bdfhjk | Do You have any questions about the last part of classes? | 18:14 |
| ClassBot | Lilian asked: printf max{output} - Python? | 18:14 |
| bdfhjk | no, I wrote in pseudocode here | 18:14 |
| Lilian | ow, thx | 18:15 |
| bdfhjk | in c++ we must iterate all answers | 18:15 |
| bdfhjk | and pick the bigger | 18:15 |
| bdfhjk | language with the bigger probability | 18:15 |
| bdfhjk | any other questions? | 18:15 |
| bdfhjk | At the end, I want to say some words about Ubuntu Algorithm Team | 18:16 |
| bdfhjk | Our main goal is to help programmers in problems related with algorithms | 18:16 |
| bdfhjk | You can use our launchpad page https://launchpad.net/algorithms-headquarter to post your problems (as bugs) | 18:16 |
| bdfhjk | Thanks everyone for participation! | 18:17 |
| yoyoo | We thank you. | 18:17 |
| ClassBot | jsjgruber-l84-p asked: So frequencies.data might contain something one line per language containing the frequecy of occurance of each letter? | 18:17 |
| bdfhjk | an example frequencies.data: | 18:18 |
| Lilian | bdfhjk: what do you mean by "problems"? Pseudo implementation of algorithms? | 18:18 |
| bdfhjk | 12 26 3 | 18:18 |
| bdfhjk | 0.103 0.016 0.054 0.060 0.113 0.010 0.010 0.048 0.056 | 18:18 |
| bdfhjk | 0.003 0.010 0.035 0.014 0.065 0.075 0.013 0.000 0.051 | 18:18 |
| bdfhjk | 0.083 0.111 0.030 0.008 0.019 0.000 0.016 0.000 | 18:18 |
| bdfhjk | 1 0 0 | 18:18 |
| bdfhjk | 0.076 0.010 0.022 0.039 0.151 0.013 0.009 0.009 0.081 | 18:18 |
| bdfhjk | 0.001 0.000 0.058 0.024 0.074 0.061 0.030 0.011 0.069 | 18:18 |
| bdfhjk | 0.100 0.074 0.059 0.015 0.000 0.009 0.003 0.003 | 18:19 |
| bdfhjk | 0 1 0 | 18:19 |
| bdfhjk | ... | 18:19 |
| bdfhjk | You can refer on fann article | 18:19 |
| bdfhjk | linked in notes | 18:19 |
| ClassBot | fasked asked: We can post any problems or only discussed here to launchpad? | 18:19 |
| bdfhjk | Becasue we don't have many problems on launchpad, I allow to ask any question now | 18:20 |
| bdfhjk | If in the future it change, then I inform about this | 18:20 |
| bdfhjk | generally | 18:20 |
| bdfhjk | answers is for all algorthim-related questions | 18:20 |
| bdfhjk | bugs in for problems related with concrete program/application | 18:21 |
| bdfhjk | by problems | 18:21 |
| bdfhjk | I mean task | 18:21 |
| bdfhjk | trouble | 18:21 |
| bdfhjk | issue | 18:22 |
| bdfhjk | the thing, which we want to do | 18:22 |
| bdfhjk | Here I used pseudocode | 18:22 |
| bdfhjk | to describe algorithms | 18:22 |
| bdfhjk | sometime I mix it with c++ | 18:23 |
| bdfhjk | but all should be affordable | 18:23 |
| bdfhjk | if not, please ask | 18:23 |
| bdfhjk | http://www.surveymonkey.com/s/MQK9SKP | 18:24 |
| bdfhjk | here is a link to survey | 18:24 |
| bdfhjk | please share your thoughts | 18:24 |
| bdfhjk | about classes | 18:24 |
| ClassBot | There are 5 minutes remaining in the current session. | 18:24 |
| bdfhjk | now we have 5 minutes for any questions | 18:25 |
| bdfhjk | not necessary related with today's topics | 18:25 |
| bdfhjk | I remember, that I had to answer some questions | 18:25 |
| bdfhjk | please remind them | 18:26 |
| fasked | Which topics you want to discuss in the future? | 18:26 |
| bdfhjk | I have some proposition, not decided yet | 18:26 |
| bdfhjk | one of them are matrix | 18:26 |
| bdfhjk | how to calc sum i=0 to n=10^18 | 18:26 |
| Lerhond | interval trees! | 18:26 |
| bdfhjk | 3^i (i+1)(i+2) | 18:27 |
| bdfhjk | Please send your ideas in survey | 18:27 |
| bdfhjk | online judge | 18:27 |
| bdfhjk | You can train coding today's algorithms | 18:27 |
| bdfhjk | solving tasks in online judge | 18:27 |
| fasked | bdfhjk: thanks for class | 18:28 |
| bdfhjk | for each topic we prepared tasks | 18:28 |
| bdfhjk | so if You want to train | 18:28 |
| bdfhjk | try solve they | 18:29 |
| bdfhjk | some are easy, some are hard | 18:29 |
| bdfhjk | binary search while debugging | 18:29 |
| bdfhjk | suppose | 18:29 |
| bdfhjk | You have a program | 18:29 |
| ClassBot | Logs for this session will be available at http://irclogs.ubuntu.com/2012/04/13/%23ubuntu-classroom.html | 18:29 |
| bdfhjk | which crashes at some point | 18:29 |
| === 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 || | ||
| bdfhjk | then to figure where it crashed | 18:30 |
| bdfhjk | You place a line | 18:30 |
| bdfhjk | like printf("Here I'm still alive"); | 18:30 |
| bdfhjk | and run your program | 18:30 |
| bdfhjk | if You see this message | 18:30 |
| bdfhjk | than you know - program isn't crashed before this line | 18:30 |
| bdfhjk | in another case | 18:30 |
| bdfhjk | You know, that bug is after this line | 18:31 |
| bdfhjk | so you can ask questions like in binary search | 18:31 |
| Lilian | bdfhjk: b-tree or fractral-tree ? :) | 18:31 |
| bdfhjk | and every time place this line in the middle of unreliable code | 18:31 |
| bdfhjk | Lilian: b-trees are interesting | 18:31 |
| bdfhjk | but I think | 18:31 |
| Lilian | fractal* | 18:32 |
| bdfhjk | are not often used | 18:32 |
| bdfhjk | are used primarily to read from disk | 18:32 |
| bdfhjk | find an information in 3 or 4 asks | 18:32 |
| Lilian | from a big database... | 18:32 |
| bdfhjk | yes | 18:33 |
| bdfhjk | If You are interested | 18:33 |
| bdfhjk | please read about it in Cormen book | 18:33 |
| bdfhjk | Introduction to Algorithms, Second Edition (9780262032933): Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Books. | 18:33 |
| Lilian | bdfhjk: nice, thx | 18:33 |
| bdfhjk | there are very well described | 18:34 |
| Lilian | bdfhjk: I went to a job interview and I was attacked with a bunch of algorithms to explain... | 18:35 |
| bdfhjk | algorithms are very useful | 18:35 |
| === yofel_ is now known as yofel | ||
| === dduffey_afk is now known as dduffey | ||
| === Resistance is now known as EvilResistance | ||
Generated by irclog2html.py 2.7 by Marius Gedminas - find it at mg.pov.lt!