Graphs, the Internet, and EverythingAirline routesWord ladderTim Berners-LeeGraphs: Structures and AlgorithmsVocabularyGraph questions/algorithmsDepth, Breadth, other traversalsBreadth first searchCode for breadth firstPseudo-code for depth-first searchEdsger DijkstraWhat does this position entail?What is this about?My recommendations at AmazonAnd again…Finally, …What is the Internet?How does the Internet work?What can be programmed?Schedule students, minimize conflictsOne better scenarioAnother possible scenarioEntscheidungsproblemThe halting problem: writing doesHaltHow to tell if Foo stops on 123 456Consider the class Confuse.javaCan we write Confuse.java?What's a meta catalog? Top 10 sites?Not impossible, but impracticalTravelling SalespersonAre hard problems easy?Theory and PracticeComputer Science in a NutshellCPS 10016.1Graphs, the Internet, and Everythinghttp://www.caida.org/CPS 10016.2Airline routesCPS 10016.3Word ladderCPS 10016.4Tim Berners-LeeI want you to realize that, if you can imagine a computer doing something, you can program a computer to do that. Unbounded opportunity... limited only by your imagination. And a couple of laws of physics.TCP/IP, HTTPHow, Why, What, When?CPS 10016.5Graphs: Structures and AlgorithmsHow do packets of bits/information get routed on the internetMessage divided into packets on client (your) machinePackets sent out using routing tables toward destination•Packets may take different routes to destination•What happens if packets lost or arrive out-of-order?Routing tables store local information, not global (why?)What about The Oracle of Bacon, Erdos Numbers, and Word Ladders?All can be modeled using graphsWhat kind of connectivity does each concept model?Graphs are everywhere in the world of algorithms (world?)CPS 10016.6VocabularyGraphs are collections of vertices and edges (vertex also called node)Edge connects two vertices•Direction can be important, directed edge, directed graph•Edge may have associated weight/costA vertex sequence v0, v1, …, vn-1 is a path where vk and vk+1 are connected by an edge.If some vertex is repeated, the path is a cycleA graph is connected if there is a path between any pair of verticesNYCPhilBostonWash DC20478190268394LGALAXORDDCA$186$186$412$1701$441CPS 10016.7Graph questions/algorithmsWhat vertices are reachable from a given vertex?Two standard traversals: depth-first, breadth-firstFind connected components, groups of connected verticesShortest path between any two vertices (weighted graphs?)Breadth first search is storage expensiveDijkstra’s algorithm is efficient, uses a priority queue too!Longest path in a graphNo known efficient algorithmVisit all vertices without repeating? Visit all edges?With minimal cost? Hard!CPS 10016.8Depth, Breadth, other traversalsWe want to visit every vertex that can be reached from a specific starting vertex (we might try all starting vertices)Make sure we don't visit a vertex more than once•Why isn't this an issue in trees?•Mark vertex as visited, use set/array/map for this–Can keep useful information to help with visited statusOrder in which vertices visited can be importantStorage and runtime efficiency of traversals importantWhat other data structures do we have: stack, queue, …What happens when we traverse using priority queue?CPS 10016.9Breadth first searchIn an unweighted graph this finds the shortest path between a start vertex and every vertexVisit every node one away from startVisit every node two away from start•This is every node one away from a node one awayVisit every node three away from start, …Put vertex on queue to start (initially just one)Repeat: take vertex off queue, put all adjacent vertices onDon’t put a vertex on that’s already been visited (why?)When are 1-away vertices enqueued? 2-away? 3-away?How many vertices on queue?CPS 10016.10Code for breadth firstpublic void breadth(String vertex){ Set visited = new TreeSet(); LinkedList q = new LinkedList(); q.addLast(vertex); visited.add(vertex); while (q.size() > 0) { String current = (String) q.removeFirst(); // process current for(each v adjacent to current){ if (!visited.contains(v)){// not visited visited.add(v); q.addLast(v); } } }}1234567CPS 10016.11Pseudo-code for depth-first searchvoid depthfirst(String vertex){ if (! alreadySeen(vertex)) { markAsSeen(vertex); System.out.println(vertex); for(each v adjacent to vertex) { depthfirst(v); } }}Clones are stacked up, problem? Can we make use of stack explicit?1234567CPS 10016.12Edsger DijkstraTuring Award, 1972Operating systems and concurrencyAlgol-60 programming languageGoto considered harmfulShortest path algorithmStructured programming “Program testing can show the presence of bugs, but never their absence”A Discipline of programming “For the absence of a bibliography I offer neither explanation nor apology”CPS 10016.13What does this position entail?Do you want to build quantitative models millions of people will use, based on data from the world's largest online laboratory? Are you passionate about formulating relevant questions and producing solutions to initially ill-defined problems? Do the challenges and opportunities of terabytes of data excite you? Can you think abstractly and apply your ideas to the real world? Can you contribute to the big picture and are not afraid to handle the details?We are looking for people with the right blend of vision, intellectual curiosity, and hands-on skills, who want to be part of a highly visible, entrepreneurial team http://www.ph.tn.tudelft.nl/PRInfo/jobs/msg00185.htmlCPS 10016.14What is this about?Ideal candidates will have a track record of creating innovative solutions, and typically a Ph.D. in computer science, physics, statistics, or electrical engineering. Significant research experience is desired in fields including active learning, probabilistic graphical models and Bayesian networks, data mining and visualization, Web search and information retrieval, judgment and decision making, consumer modeling, and behavioral economics. What is data mining? What is machine learning?CPS 10016.15My recommendations at AmazonCPS 10016.16And again…CPS 10016.17Finally, …CPS 10016.18What is the Internet?The Internet was originally
View Full Document
Unlocking...