This course is for experienced C programmers who want to program in C++. The examples and exercises require a basic understanding of algorithms and object-oriented software.

Loading...

From the course by University of California, Santa Cruz

C++ For C Programmers, Part A

354 ratings

This course is for experienced C programmers who want to program in C++. The examples and exercises require a basic understanding of algorithms and object-oriented software.

From the lesson

Module 3

Point: Default constructor and initializing syntax. Conversion Constructors. Copy Constructor. List and dynamic memory allocation. Deep Copy.

- Ira PohlProfessor

Computer Science

So, part of what the course is going to give you expertise in

Â is algorithmic graph theory, because it's a very, very good subject,

Â because graphs themselves are widgets, complicated widgets.

Â That have very different representations in many

Â ways to try and implement and get efficient

Â for particular different instances.

Â And so, we can see a lot of the old ideas and a lot of the uses of C++ effectively.

Â When we try to implement these algorithms in C++.

Â But also it gives you some background in doing further

Â and more complicated programs as this course (...)

Â progresses.

Â And one of the classical algorithms in computational, graph theory was invented

Â by the very famous Dutch mathematician and computer scientist Edsger Dijkstra.

Â So we're going to see how to use Dijkstra's algorithm and your homework is

Â going to be to implement Dijkstra's algorithm

Â and use it on a randomly generated

Â graph, which you'll also have to implement.

Â We'll also show you how to do a very similar but simpler

Â problem based on an algorithm that I invented many, many years ago.

Â Originally I implemented it in a much earlier programming language call PL-1.

Â And it's the problem of finding out whether a graph is a simple

Â connected component graph. And we're also

Â going to add some drawing lessons. We're going to be drawing

Â graphs as we go through and simulate these algorithms.

Â So this is the set of ideas we're going to need, to do the remaining homework.

Â in this class. So here's an unconnected graph and

Â that unconnected graph

Â is a graph of seven nodes. We might label

Â these nodes 0, 1, 2, 3, 4, 5, 6.

Â That would be traditional C labelling, namely we start from zero.

Â We might label these nodes, A, B, C, D. You'll see all these

Â labellings in the graph literature or might see them

Â as nodes on graph, maybe this is San Francisco.

Â And this is Los Angeles.

Â All of these are possible.

Â So I'm unconnected because we can't go from any node to any other node.

Â There's, we don't see any path.

Â Between, in this unconnected graph, between San Fransisco and Los Angeles.

Â We just see nodes.

Â Now, here's what we're going to show as a connected graph.

Â So I have left the

Â same labelling and now I'm going to add what are called edges.

Â So these blue lines are what we call as edges.

Â The little circles are nodes.

Â The little blue lines are edges. When you think of edges, think of roads.

Â So here's a road from San Francisco, going to Los Angeles.

Â For us who are Californians, that might be 101.

Â here's another road, from San Francisco to D.

Â Maybe D is San Jose.

Â Maybe this is San Diego. So

Â again, you have familiarity in the, in the ordinary world

Â with graphs. They're basically just road maps.

Â And they're road maps in which the cities are nodes and the highways are edges.

Â Now,

Â I'll draw a few more edges. If you looked at this connected graph.

Â The reason it's connected, is, I can find a path between any 2 of the cities.

Â And 2 of these nodes. Or, another term for nodes is vertices.

Â So if I want a path from San Francisco to San Diego, I'll use

Â this little wiggly line and show you here. Oh, there's a path.

Â So that whole graph is connected and indeed a single component.

Â Now, how can I get a computer to draw a graph?

Â Drawing a graph by computer is actually fairly efficient and the critical thing

Â will be to generate using a representation for the graph, an internal representation

Â a number of vertices, so we'll have to decide on the size of the graph.

Â And then we'll have to decide what edges will be placed in the graph.

Â And this particular algorithm I'm going to show

Â you, that'll generate a randomly generated graph.

Â We'll use the heap and create

Â a two-dimensional representation of the graph.

Â So let's see what that means.

Â The overall graph is going to be a pointer That ultimately stores boolean values.

Â What are boolean values?

Â They're the values true or false.

Â If I have a graph

Â that has edges, let's say they were like What we just saw, zero to 6.

Â And

Â I have true in one of the matrix entries. So let's say, in element 3, 4, I've stored

Â true.

Â This is going to mean that the edge from vertex three to four exists.

Â That's what's being created by this little routine.

Â The way it's created is, I seed the random number generator, I hope this

Â is all review, otherwise you'll have to

Â review how a pseudo-random number generator works.

Â I create a graph,

Â in this case, of the appropriate size. It's a graph that

Â is, has seven nodes.

Â And then, for each node, I have to

Â have a row, a Boolean row. So these are the rows.

Â That's what's being created here.

Â And then these are all capable of storing a Boolean value.

Â So the heap has allocated off the heap, through this for loop I've

Â created a two-dimensional array. Whose base pointer is graph.

Â And now,

Â I put edges in.

Â And I'm going to put edges in according to a density.

Â What do I mean by a density? The

Â density

Â is the probability an edge exists.

Â So that could be 0, or it could be up to 1.

Â That's what dense, the range of densities are.

Â 0 would mean, that I'm never going to put (an edge in).

Â If, if this had been 0, no probability would be greater than 0, less than 0.

Â And so I'd never put in an edge. This is the act

Â of putting an edge

Â in. 0 would lead to no edges.

Â One would lead to every edge, the term here is complete.

Â A graph that has all its' edges, all its possible edges, is called complete.

Â So, we have a for loop . The for loop marches through the 2 dimensional graph,

Â if

Â i equals j that means if its on the diagonal we automatically put in false.

Â Otherwise and this is

Â symmetric this turns out to

Â be the undirected graph.

Â If the probability, in our case, we're looking at a density of point one nine.

Â So, roughly, one in five times I'm going to stick an edge in.

Â And, probability is just some function I'm computing

Â using the random number generator you may have to

Â review that, or you may have to look

Â at the code that's online for the probability function.

Â That will generate a randomly generated graph of the given density.

Â So, here's a few questions.

Â Density is zero. The graph has no, what?

Â Density is 1, the graph is what? The C word.

Â The density is fixed, say, to some size and the graph gets larger.

Â What can we say about it?

Â Likely it, how likely it is to be connected.

Â Take a second to look at that.

Â Okay.

Â As we just said already, zero means the calculation says, no chance.

Â You're never going to stick in an edge.

Â One means you're always going to stick an edge in.

Â So it's going to be a complete graph. And now, if the density is 0.1 and we have

Â a, a size that grows. So let's say we have five

Â nodes, density is one. 0.1 I should say.

Â 0.1.

Â That means one tenth of the time in a five node graph, we're going to stick an edge.

Â Well, that's not going to happen often. Five nodes, that means roughly

Â speaking we're going to throw in an edge 50% of the time for that particular node.

Â Well,

Â that's not going to be connected, so it's very unlikely.

Â Let's say we go to a 50,000

Â node graph whose density is 0.1.

Â So if you're following me, the 50,000 node graph and

Â we have lots of 50,000 node graphs in the real world.

Â Just think of the map of all the cities in the United States.

Â And if you're thinking about the map of all the cities in the United States.

Â How many roads are there out of an individual city?

Â Maybe there's 20 rows out of an individual city, that might even be a big city.

Â So a density of 0.1 on a big map

Â is not all that, this would mean,

Â 0.1 would mean that on average,

Â we're going to get 5,000 edges

Â per node. Here it was an average one half edge

Â per node.

Â When half edge per node for a small graph, it's going to leave us unconnected.

Â 5,000 edges out of a 50,000 node graph is

Â going to leave us with a humongous number of paths

Â in that graph and it's very likely that, almost

Â certainly, with probability approaching 1, going to be connected.

Â So if you have a good intuition, about what we've been talking

Â about with these randomly generated graphs and this is going to come up

Â in the homework I'm assigning you, as the graphs get larger, namely

Â the number of vertices, the number of nodes in the graphs get larger.

Â Having a particular density makes it more and more

Â likely that there are paths between all the nodes.

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