[MUSIC] In this video, what I'm going to try to do is give you a feel for what is expected from you for the project report which is optional this week. So by the end of this video, you should know what we expect in the project report so you can write it up and submit it for peer review. Again, thinking about the big picture in terms of Week 3, this is the optional piece, submitting your mini-project report for review. But the same guidelines for this project report are actually going to apply for the required report you're going to do in Week 5. So we actually have two sample reports in the readings, there are PDFs. If you want, feel free to just look at those sample reports, if you don't feel like you need more of an explanation about what we're looking for. If you do feel like you need more of an explanation, feel free to keep watching, and I'll walk through every single one of the points that we're asking for in the project report. All right, so the first one is to give us an overview of the project. And this should be in the range of one to three sentences and should be describing what you're exploring in your project. So an example, this might just be something along these lines. And I want to keep with one consistent example here. And here we're trying to investigate the community within a social network. And the first part of the project's trying to look at the relationships between a user's friends. Essentially, are they actually all connected together, and a second part of the project, we're looking at identifying subcommittees within the larger social network. So, that's the sample project we're actually going to be talking through in all of these as we continue through the project report. The second piece is data. What data are you going to use for your report? Are you going to be using some of the data that we provided you? Did you find your own data? If you did find your own data, give us some characteristics of the data. How many vertices are there, how many nodes, was there something special about the data that you got? In my case, I just used the UCSD Facebook data with just a main connected component extracted from my project. Describe your question. So right now, we're just focusing on the easier question for the Week 3, but in Week 5, you could be focusing on the larger question. So what question are you trying to answer with your work? And it's totally okay here to do a question as well as an example. So again what I'm trying to look at is for a given user, which of their friends aren't connected as friends yet? And here I actually give an example where if Maria's friends with both Jamaal and Huang, are Jamaal and Huang friends? If they're not, we could actually suggest them as potential friends. And then, probably the largest piece of this write-up is going to be your algorithms, data structures, and the answer to your question. So let's get started first with the data structures you use. Now, what you're going to be focusing on here are the core data structures. You probably have a number of data structures all throughout your project. Focus on the core data structures that actually apply to the problem you're trying to solve right here. So in this example, I laid out my network as a classic graph with an adjacency list. And I was able to just use that graph to solve my easier question. The second piece is focusing on your algorithm. And here, again, you may have many algorithms throughout your project. Focus on the one that's most interesting for the question you're trying to solve with your project. In this case, I'm going to focus on the algorithm I used to solve this easy question. The algorithm is actually fairly straightforward. All I do is I create a list of friends, then I create a list of potential pairs of users that I should be suggesting, and that list is initially empty. And then I'm going to do a really kind of a brute force approach here. I'm going to take that list of all my friends, and I'm going to go for all my list of my friends for each of my friends again in the list. If they're not the same person and they're not already friends, I suggest them as potential friends. And I'll walk through this again when I do the algorithm analysis, but you just want to report, again, the algorithm that was the core to solving the problem you're talking about. The last piece is if you have answers to your question that are interesting, this is a great time to report those. So you may have asked a question about a large data set about who is the most influential person in this social network. You can report back, we actually found that this person was the most influential and they in fact had this many friends, or this many followers. In my case, I actually reported back suggested friends, so I got this huge list back. Don't feel like you're obligated to provide that list. You can just say I got a huge list back, even with small data sets, so I'm just going to omit that from the report. The next step we want you to do is an algorithm analysis. And this is just like you did which we taught you in course two, and we continue doing even through course three, and really is a core part of course four as well. And that is take your algorithm and look at it and figure out what would be the runtime of it. Now in my case, I already kind of talked you through the basic pieces of the algorithm. The core part I'm going to care about is that nested loop. And we notice that on the number of friends I may have, may be all the vertices in the social network, right? So it could be as big as all the vertices, and I'm going to loop over that twice. So it's a nested loop over all vertices. And an interesting part for my project was actually doing the analysis of this second part, so the if statement, the first part of the if statement is actually really basic, our x and y are the same. Okay, I can test that in O(1). But is x already friends with y? That's not so straightforward. It really depends on the data structure that you use. And I'm going to talk about this when we do the reflection here in a few minutes. But because I'd chosen to use a hash table to represent my edges, I could actually do this in O(1). But if I had chosen to do this as a list, this would have actually been, again, an O(V) operation. But because I used a data structure hash table, I end up with an O(1) operation. Now I can do the analysis in this to recognize I have nested loops that are the number of vertices, which means this is O(V squared). In your write up, you're welcome to do exactly this. Just label each of the steps, and give some justification why you did those. You can also just do it in text, and say, here's where I did my analysis. Here are the pieces that I pulled out. This was the interesting piece, and here's what I came up with as my final answer. So the next piece you're going to want to do is test your code. You want to make sure that your code is correct, and how did you do this. So you're going to talk about whether or not you created sample test cases. How big those test cases were, and how you worked out the answer on your own, and then verify that against your algorithm. You'll also talk about how you did some automated testing through various parts, whatever you use to test your code. Whatever you did to convince yourself your code's right, that's what you're going to talk about here. So in our case, we actually just created three small data sets, verified by hand that our answers were right, and then ran them against our algorithm and got the same answer back. Through the process of testing, we actually found a bug. We're reporting back users suggested as friends with themselves on accident. So the testing process actually helped us find a bug and fixed it. And if that happens for you, feel free to talk about that as well. And the last piece is just doing some reflection. And the reflection here is just what worked well, what didn't, what data structures did you choose? How would you have made different choices? And at this point, there's not that much reflection required for the Week 3 report. Because you designed all your data structures with this problem in mind. But I think when you go to Week 5 and you're reporting on your harder problem, it's very likely that data structures that worked well for your easy question aren't going to work as well for your harder question. And here is where you're going to reflect about on what changes are required to make that work. The other piece of the report is your code overview, and within your code overview, we're asking for two things. The first is for you to give us an outline of what classes you used and what their role was. And all you're going to do is just give us a class and give us a brief description, one to three sentences, of what that class does. If you want, you can add some potential methods in there, that were the most meaningful methods for your project. And this is just so that when the person doing peer review reads it, they get a better feel of how you laid out your classes, and then what the structure of your code was. You're going to want to do this for all of your classes. And then the second part of the quota review is to justify why you made the choices you did about the classes that you have. And it's very likely you're going to run into some contentious points. You're going to have said well, you know I could create this extra data structure here. But I've already got this one that might work for this, I'm just going to use one I already have. Or you may have hit this point where you didn't know whether or not to use a hash table or a list. All of that goes into this discussion. In our case, our most contentious point was when I did that return from my suggest friends of friends, I'm suggesting pairings of friends. Now it would have made sense to create another class that's just a pair of vertices to return back. So I return a list of those pairs of vertices. But it turned out my Edge class already had that. So I chose to just return back a bunch of edges which represent the potential friends. But that might make my code a little less readable. So those are the decisions I had to make. Whatever decisions you had to make in your design is what's going to go into this design justification piece. So again, feel free to look at these sample reports that we have in the reading, and good luck with your project.
