Support: Where to start the project design?

Loading...

From the course by University of California San Diego

Advanced Data Structures in Java

878 ratings

University of California San Diego

Advanced Data Structures in Java

878 ratings

Course 3 of 5 in the Specialization Object Oriented Java Programming: Data Structures and Beyond

How does Google Maps plan the best route for getting around town given current traffic conditions? How does an internet router forward packets of network traffic to minimize delay? How does an aid group allocate resources to its affiliated local partners? To solve such problems, we first represent the key pieces of data in a complex data structure. In this course, you’ll learn about data structures, like graphs, that are fundamental for working with structured real world data. You will develop, implement, and analyze algorithms for working with this data to solve real world problems. In addition, as the programs you develop in this course become more complex, we’ll examine what makes for good code and class hierarchy design so that you can not only write correct code, but also share it with other people and maintain it in the future. The backbone project in this course will be a route planning application. You will apply the concepts from each Module directly to building an application that allows an autonomous agent (or a human driver!) to navigate its environment. And as usual we have our different video series to help tie the content back to its importance in the real world and to provide tiered levels of support to meet your personal needs.

From the lesson

Class design and simple graph search

This week you'll get the backbone of your map search engine up and running. In previous courses, including the previous courses in this specialization, you've probably been given most of the classes you needed to complete the assignments. But learning how to design classes from scratch is a key skill that you will need as you become a more sophisticated Java programmer. This week we'll give you the tools you need to create a robust and elegant class design for your map search engine. We'll introduce a similar problem and show you how it can be represented as a graph. Then we'll introduce two core search algorithms: depth-first search and breadth-first search. Finally, we'll turn our graph problem into a set of Java classes. Your task on the programming assignment this week will be to do the same thing, but in the context on the map search engine!

Core: Class Design8:40

When I struggled: If you fail to plan ...1:28

When I struggled: ... but don't forget to start!1:13

In the real world: Planning ahead with design4:31

Core: Refactoring12:12

Support: Where to start the project design?10:04

In the Real World: Why is code refactored?2:37

Meet the Instructors

Leo Porter
Assistant Teaching Professor
Computer Science and Engineering
Mia Minnes
Assistant Teaching Professor
Computer Science and Engineering
Christine Alvarado
Associate Teaching Professor
Computer Science and Engineering

[SOUND] So in this support video, what we're gonna be doing is actually

looking at the class hierarchy as you're gonna be doing for your project.

Now, I first of all wanna say that this is a major spoiler.

So, I encourage you to do this on your own first, or

at least try to do this on your own first, before you watch this video.

But if you want some extra help, or you just want some tips to get started,

feel free to keep watching.

The other thing I wanna mention before we get started is that this is actually

a fairly authentic environment.

So whenever I'm trying to do a major project,

I always do this at my whiteboard.

And my whiteboard is gonna look very much like what we're about to do here,

by the end.

Now I also wanna be quite honest about what my whiteboard looks like.

My whiteboard ends up messy at various points in time.

You almost always have a really clean idea of what you're gonna

do when you start sketching it out and then you make mistakes, or

you notice you make a mistake, but you are working on a code and

you go oh shoot I need access to this from here, but I don't.

How am I gonna get access to it?

And whenever that happens, you end up changing around your class hierarchy.

That kind of refactoring is completely normal and is completely okay.

At various points in time, you may end up having to clean things up a bit, but

it's completely okay to change your code.

All right, so without further ado, let's start diving into how

would you lay out your class hierarchy for the project in this mod, in this week?

So, you have a MapGraph class that's provided to you,

you know the methods that you need right there and all we are gonna do is simply

sketch what should be in this class and what may be in other classes.

And now there may be a temptation really early on

which is to simply put all the information you wanna know in this class.

And the way that you might do that is you might say, okay, well I could keep

say a list of all the vertices, and then for each of the vertices.

I could keep another list which maintains the other vertices that are connected to.

Now I may not sketch that out because pretty quickly you're gonna recognize,

if you take this approach that it's unmanageable.

There's way too much complexity being put in map graph class.

And you need to move this into other classes.

And again that's the main principle of [INAUDIBLE] during your programming.

So what should we keep?

Well it would make a lot of sense to have nodes, or vertices,

in my graphs, potentially have their own class.

And then instead of trying to keep that list of vertices, and

then some other list of things that are connected to it,

we may be able to put that all within say a vertex class.

So let me do that.

We're gonna do then, is add a new class called MapNode,

and the MapNode class is gonna contain a few things.

It's gonna contain the location.

Location of the node.

And this might be a geographic point in the hierarchy that we've given you.

And then, you might also want to maintain other features about it.

Now if we're doing an adjacency list representation what you'll

be really tempted to do is to say well, I should keep a list of more map nodes.

So List MapNodes,

and these are essentially my adjacency nodes.

Now you may keep a list like that and

then what's gonna happen pretty quickly is you're gonna say well,

is it enough for me to know all the other nodes that are adjacent to me?

I know that's how we sketched it out in week 1.

But is all the information about an edge contained just in the start and the end?

Well, not really, right?

What you'd have almost certainly is

essentially the names of the streets are missing, right?

At the very least you're missing names of streets.

So what you do then is say, well maybe I should maintain a list then,

that I'll keep in parallel with the adjacency list at the street names.

And they can be a string for street names.

And the problem there is gonna be maintaining the consistency between these

but let's just say we could do it.

And again kind of a high level with this might look like is, say you had a node,

your node is A at location A and you're connected to B and C.

Well I have to maintain the street names for B and C and

maybe that's Maine and Park.

And I have to make sure that B is always associated with Maine and

the path to C is always associated with Park.

And then I go one more step and I go this isn't everything I need to know.

The edge is not always a straight path from one location to another.

We actually need to know how long it is.

How long is that path on a real road?

Now I have to maintain another list of double

distances and double lengths, which are essentially, how long are these?

So, now I go, okay, well, my distance from A to B on Main Street was 3.2 kilometers,

and my distance from A to C via Park Avenue is 6.7.

And you could actually make this all work this way.

You could have these essentially parallel arrays

that you maintain consistency between.

But what's gonna go wrong here is the second you try to insert something or you

try to move something or you try to remove something, you're gonna make mistakes.

It's gonna be easy to lose the consistency between these.

So even though this looks like a good idea when I first started sketching it out,

this is actually gonna be a mistake, and I'm gonna cross this out,

and I'm gonna start again thinking about this in a more object oriented way.

Be right back.

All right, so

what I've done is I've taken away the essentially wrong direction that I done.

So we'd again try to have our distances, and

we try to have our vertices, and all these things in different parallel rays.

When really we could put them all in one other class, right?

I could just make a class called an edge, that would maintain all these pieces.

So let's just do that.

So let's make a new class called Map Edge.

And within the Map Edge class,

now I'm gonna contain all those pieces I just talked about.

I'm gonna contain a location for the start.

I'm gonna maintain a location for the end.

I'm gonna maintain the name of the street.

So this will just be a string street name.

I'm gonna maintain potentially the street type.

I could also maintain the distance just like we just talked about.

Distance or length.

And now I've encapsulated all of these pieces, all within the Map Edge.

Now I can hook this all back together.

So on map node, so let me draw some boxes around these.

So a map node is gonna have a list of edges connected to it.

So now I just do a list of map edges.

[SOUND] And I could call these neighbors or edges,

or whatever variable name works for us.

And that will then point to a list of these objects.

So for each of the edges that I have, I'd have a different Map Edge.

So for example here, if my location were in A,

one of the map edges I would have would be B with a street name of

main and a distance of whatever value we wanna put there.

And likewise, I'd also have, in this list, another edge, which

contains the edge from A to C that now uses Park Street and some other distance.

So, it's a nice way of encapsulating this.

And I can have this be the other class.

And now the last piece I have to do is,

again, relate this back to how my MapGraph is actually contain this.

And now my map graph is gonna just have a list of these map nodes.

Now I can just do List MapNods, and

I can call this my vertices or nodes.

So I have some choices here.

And then in terms of how I might lay this out, I could just have my vertices, but

it actually might be useful to have my edges.

But we'll talk about that in just a second.

So my usual general use will be, go to my list here,

look up my node that I'm looking for right now.

And now with a list, you're gonna say, now wait a second.

If you're doing a lookup on a list, maybe you should have done a list.

Look up on a list.

If I'm looking for a certain vertex, it's gonna be O of N.

I could just rearrange this to be pretty quickly a Hash map, right?

The Hash map and have it be a vertex or location.

And a map node and now that will be my vertices.

So I can get rid of these.

Now I can do an official lookup, so now we do an official lookup of a location in my

hash map that tells me the, what I'm looking for, say A.

And then I can, essentially diverse the graph from there.

I can go to A to say, well who are your neighbors?

Well I've got a list of edges.

My edges tell me that I have neighbors B and C.

And we can just continue traversing this way.

So there are a number of different ways to solve this project.

You don't have to use the classes that I've described here.

But this is the way that we went about solving it,

and it actually worked fairly cleanly for us.

We added one other piece, and

that was that we actually kept track of the edges here, essentially just for

quick look up and in case we wanted it for debugging purposes.

But you don't necessarily have to have that there.

All right.

I hope this helps.

Good luck on your project.

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2018 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play