Explore
For Enterprise
Join for Free
Log In

artes y humanidades
Negocios
Ciencias de la Computación
Ciencia de Datos
Tecnología de información
salud
Matemáticas y Lógica
Desarrollo Personal
Ciencias Físicas e Ingeniería
Ciencias sociales
Aprendizaje de un idioma
Títulos y certificados

Explorar todo lo que Coursera tiene para ofrecer

Explorar
Buscar
For Enterprise
Inicia Sesión
Únete de forma gratuita

4.1 MST

Loading...

C++ For C Programmers, Part A

Universidad de California en Santa Cruz

4.4 (588 calificaciones) | 90K estudiantes inscritos

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.

Destrezas que aprenderás

Graph Theory, C++11, C++, Graph Algorithms

Revisiones

4.4 (588 calificaciones)

5 stars
376 ratings
4 stars
138 ratings
3 stars
31 ratings
2 stars
18 ratings
1 star
25 ratings

AK

Jul 04, 2017

I like Prof. Ira a lot and wish to see more courses from him! I wish I was his student at SC. Best Regards to him and the Coursera team for the great work.

PK

Jul 18, 2018

I really loved this course. It is really helpul for my programming aspect. I have managed to develop my logical abilty and this course really helped me.

De la lección

Module 4

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

4.2 Jarnik-Prim MST11:50

4.3 Jarnik-Prim MST: Another Look11:07

4.4 Kruskal's Algorithm8:30

4.5 Overloading and Function Selection32:19

4.6 STL and STL C++1111:00

4.7 STL Example5:05

4.8 C++11 Feature: auto5:38

4.9 Vector Methods10:36

4.10 More Code8:50

4.11 C++11 Feature: for statement7:07

4.12 STL Input File11:30

4.13 Iterators Categories14:19

4.14 Output a Random Graph12:30

Impartido por:

Ira Pohl
Professor

[MUSIC]

So we're on a new topic.

Everybody should've completed the Dijkstra's Algorithm which was

our second assignment and really our first major

assignment. so you should have a fair familiarity

without how to process graphs. The notion of turning a

graph into a class structure, an abstract data type,

to getting a lot of benefit from using graphs which are

very, very useful throughout algorithms computer science study, and again,

hopefully for most of you, all of this is review, so we're

using material you should've already learned.

and isn't novel, but if it isn't review or you've forgot a lot of it.

There're excellent articles especially on the Wikipedia on all these

algorithms on the basic graph theory including the

algorithmic graph theory behind things like Dijkstra's algorithm.

Today's algorithm, which we're going to talk about and

will be the basis for the next homework assignment.

So it builds on Dijkstra, so in some sense, it should be easier because now

you've, you've you're past the jitters. You've gotten your,

your programming legs in terms of this complicated aggregate,

and you're just going to add a new algorithm.

And the whole course is structured to build algorithm by algorithm.

Towards the end of the course, we're hoping you're going to all be able to

implement this very interesting game, hex, which can also be

represented largely as a graph.

So, today the main topic is minimum spanning trees, basis

for homework three, and we're also going to study again, object orientation.

How important object orientation is. When we use a language, like C++,

what are the ideas, we bring to the table, to do good C++

programming? C++ is way more than an object-oriented

language. It's got multiple tools in its, in its

bag and it has the ability to do generic programming and it

has the ability actually, to do functional programming

in terms of C++ 11.

So it's multi-paradigmatic, C++ is multi-paradigmatic.

But, a really great strength. And the thing that

has it replacing C was the shift

from ordinary imperative programming that was C.

To encapsulation-based on the object-oriented paradigm.

And we'll see that with, a very

simple but, very useful example called class point.

So, homework three.

You've already built the graph abstract data type.

you hopefully got the Dijkstra algorithm to work.

You got it to work on automatically

generated, graph based on densities and size.

You computed an average length in such a graph.

Saw how all of that could work. And we're going to add this next

major algorithm, again extremely useful. Minimum spanning tree comes up.

In many, many areas in computer science and electrical engineering.

In some sense it's maybe at the heart of

the Internet, the way the Internet works, one wants

to have a minimum spanning tree so that from

particular foci you can get your messages, packets whatever

out to arbitrary other foci.

Minimum spanning tree, a definition. So again, we're going to have a

graph in which an edge has some arbitrary positive cost, an edge.

So we might have

an edge from a to b. With, let's say, cost seven.

And

we have a whole graph built of edges with costs.

First off, we have to know what a spanning tree is.

A spanning tree is just a set of edges, that in effect is a tree.

Remember we, in computer science

frequently use things called, binary trees.

Binary trees would be spanning trees of graphs if the graph

had inside it, a binary tree. So a spanning tree is a set

of edges within the graph that connects all the nodes of the

graph, and where there is no cycles. So an immediate

implication of that is if we have a graph of

n-nodes, a spanning tree is a tree

with

n minus 1 edges. Now,

I'm also going to, in

this homework problem,

assume that edges in the spanning tree can have different colors.

It's going to make it a little more sophisticated and it'll

add to some of the ideas in how you learn C++ programming.

It'll enable you to use, an enum type, or a class enum type.

that, class enum type is yet another novel idea in C++ 11.

So if you have a C++11 compiler we may talk a little bit about a class enum

type, as opposed to the earlier, pure enum type, which remains.

and so we can assume that an edge

can be red. There can be red edges.

There can be blue edges.

There can be green edges. And we might, when

we specify our minimum spanning tree problem, decide on well do

we want a minimum spanning tree in which all the edges are green?

Green and MST?

Or maybe we would have blue

and red and MST.

So for the same graph in which they were colors, we

could have multiple answers to the minimum spanning trees.

So as they say, it just makes the problem a little bit non-standard,

not as easy to copy the code off the internet, adds a little flavor to it.

And actually it'll be a flavor that will

be useful in many later and more complicated venues.

So first let's take a little quiz. If we

have a enumerated type, here's a simple enumerated type, color.

This is different than as I say C++ 11 will have a

class enumerated type. Why were the colors capitalized?

The enumerators have internal values, in this case

what would be the value of green? And if we wanted, and this is a new type.

So again, object orientation is all about adding

types to the basic native types in a

way that, is compatible with the basic native

types, and fulfills the expectation of the C++ community.

And the expectation in the C++ community is

that the IO, the, what you might call pseudo-operators, the, the

operators adopted to in this case, the bit shift operators.

Adapted so that they do IO. can be overloaded.

How would we overload to print red?

So take a few minutes and see how you'd answer those questions.

Well, first off, the reason that we use capital is just a community convention.

So whenever we have things that we think of as constants.

This even goes back to the old C style where when

we didn't have a enumerators, we just did this using macros.

So the minute we see in our C code some big cap,

all caps identifier, we think that must be some

kind of standard constant. In this case,

the values go sequentially 0, 1, and 2, so green

ends up two, and then if we were

to implement the code for overloading the operator,

recall that it has a certain idiomatic format.

We're always going to call

by reference,this complex construct, the ostream.

We call the new type that we want to overload.

And then we're going to return. What do we return here?

Everybody should know that should be return of out.

Why is that again? So that we could properly use C out,

something.

And that in effect,

these are expressions that evaluate to the same ostream so that

you can use that output

repeatedly. Here's some new

novel stuff fresh from the new standard. They are

what we call strongly typed enumerators, enum classes.

We're going to see why we need them. Let's say in the old

style I could've had enum color. And enum traffic.

And then I'd have two specific uses of red as enumerators.

And they can actually get confused because they weren't strongly typed.

In essence,

some kind of integer and they would be comparable if I wanted to.

However, when I turn them into this newly,

strongly typed enum, and that happens by, instead

of just calling an enum, I'm calling them enum class, so it looks somewhat the same.

Except now I have class.

Now, the two enumerators are distinct. They're not comparable.

They're not.

They have type distinction. Since they have type distinction.

They're much safer in code.

We can't get into trouble with conversion opportunities for example.

Explora nuestro catálogo

Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.

Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.

© 2019 Coursera Inc. Todos los derechos reservados.

Descargar en la App Store

Consíguelo en Google Play

Coursera
Acerca de
Liderazgo
Empleo
Catálogo
Certificados
Certificados MasterTrack™
Grados
For Enterprise
For Government

Comunidad
Learners
Partners
Developers
Beta Testers
Translators

Conectar
Blog
Facebook
LinkedIn
Twitter
Instagram
Youtube
Blog de Tecnología

Más
Términos
Privacidad
Ayuda
Accesibilidad
Prensa
Contacto
Directorio
Afiliados