| === yofel_ is now known as yofel | ||
| bobweaver | Hello there all hoe everyone is having a great day. I/and others started up something for ubuntu forums and ubuntu wiki. we have a v.small team that takes tutorials from ubuntu forums and we have a tool that I made that converts all the forums html too moin moin markdown. so that it can go up on the wiki fast and othres do not need to type out the whole tutorial. we are thinking about also using it for ask ubun | 11:59 |
|---|---|---|
| bobweaver | comunnity wiki that is | 12:00 |
| bobweaver | looks like on friday @ 1700 there is nothing booked. we have a monthly meetings on the 1st wed of each month and am going to put on agaenda right now to see also what the team thinks. once again thanks for your time. | 12:02 |
| === Mkaysi_ is now known as Mkaysi | ||
| pleia2 | bobweaver: were you asking something earlier? your message is a bit unclear to me (and we do have a classroom session at 17:00 UTC today) | 15:58 |
| === sergio_ is now known as Guest83457 | ||
| === IdleOne is now known as pangolin | ||
| === pangolin is now known as IdleOne | ||
| tomek204 | Hello everyone | 16:56 |
| tomek204 | I'm leading today's classes | 16:57 |
| tomek204 | We have 3 minutes before start | 16:57 |
| === 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, tomek204 | ||
| ClassBot | Logs for this session will be available at http://irclogs.ubuntu.com/2012/04/27/%23ubuntu-classroom.html following the conclusion of the session. | 16:58 |
| tomek204 | Ok | 17:00 |
| tomek204 | I guess we can start | 17:00 |
| tomek204 | Welcome to the second classes. | 17:01 |
| tomek204 | Today’s topic is graphs. | 17:02 |
| tomek204 | First I will introduce the definition of a graph, different types of graphs and their uses. | 17:02 |
| tomek204 | Then I will talk about representing a graph in computer memory. I will show you adjacency matrix in which we can store the graph. | 17:02 |
| tomek204 | The last part will be Depth-first Search algorithm. It’s a simple algorithm used for exploring a graph. | 17:02 |
| tomek204 | If there’s anything You don’t understand, please ask. | 17:03 |
| tomek204 | Ok, let’s start. I think we should begin with a question: What is a graph? | 17:04 |
| barzoslaw | mlp ftw | 17:04 |
| barzoslaw | i have no idea | 17:04 |
| tomek204 | The definition says that graph is a pair of two sets: set of verticles (nodes) and a set of edges. | 17:04 |
| tomek204 | To understand this definition think of a map. | 17:05 |
| tomek204 | There are some cities marked on it. We can compare them to verticles in graph. | 17:05 |
| tomek204 | There are also roads between some pairs of two cities. | 17:06 |
| tomek204 | They can be the edges in a graph representing this city. | 17:06 |
| tomek204 | If there is an edge (u,v), it means you can reach city v from city u. | 17:06 |
| tomek204 | Please tell me if that's clear for you. | 17:07 |
| faroukelabady | Not quite can you illustrate the last sentence more clearly | 17:08 |
| tomek204 | The edges in a graph are marked as (u,v) | 17:08 |
| tomek204 | where u and v are verticles | 17:08 |
| tomek204 | connected by this edge | 17:08 |
| tomek204 | So if such edge exists | 17:09 |
| tomek204 | It means those two verticles (cities in the example) | 17:09 |
| tomek204 | are connected | 17:09 |
| bdfhjk | consider edge as the road between cities | 17:09 |
| tomek204 | That's right, road (u,v) connects city u and city v | 17:11 |
| faroukelabady | I see, so if I say the edge (u,v) then I am talking about the road the connects the u city with the v city | 17:11 |
| tomek204 | Yes | 17:11 |
| tomek204 | Now let’s think of another example: Ubuntu repositories. | 17:11 |
| tomek204 | There are some packages and dependencies between them | 17:12 |
| tomek204 | (You can’t install a package until you install all packages used/needed by the desired one). | 17:12 |
| tomek204 | Can you guess what will verticles and edges represent? | 17:12 |
| tomek204 | vertices* | 17:13 |
| tomek204 | As someone said on chat channel, | 17:14 |
| tomek204 | vertices will represent packages | 17:14 |
| tomek204 | and edges would be dependencies between packages | 17:14 |
| tomek204 | So an edge (u,v) here would mean that to install package u You need package v first. | 17:14 |
| bdfhjk | there important to note is, that we consider edges from u to v | 17:15 |
| bdfhjk | and two edges (u,v) and (v,u) are different | 17:15 |
| tomek204 | Yes, now we consider "one-way" edges | 17:16 |
| tomek204 | Thanks for this | 17:16 |
| tomek204 | There are two main types of graphs: directed graphs and undirected graphs. What is the difference? | 17:17 |
| tomek204 | I will explain it using our first example - map, where nodes are the cities and edges - roads between them. | 17:18 |
| tomek204 | In undirected graph if you have an edge (u,v), You can go from node u to v and from v to u. | 17:18 |
| tomek204 | It’s like a two-way road between two cities on our map. We can travel between these cities both ways | 17:18 |
| tomek204 | We can say that in undirected graph (u,v) and (v,u) are the same edge. | 17:19 |
| tomek204 | Do You have any questions so far? | 17:20 |
| tomek204 | If not, I will now explain directed graph. | 17:21 |
| tomek204 | In directed graph every edge has it’s direction. | 17:21 |
| tomek204 | Just like a one-way road - you can go in one, specified way. | 17:22 |
| tomek204 | An edge (u,v) lets us reach city v from city u, but we can’t go from u to v. | 17:22 |
| tomek204 | Sometimes even in directed graph we can go both ways between two nodes. | 17:23 |
| tomek204 | Can you guess when? | 17:23 |
| tomek204 | We can go both ways between nodes u, v when there are edges (u,v) and (v,u) in the directed graph. | 17:25 |
| faroukelabady | If there is another road from u to another city then v | 17:25 |
| barzoslaw | No shit | 17:25 |
| tomek204 | If you have any question | 17:25 |
| tomek204 | please ask now | 17:26 |
| barzoslaw | Why you all start your sentences with capital letters? | 17:26 |
| barzoslaw | And why your english is so sophisticated? | 17:26 |
| tomek204 | You just did it | 17:26 |
| tomek204 | Now You may wonder what are uses of the graphs. | 17:26 |
| tomek204 | There are quite a lot of them. | 17:26 |
| tomek204 | I already told You about two example uses - representing a map or dependencies in packages repository. | 17:27 |
| tomek204 | Representing map as a graph, we can etc. check if two cities are connected or get the lowest time or price for travelling between them. | 17:27 |
| barzoslaw | And why you end your sentences with dots? | 17:27 |
| tomek204 | There is special kind of graph - tree, which can be also used for many problems, even if some of them don’t seem to be connected with graphs. | 17:28 |
| tomek204 | For example we can build dictionary or search engine using prefix trees. | 17:28 |
| tomek204 | The next thing we will learn is storing a graph in computer memory. | 17:29 |
| tomek204 | I hope You wouldn’t have problem with drawing a graph on a piece of paper. | 17:29 |
| tomek204 | All we need to do is to draw some points which would be the vertices and lines between them. | 17:30 |
| tomek204 | Note that lines in directed graphs have arrows. | 17:30 |
| pleia2 | just a quick reminder, please ask questions in #ubuntu-classroom-chat and start your questions with QUESTION: | 17:31 |
| tomek204 | But how to keep it in computer? | 17:31 |
| tomek204 | Do You know any methods? | 17:31 |
| tomek204 | The thing we need is adjacency matrix. It’s a boolean matrix sized n x n. | 17:32 |
| ClassBot | the_hydra asked: array 2d | 17:32 |
| tomek204 | That's right, sorry that I noticed it now | 17:32 |
| tomek204 | So we need adjacency matrix. | 17:33 |
| tomek204 | Let’s call it Adj[n][n]. For every two nodes u, v, Adj[u][v] = true if there is an edge (u,v) and Adj[u][v] = false otherwise. | 17:33 |
| tomek204 | That's very important part, if You don't understand it please ask. | 17:34 |
| ClassBot | the_hydra asked: array 2d | 17:34 |
| ClassBot | jsjgruber-l82-p asked: Why not just use two lists: V=[a,b,c] and E=[(a,b), (b,c)] | 17:35 |
| tomek204 | It would work | 17:35 |
| tomek204 | But it would be hard to find all edges coming out of a given node | 17:35 |
| ClassBot | faroukelabady asked: can you give a quick reminder on adj in matrix | 17:36 |
| tomek204 | Adj will be the name of our adjacency matrix | 17:36 |
| tomek204 | Please look at the C++ implementation of adjacency matrix: | 17:37 |
| tomek204 | int n, m; bool Adj[1000][1000]; void read(){ cin >> n >> m; for(int i = 0; i < m; i++){ int u, v; cin >> u >> v; Adj[u][v] = true; } } | 17:37 |
| tomek204 | oh, sorry | 17:37 |
| tomek204 | I'll put it line by line | 17:37 |
| tomek204 | int n, m; | 17:37 |
| tomek204 | bool Adj[1000][1000]; | 17:37 |
| tomek204 | void read(){ | 17:38 |
| tomek204 | cin >> n >> m; | 17:38 |
| tomek204 | for(int i = 0; i < m; i++){ | 17:38 |
| tomek204 | int u, v; cin >> u >> v; | 17:38 |
| === bulldog98_ is now known as bulldog98 | ||
| tomek204 | Adj[u][v] = true; }} | 17:38 |
| tomek204 | Function read() reads all the edges | 17:39 |
| tomek204 | and puts them into the adjacency matrix | 17:39 |
| tomek204 | That was the code for directed graphs | 17:40 |
| tomek204 | But how to modify it to work with undirected graphs? | 17:40 |
| tomek204 | Hint: (u,v) and (v,u) are the same edge in undirected graph. | 17:40 |
| tomek204 | The correct answer is: we need to add line: Adj[v][u] = Adj[u][v]; | 17:41 |
| tomek204 | Remember that Adj[u][v] has already "true" value | 17:42 |
| tomek204 | Remember to fill the matrix with “false” value before putting the graph in it. | 17:43 |
| tomek204 | If you would like to practice implementing adjacency matrix, there will soon be a task available. | 17:43 |
| tomek204 | Before we start the last part of classes, DFS, please ask about anything that You don’t understand. | 17:44 |
| tomek204 | I can see no questions | 17:44 |
| tomek204 | Depth-first search is a recursive algorithm. | 17:44 |
| tomek204 | You can explore the graph using it and get many useful information from it. | 17:45 |
| tomek204 | It can be used for solving or generating mazes, checking if two cities are connected or finding dependencies in repository. | 17:45 |
| tomek204 | But how does it work? | 17:46 |
| tomek204 | To learn DFS You need to understand function DFS_visit(u), where u is the vertex given. | 17:46 |
| tomek204 | I'll put a code of this function in a while | 17:46 |
| tomek204 | Please look at the order of visiting vertices in DFS: http://jcop.sourceforge.net/images/user/dfs-animated.gif | 17:47 |
| tomek204 | Here's DFS_visit() function implementation | 17:48 |
| tomek204 | in C++ | 17:48 |
| tomek204 | : | 17:48 |
| tomek204 | http://pastebin.com/w7mTN5vh | 17:48 |
| tomek204 | Do You see how it works? | 17:49 |
| tomek204 | Ok, I can't see any questions | 17:50 |
| tomek204 | There is a possibility that starting from example verticle u You won’t reach all other vertices. | 17:50 |
| tomek204 | To explore entire graph we need to start DFS_visit(i) for every not visited vertex i. | 17:51 |
| tomek204 | Please look at the simple code of DFS() function: | 17:52 |
| tomek204 | http://pastebin.com/CWYmR884 | 17:52 |
| tomek204 | It's just a simple loop through all the vertices | 17:52 |
| tomek204 | which starts DFS_visit(u) for every node u | 17:52 |
| tomek204 | That hasn't been visited yet | 17:52 |
| tomek204 | Note that DFS is a recursive function | 17:54 |
| tomek204 | so it goes deeper and deeper in the graph | 17:54 |
| tomek204 | while it can still find unvisited nodes. | 17:55 |
| tomek204 | I know this algorithm is hard to understand at the beginning | 17:56 |
| tomek204 | So feel free to ask about anything You don't understand. | 17:56 |
| tomek204 | Unless You have any questions, that would be all for today. | 17:57 |
| tomek204 | So I would like to thank You for participating in second Ubuntu Algorithm Classes | 17:58 |
| tomek204 | Oh, wait | 17:59 |
| tomek204 | there is a question | 17:59 |
| ClassBot | faroukelabady asked: it's clear now :) | 17:59 |
| ClassBot | jsjgruber-l82-p asked: So why would I want to visit all unvisited nodes after going through the tree of the nodes I'm interested in? | 17:59 |
| tomek204 | Usually You need to explore full graph | 18:00 |
| tomek204 | But if You know in which nodes You are interested | 18:01 |
| tomek204 | You don't have to go through all the others | 18:01 |
| tomek204 | I had a questuin on chat channel about finding a "head node" | 18:07 |
| tomek204 | Please look at the chat if You're interested | 18:08 |
| tomek204 | I'd like to ask You to complete the survey about this classes | 18:08 |
| tomek204 | http://www.surveymonkey.com/s/RWFQJDX | 18:08 |
| tomek204 | If You want to acces notes or IRC log of this classes | 18:09 |
| tomek204 | Here are the links: | 18:09 |
| tomek204 | http://irclogs.ubuntu.com/2012/04/27/%23ubuntu-classroom.html - log | 18:09 |
| tomek204 | https://docs.google.com/document/d/1jZS1Z6j3xCeZwszMmm6SjUjQah_nouA3yIg1YzxO7yg/edit?pli=1 | 18:09 |
| bdfhjk | https://docs.google.com/document/d/193hpWIj2R7ZDrHZYr0m6qUVHccvsQmpBlkc6tTf1W7s/edit | 18:12 |
| bdfhjk | this doc is correct | 18:12 |
| tomek204 | At the end | 18:14 |
| tomek204 | I would like to thank You once again for participation | 18:14 |
| tomek204 | And I think that's all :) | 18:14 |
| bdfhjk | If You have any question | 18:15 |
| bdfhjk | not necessary connected with today's topic | 18:15 |
| bdfhjk | fell free to ask us | 18:15 |
| bdfhjk | I will stay online about 5 minutes from now | 18:16 |
| ClassBot | There are 10 minutes remaining in the current session. | 18:18 |
| ClassBot | There are 5 minutes remaining in the current session. | 18:23 |
| ClassBot | HH91 asked: is Algorithm Classes Notes 1 still available ? | 18:24 |
| bdfhjk | yes | 18:24 |
| bdfhjk | link: https://docs.google.com/document/d/1CHU5TgXegp6IkRQhx7ok9HFNMPVONiWojbkIgfdFJrQ/edit | 18:24 |
| ClassBot | Logs for this session will be available at http://irclogs.ubuntu.com/2012/04/27/%23ubuntu-classroom.html | 18:28 |
| === 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 || | ||
| === ghostcube_ is now known as ghostcube | ||
Generated by irclog2html.py 2.7 by Marius Gedminas - find it at mg.pov.lt!
