[MUSIC] This week's project is all about this new data structure called a graph. This week you'll learn about graphs from Mia, but I want to give you a quick overview of what you'll do in your programming assignment this week. So here's an example of a graph, and Mia again will introduce this in much more detail, but basically what a graph is, is a way of representing entities in the world. Those are the circles you see here. And the relationships between them, those are the arrows. So here's a toy example, this is an example you'll get to work with as part of the programming assignment. And here's another. Now in general the graphs we'll be working with have many more circles and many more arrows in them. But these are just some toy examples that you can use to debug your program. What you're going to be doing is you'll be implementing two representations of this graph structure in Java code. That will involve writing code for two different classes that we provide you with as starter code. Next we'll be calculating some properties of these graph structures. So you'll calculate something called the degree sequence of the graph. Again, Mia will explain much more what the degree sequence is. But just to give you some examples here on the two examples that I provided, the degree sequence of this top graph is [4, 4, 2, 0]. While the degree sequence of the bottom graph is [4, 3, 3]. Once you get through this week's videos you'll understand why that's the case. Then the next thing that you'll be doing with these graph structures, is you'll be taking a node, or a labeled circle in the graph, and determining how far you can get from that node in two hops. So for any given labeled circle in the graph how, where do you end up if you take two arrows away from that node? So for example for that top graph, if we start at node 0 in two hops we can get back to node 0, or we can get to node label 3, and that's it. For the bottom graph if we start at node 2, then the only place we can get in two hops is back to node 2, that's it. So again, you'll be writing the code to do both of those calculations. Once you've got the code to do both of those calculations, you can start to explore some real world data, and we provide some data sets for you. So for example, if you look at the degree sequence for some data that represents some streets in La Jolla, near where we are here at UCSD, you can see that it looks very different from the degree sequence for some data that represents United Airlines routes. You can see that in the street data the degree sequences are very small and somewhat uniform. While in the United Airlines routes they're very large at first, but then they drop off very quickly. So what you'll see is that this degree sequence is giving is some measure of the structure of the graph. And these structures are going to make sense once you learn what these are and think about what the data represents. So we hope you'll have fun this week working with and exploring some real-world data. As well as getting warmed up with the graph structures that you'll use throughout this class. But right now, let's get started learning about graphs.