[MUSIC] In this video, we are going to demo the prototype of the project that Christine was talking about and this project really has two phases. The first phase, we're going to think about the different transportation networks that we have when we compare driving around a city on roads in a car as opposed to flying around the world, hopping around from one flight to another. What we'll do is we'll translate these different transportation networks to this data structure of graphs and look at the underlying graph structure and see how it relates to these real world applications using real data. Then the second phase of the project will focus on the router data and the intersections, and think about enriching the data structure that we've implemented in Java. So that we can really start implementing some algorithms that lead to the functionality that you'll be building for the Google Maps like application that you'll do. What we're gonna do now is switch to the code and take a look at the prototype that you will be building. Let's jump in to this Google Maps application, and what we're doing here is using a front end to see the familiar presentation of Google Maps but really leave the algorithmic and data structures questions, at the heart of this course, to you to implement in Java. When we open up the front end application that we've given to you as a prototype, and thank you to the Google Maps API, and our development team here for this course, for creating this, and allowing us to use this functionality. What we've got here is the same features and user experience that you might expect from Google Maps and what we'll do now is take some real world intersection data. We'll stick close to campus here, near UC San Diego and look at the intersections around here, and try to figure out how to plan routes around this region. Now, in this project, you'll be able to fetch data and look at the intersections around your hometown, or any part of the world that you're interested in, and we'll guide you through that process in a little bit. But in order to see the functionality, what we'd like to see here, is that we can pick any of these intersections as our start position for a route that perhaps we're planning to take, and pick any other intersection as our goal. Now we can ask the algorithms that we'll discuss in this class to give us a route from the start to the goal and there it is! Isn't that amazing? Not only do we have a route that goes along the roads, follows the intersections to go from the start to the goal, we can actually ask how this algorithm came up with this route. So we have a visualization available to you for thinking about the nodes in the graph, the underlying graph structure that have to be explored in order to find a path from the start to the goal. Now this visualization isn't usually something that we would expose to a user of a route planning application. But it's very useful for us, as a developer, when we're thinking about the performance of the algorithms that we use for replanning to try to compare the features of different algorithms in terms of how long they take. And perhaps, how far off course they explore before finding the correct path. Now speaking of comparing algorithms, let's look at one other algorithm that we'll be talking about in this class, and we'll see that it also finds the route from the start to the goal destination. But when we visualize the region of the graph that it explores in finding this route, we notice that it explores nodes a little bit differently and in a different order from that first algorithm, the breadth first search algorithm that we saw in the first time that we ran this example. Throughout this course, you'll be thinking about how these algorithms compare and what their relative merits are when we might want to use one rather than the other. What we'll do now is move to the other phase of the course that I mentioned at the very beginning of this video. Not only will this course help you think about transportation networks with real world road data and thinking about route planning in a city, we also want to think about other transportation networks. And other ways in which we might capture their properties in terms of graphs and graph data structures. In this second visualization that we have available for you, what we're going to do is read in the intersection data that we had before in that Google Maps like application. But now we're going to think of these intersections as a graph, a collection of nodes with edges between them and what we'd like to do is think of the abstract structure of this graph. Members of the Google team have helped us build this graph viewer, and we're very grateful to them for doing so. When we read in a data file that has this representation of a graph, what we can see is the number of nodes, edges in the graph and also the degree distribution. Now if you don't know what words like degree and edges means just yet, that's okay, that means you're in the right place. This is the course where you will learn all about it. But what we're going to be doing is connecting the real live data of streets, of flights, of airlines, and these abstract mathematical notions of graphs to understand how the two could inform one another. Just to see that connection once more, let's pick a node and view it on Google Maps and throughout this course, we'll be going back and forth between the applications and the abstract theory, and seeing the power of combining the two. Let's get started.