=== yofel_ is now known as yofel
bobweaverHello 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 ubun11:59
bobweavercomunnity wiki that is12:00
bobweaverlooks 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
pleia2bobweaver: 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
tomek204Hello everyone16:56
tomek204I'm leading today's classes16:57
tomek204We have 3 minutes before start16: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
ClassBotLogs 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
tomek204I guess we can start17:00
tomek204Welcome to the second classes.17:01
tomek204Today’s topic is graphs.17:02
tomek204First I will introduce the definition of a graph, different types of graphs and their uses.17:02
tomek204Then 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
tomek204The last part will be Depth-first Search algorithm. It’s a simple algorithm used for exploring a graph.17:02
tomek204If there’s anything You don’t understand, please ask.17:03
tomek204Ok, let’s start. I think we should begin with a question: What is a graph?17:04
barzoslawmlp ftw17:04
barzoslawi have no idea17:04
tomek204The definition says that graph is a pair of two sets: set of verticles (nodes) and a set of edges.17:04
tomek204To understand this definition think of a map.17:05
tomek204There are some cities marked on it. We can compare them to verticles in graph.17:05
tomek204There are also roads between some pairs of two cities.17:06
tomek204They can be the edges in a graph representing this city.17:06
tomek204If there is an edge (u,v), it means you can reach city v from city u.17:06
tomek204Please tell me if that's clear for you.17:07
faroukelabadyNot quite can you illustrate the last sentence more clearly17:08
tomek204The edges in a graph are marked as (u,v)17:08
tomek204where u and v are verticles17:08
tomek204connected by this edge17:08
tomek204So if such edge exists17:09
tomek204It means those two verticles (cities in the example)17:09
tomek204are connected17:09
bdfhjkconsider edge as the road between cities17:09
tomek204That's right, road (u,v) connects city u and city v17:11
faroukelabadyI see, so if I say the edge (u,v) then I am talking about the road the connects the u city with the v city17:11
tomek204Now let’s think of another example: Ubuntu repositories.17:11
tomek204There are some packages and dependencies between them17:12
tomek204(You can’t install a package until you install all packages used/needed by the desired one).17:12
tomek204Can you guess what will verticles and edges represent?17:12
tomek204As someone said on chat channel,17:14
tomek204vertices will represent packages17:14
tomek204and edges would be dependencies between packages17:14
tomek204So an edge (u,v) here would mean that to install package u You need package v first.17:14
bdfhjkthere important to note is, that we consider edges from u to v17:15
bdfhjkand two edges (u,v) and (v,u) are different17:15
tomek204Yes, now we consider "one-way" edges17:16
tomek204Thanks for this17:16
tomek204 There are two main types of graphs: directed graphs and undirected graphs.  What is the difference?17:17
tomek204I will explain it using our first example - map, where nodes are the cities and edges - roads between them.17:18
tomek204In undirected graph if you have an edge (u,v), You can go from node u to v and from v to u.17:18
tomek204It’s like a two-way road between two cities on our map. We can travel between these cities both ways17:18
tomek204We can say that in undirected graph (u,v) and (v,u) are the same edge.17:19
tomek204Do You have any questions so far?17:20
tomek204If not, I will now explain directed graph.17:21
tomek204In directed graph every edge has it’s direction.17:21
tomek204Just 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
tomek204Sometimes even in directed graph we can go both ways between two nodes.17:23
tomek204Can you guess when?17:23
tomek204We can go both ways between nodes u, v when there are edges (u,v) and (v,u) in the directed graph.17:25
faroukelabadyIf there is another road from u to another city then v17:25
barzoslawNo shit17:25
tomek204If you have any question17:25
tomek204please ask now17:26
barzoslawWhy you all start your sentences with capital letters?17:26
barzoslawAnd why your english is so sophisticated?17:26
tomek204You just did it17:26
tomek204Now You may wonder what are uses of the graphs.17:26
tomek204There are quite a lot of them.17:26
tomek204I already told You about two example uses - representing a map or dependencies in packages repository.17:27
tomek204Representing 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
barzoslawAnd why you end your sentences with dots?17:27
tomek204There 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
tomek204For example we can build dictionary or search engine using prefix trees.17:28
tomek204The next thing we will learn is storing a graph in computer memory.17:29
tomek204I hope You wouldn’t have problem with drawing a graph on a piece of paper.17:29
tomek204All we need to do is to draw some points which would be the vertices and lines between them.17:30
tomek204Note that lines in directed graphs have arrows.17:30
pleia2just a quick reminder, please ask questions in #ubuntu-classroom-chat and start your questions with QUESTION:17:31
tomek204But how to keep it in computer?17:31
tomek204Do You know any methods?17:31
tomek204The thing we need is adjacency matrix. It’s a boolean matrix sized n x n.17:32
ClassBotthe_hydra asked: array 2d17:32
tomek204That's right, sorry that I noticed it now17:32
tomek204So we need adjacency matrix.17:33
tomek204Let’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
tomek204That's very important part, if You don't understand it please ask.17:34
ClassBotthe_hydra asked: array 2d17:34
ClassBotjsjgruber-l82-p asked: Why not just use two lists: V=[a,b,c] and E=[(a,b), (b,c)]17:35
tomek204It would work17:35
tomek204But it would be hard to find all edges coming out of a given node17:35
ClassBotfaroukelabady asked: can you give a quick reminder on adj in matrix17:36
tomek204Adj will be the name of our adjacency matrix17:36
tomek204Please look at the C++ implementation of adjacency matrix:17:37
tomek204int 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
tomek204oh, sorry17:37
tomek204I'll put it line by line17:37
tomek204int n, m;17:37
tomek204bool Adj[1000][1000];17:37
tomek204void 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
tomek204Function read() reads all the edges17:39
tomek204and puts them into the adjacency matrix17:39
tomek204That was the code for directed graphs17:40
tomek204But how to modify it to work with undirected graphs?17:40
tomek204Hint: (u,v) and (v,u) are the same edge in undirected graph.17:40
tomek204The correct answer is: we need to add line: Adj[v][u] = Adj[u][v];17:41
tomek204Remember that Adj[u][v] has already "true" value17:42
tomek204Remember to fill the matrix with “false” value before putting the graph in it.17:43
tomek204If 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
tomek204I can see no questions17:44
tomek204Depth-first search is a recursive algorithm.17:44
tomek204You can explore the graph using it and get many useful information from it.17:45
tomek204It 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
tomek204To learn DFS You need to understand function DFS_visit(u), where u is the vertex given.17:46
tomek204I'll put a code of this function in a while17:46
tomek204Please look at the order of visiting vertices in DFS:  http://jcop.sourceforge.net/images/user/dfs-animated.gif17:47
tomek204Here's DFS_visit() function implementation17:48
tomek204in C++17:48
tomek204Do You see how it works?17:49
tomek204Ok, I can't see any questions17:50
tomek204There 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
tomek204Please look at the simple code of DFS() function:17:52
tomek204It's just a simple loop through all the vertices17:52
tomek204which starts DFS_visit(u) for every node u17:52
tomek204That hasn't been visited yet17:52
tomek204Note that DFS is a recursive function17:54
tomek204so it goes deeper and deeper in the graph17:54
tomek204while it can still find unvisited nodes.17:55
tomek204I know this algorithm is hard to understand at the beginning17:56
tomek204So feel free to ask about anything You don't understand.17:56
tomek204Unless You have any questions, that would be all for today.17:57
tomek204So I would like to thank You for participating in second Ubuntu Algorithm Classes17:58
tomek204Oh, wait17:59
tomek204there is a question17:59
ClassBotfaroukelabady asked: it's clear now :)17:59
ClassBotjsjgruber-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
tomek204Usually You need to explore full graph18:00
tomek204But if You know in which nodes You are interested18:01
tomek204You don't have to go through all the others18:01
tomek204I had a questuin on chat channel about finding a "head node"18:07
tomek204Please look at the chat if You're interested18:08
tomek204I'd like to ask You to complete the survey about this classes18:08
tomek204If You want to acces notes or IRC log of this classes18:09
tomek204Here are the links:18:09
tomek204http://irclogs.ubuntu.com/2012/04/27/%23ubuntu-classroom.html - log18:09
bdfhjkthis doc is correct18:12
tomek204At the end18:14
tomek204I would like to thank You once again for participation18:14
tomek204And I think that's all :)18:14
bdfhjkIf You have any question18:15
bdfhjknot necessary connected with today's topic18:15
bdfhjkfell free to ask us18:15
bdfhjkI will stay online about 5 minutes from now18:16
ClassBotThere are 10 minutes remaining in the current session.18:18
ClassBotThere are 5 minutes remaining in the current session.18:23
ClassBotHH91 asked: is Algorithm Classes Notes 1 still available ?18:24
bdfhjklink: https://docs.google.com/document/d/1CHU5TgXegp6IkRQhx7ok9HFNMPVONiWojbkIgfdFJrQ/edit18:24
ClassBotLogs for this session will be available at http://irclogs.ubuntu.com/2012/04/27/%23ubuntu-classroom.html18: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!