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

370 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

Okay, so, while I'm assigning you a

Â homework problem that's Dijkstra's shortest path algorithm.

Â I'm going to show you the process of

Â handling the is-connected problem, they're related.

Â To some extent you could, in fact, uses Dijkstra's shortest path algorithm.

Â And it's in one form to find whether a graph is-connected or not.

Â But the simpler one should give you ideas about how to do the Dijkstra's algorithm.

Â And this goes back to my own work.

Â Back in 1968 when I was a research graduate

Â student research assistant at the Stanford Linear Accelerator Center.

Â And I was being asked to use this very new programming language called

Â PL1, which is more or less out of favor now but still available.

Â And the interesting

Â thing about PL1 was, it was an attempt to get a universal programming language.

Â PL1 was supposed to IBM's ability to

Â having to do away with special purpose languages.

Â And IBM was finding that it was, it wanted

Â to be a hardware company, not a software company.

Â It wanted to sell big machines, which generally filled

Â up lots of space, and cost lots of money.

Â And software was an, an irritating expense.

Â So, the fact that they had

Â to provide machine language comp compilers, macro

Â preprocessors, COBOL compilers, FORTRAN compilers, sometimes Algol compilers.

Â That was just a lot of different software they were supporting and they just

Â felt, well, why can't we get a

Â universal language, and that will simplify our tasks.

Â And they tried. And the way

Â they tried was unfortunately what I call, the kitchen sink approach.

Â They took everything they had, in all these different languages, threw them all

Â together There was a lot of redundancy in, in this language.

Â You could do things in a COBOL manner or Fortran manner.

Â There wasn't an obvious PL 1 manner to do things.

Â And that's in a way why PL 1 didn't survive the object oriented revolution.

Â Object orientation allows you to have a much simpler idea

Â of what a kernel language is, in our case C.

Â And, then expanded by letting the programmer add

Â classes, whenever they needed, yet, a new domain.

Â A new set of widgets to work with. Now,

Â the algorithm I'm going to describe goes back to work that

Â I did and was documented in some reports at SLAC.

Â But later it was generalized in a very important way by Tarjan

Â and Hopcroft, and it's a foundational algorithm called breadth-first search.

Â And you can certainly read about that.

Â So this is also a vital algorithm that you should be

Â familiar with, Breadth First Search and you can find it in the Wikipedia.

Â And

Â what we're going to do in trying to find out whether

Â a graph, is connected is we're going to start arbitrarily with some node.

Â And since everything in C starts at zero, and we'll probably use the labeling system

Â that says we'll have node zero up to node n minus onee or up to node size minus one.

Â We will assume that node

Â zero Think of our map before, San Francisco.

Â If I'm sitting in San Francisco, I've reached San Francisco.

Â So San Francisco is automatically connected to San Francisco.

Â So we're going to have this initial set, and

Â in that intital set we'll put the node zero.

Â Then we will look from San Fransiciso and see where

Â are the next, where are the adjacent cities we can reach.

Â And this will be what I will call a closed set.

Â And then waht I'm going to call an open

Â set, I'm going to put nodes reachable from San Francisco.

Â So if I could reach node three and node seven,

Â those will be nodes in the open set.

Â Now, what if there was no way out of San Francisco?

Â maybe there's been a huge earthquake and all roads have been busted.

Â What does that mean? It means the graph is disconnected.

Â I can't get from San Francisco to San Diego.

Â I could stop.

Â So, if I have a closed set automatically with a starting node, and if there's no

Â edges out, well, then the algorhythm will stop

Â and report that the graph is not connected.

Â However, if there are ways to get out of San Francisco, namely I can go

Â to Los Angeles or San Jose, as was in that early map I showed you.

Â Those nodes with

Â their names would go into the open set.

Â And then each time I would go to the open set and pick off a next node.

Â Maybe in my algorithm, I pick the node with the lowest number.

Â Take that node and drag it over.

Â Place it in the closed set, and look again for what places I can go from node three.

Â And maybe I can go to node four and node two.

Â And they would become new entries in the open set.

Â So, the open set would contain those that can

Â be reached from what was put in the closed set

Â with the provisio that I don't need

Â to go back to something in the closed set.

Â If there's another way to get back to San Francisco, that's not of interest.

Â So the open set will only have,

Â nodes that are not in the closed set.

Â The calculation will stop, when one of two things happen.

Â Either, (futer - was further -sic) and this is important

Â Either I can't reach all the nodes, in which case, the open set

Â is exhausted, and the closed set has yet to contain size

Â n nodes, all the nodes in the map. So I'm not connected.

Â Or all the nodes, the set of nodes, that are now in the closed set,

Â are, in fact, there are size of them.

Â And then we can stop and

Â the graph is connected.

Â So that's our algorithm. That's what we're going to implement.

Â We go back and we have our matrix

Â representation of the graph,

Â we have it as a Boolean matrix's

Â representation. We have the size

Â of a graph and we are going to keep

Â track of closed and open. And here is where open of zero is true.

Â That's like saying San Francisco is originally in

Â the open set and it"ll be the first, since it will be the only thing in the open set.

Â It'll get automatically selected, placed in the closed set.

Â So, at this point, the open set has node zero on it.

Â It could work if any other node is

Â placed in it, but there's nothing special about zero.

Â To determine whether the graph is connected or not.

Â Nothing is yet in the closed set, and each

Â iteration will add one node to the closed set and

Â possibly many nodes to the open set, or maybe not.

Â The open set doesn't get added to.

Â We're still going to the open set each time as long as there are entries

Â in the open set, and we've yet not worked out whether the graph is connected.

Â So add (to) the closed while the, I'm keeping track of

Â C_size. This is size of the closed set.

Â The

Â old size is the C_size.

Â We then place something in the closed set, meaning.

Â One element is placed in the closed set, so we ought to increment it.

Â The closed set has that element being true.

Â And then, we go and look for things in the open set.

Â And we got to put into the open set anything that's already in

Â the open set that stays in the open set or anything that's newly reachable.

Â Recall this is

Â just our note this is true if an

Â edge (i,j)

Â in the graph and this just logical or.

Â So, this is the logical or operation.

Â So, open is true, if open is already true, or.

Â There is now a new edge that previously couldn't reach j, but now reaches j.

Â We are done if we have all the nodes in the

Â closed set, or if no nodes are available in the open set.

Â If all the here connected, we're connected.

Â Here we're unconnected, and these are our termination cases.

Â And keep in mind, how many iterations are we going to do?

Â We're going to do no more iterations than size.

Â because, in size, we either get a new node, or we fail.

Â And if we fail, before then, we fail before size.

Â And if we keep getting a new node, we get everything up to

Â San Diego and we're finished so we only have to do this the size of the graph.

Â So the fairly straight forward algorithm.

Â Okay.

Â So, I'm going to explain a lot more about Dijkstra's algorithm, how to

Â implement it, how to do your homework and that'll be in our next lecture.

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