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...

Из курса от партнера University of California, Santa Cruz

C++ For C Programmers, Part A

493 оценки

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.

Из урока

Module 4

Prim’s and Kruskal’s algorithms. Use of basic Container Classes. Tripod-Container, Iterator, Algorithm.

- Ira PohlProfessor

Computer Science

Okay, let's do something a little more complicated,

and something in which we've used in our homework assignments.

So in the assignments,

I talked about generating a random graph.

And the random graph has what's called a density, and

the density is roughly speaking how many edges per node are available.

So if I have a density of 0.5,

density will be between 0 and 1.

1 would mean that we have what's called the complete graph,

every possible edge is Is included in the graph.

0 would mean we would have a completely disconnected graph.

We would have nodes but no edges.

Half would mean that if I had a graph which had 100 nodes,

on average there would be 50 edges per node.

That would be a reasonably dense graph for something that large.

And it's very useful to use random generation techniques

because when you start applying graph algorithms

to hard problems, it's hard to get real world data.

So at University of California Santa Cruz,

my colleagues have a huge project in designing

the Internet in the sense of making Internet

connections reliable and optimal.

And the Internet has hundreds of millions of nodes,

or maybe even billions of nodes at this point.

And you can send packets reliably all through the Internet.

And there has to be some design criteria.

How is an organization going to build its own local Internet?

Or in the case of the military you might have to have a dynamic

net because the connections are going to involve things in

which there are catastrophic failures.

Let's say your tank is shot up.

And it was one of your Internet points.

Nowadays the battlefield is electronic.

So there's just tons of research in how to create both static and

dynamic networks that make the Internet efficient and

highly reliable and inexpensive.

And those characteristics are hard to come by.

The data's hard to come by, and so, you try to simulate it.

And frequently you simulate it with the right set of random parameters.

So here's something very basic,

and it will also show a small amount of,

uses some of the techniques we've already talked about.

We're gonna borrow stuff from the standard library.

In C++ 11, we might wanna replace rand.

rand is very basic.

And C++11, one of the places where there's significant improvement

is a new set of standard

random functions that get you all sorts of interesting characteristics.

So I hope you go and examine that.

And maybe at a later time, we'll talk a little bit about that.

And this is a simple thing that provides a probability, and

you should see why it provides a probability.

First off, rand is in the int domain.

RAND_MAX is the largest possible value that can be generated.

So this is going to be, well this is unsigned.

And this is the largest possible value.

So this is always going to be less than 1.

But if they both were in an int domain, these would always lead to 0s.

We don't want that, so we force that value into the double domain.

We cast it into the double domain.

And then this becomes a mixed computation.

And then indeed we get a fractional value, which would be between 0 and 1.

So that's the probability you want.

As a probability we want something between 0 and 1.

Here's the density.

The density we're going to get from the user, be inputted.

We want some value inputted such as 0.5.

We also want a size.

So let's say this was the default.

We ask for a size, and this could have just as well been 0.

So we're getting a new size.

Let's say we want a 100.

So we'd have to type that in.

And now we're gonna create a graph.

And we're going to use basically,

A bool matrix.

So the graph is going to have in effect a 0 if there's no edge, i and j no edge.

0, or actually false.

And if there's an edge, there's going to be a 1, i and j having an edge.

True.

We're also going to allow colors.

So that makes the problem a little more interesting.

So edges are going to be able to have colors.

Think about your navigation computer on your car.

And my navigation computer allows the streets to be freeways or local streets.

And it allows me in computing a route to say avoid freeways.

How does it know to avoid freeways?

Freeways are blue, and ordinary streets are green.

And so it's going to look at the sub graph, namely the sub graph

of edges which are only green if it wants to avoid freeways.

Recall that any time we use a random number generator we want to

do something about initializing a seed to avoid routinely

getting always the same behavior out of the program.

So this is a standard practice to seed the random number generator using

something from the real world which would start at a different value.

Here we construct the different components.

We're basically constructing 3 matrices.

So this is a cost matrix like how if i and

j at cost 5 You can think of that as 5 miles.

Here's a [INAUDIBLE].

Maybe i and j will have the color Red.

And this is whether i and j exist.

So we're building the data structure to let us

Represent the graph.

And the graph representation in this case is a matrix representation,

not the edgeless representation.

So for those of you who want,

you can try and I try to do the same thing but do it with an edge list.

Here's where we create an edge.

Think of of this as flipping a coin.

The coin is weighted to give me a probability between zero and

one and then test whether the probability is below the density.

So if density was 1, all these probabilities would be less than 1.

But if density was down near zero, then

the probabilities would largely be greater than the density.

And so, it would be a relatively sparse graph.

So, we're testing to see in the fact that this is symmetric means

that the edges are undirected.

So we're generating undirected edges

of a particular density and then, we're testing if the edge exists

So this is boolean.

Then we do a color and a cost.

We're gonna have 3 colors, so we'll use the modulo operator.

And we'll get value 0, 1, or 2.

And those'll be the equivalent of the colors.

And we'll have a cost, in this case it'll be probability 30,

so times 30, so the values of the cost,

if they're integer values will be between 0 and 29.

I don't think we can get the 30.

And then I'm going to print this to an output file and

the output file, you should try this yourself.

Take the code from the site and you'll see that you'll get

a code that has these characteristics, that will have certain costs for

each edge we'll check again to see that the edge is true

and if the edge is true then those files will list the cost and

the color will have them as output.

Okay, okay we're at the end of

Part A of this course.

I hope you've had a good time, and got to really make use of C++ and

enhance your programming skills.

You've also learned how to do things with graphs and graphs algorithms.

And then, Part B is going to be the next class.

And I hope to see many of you in part B.

And there will be more advanced parts of C++ in Part B.

And try to see yet some newer C++11 features as well,

and the chief work of Part B is to Build a Game.

To Build a Game, is a well known game.

That's Hex. And the reason Part A was so

important to this is not only that you learn how to program effectively in C++,

but Hex is a game that is well represented by graph theory.

So

all

of

this

graph

theory,

should

go

into

understanding

and

building

this

Major

project.

Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.