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 2

Review of Dijkstra's shortest path algorithm. C++ Functions and Generics. C++ classes and OO.
Point as an example.

- Ira PohlProfessor

Computer Science

So the other thing that we're going to emphasize in this

Â course is algorithmic graph theory.

Â That's gonna be the domain we're largely going to use for examples, and

Â there's several reasons for it.

Â Turns out that graph theory is an underpinning to

Â a lot of the discrete problems of interest in computer science.

Â It shows up all over the place.

Â In artificial intelligence,

Â there are search algorithms that are foundationally graph theory algorithms.

Â Your GPS devices where you're asking your car to find you a route,

Â you're doing basically very efficient, very complex graph theory calculations.

Â When you're working on the internet, and you're connecting packets between

Â machines over the many hundreds of millions of nodes now on internet.

Â You're basically doing graph theory.

Â So this is basically a great topic.

Â It's foundational in computer science.

Â It requires a lot of careful though in the use of data structures its not

Â typically an ordinary computer language a built in data type its not

Â a native data type so one of the things we're going to find with graph theory is

Â thinking about how to implement graph as a data type.

Â That's going to be part of our

Â understanding of using C++ as an object oriented language.

Â And hopefully you have some of that background.

Â So you should have some notion of what object orientation is.

Â Maybe you even have experience with a language like Java or

Â Python that has object orientation built in, and that experience

Â will stand you in good stead, but you'll still have to see how C++ uses it.

Â But again, graph theory, by itself is just a very important topic.

Â In computational science and applicable all over.

Â So the first thing I want you to do, since to some extent this is review for you,

Â is draw the complete graph of four nodes.

Â And I will give you a definition.

Â A complete graph if you have forgotten that is a graph in which every

Â edge exists in that graph in that map,

Â so if you have San Francisco, Los Angeles,

Â San Jose and Selinas as cities, that would be four nodes.

Â Then there's a direct path from each city to

Â every other city in that graph, and that would be called a complete graph.

Â So take a second and try to draw it.

Â So I'm gonna draw it for you, and

Â we're going to assume that we are using undirected edges so

Â there are directed edges and undirected edges in graph theory but

Â most of what I will be doing will be using direct, undirected edges.

Â And undirected edges are like roads that are two way roads so

Â you can go in either direction.

Â So here is city one to city two.

Â Here is city two to city three,

Â city three to city four, city four back to city one.

Â But that's not complete yet.

Â I could also go from city one to city three.

Â And I can also go from city two to city four,

Â and I'll do it with a little cross over.

Â Are there any other connections that can be made between these?

Â No.

Â So you notice a certain property here.

Â Now in the graph theory world this is called K4, and

Â you should be able to, if you wanted, K5 now.

Â That would be five nodes, all edges and five nodes.

Â K6 and so on, K is just, a notation, meaning complete graph.

Â So, we have four nodes.

Â I'm gonna label them, 1, 2, 3, 4.

Â We could've labeled them, as well, A, B, C, D.

Â Or you could've labeled them San Francisco, Salinas, San Jose, Los Angeles.

Â And then the other property I want you to know about,

Â or another definition, is look at note three.

Â It has three edges out.

Â It has an edge between 3 and 2.

Â I'm gonna notationally write that in between parentheses.

Â It has an edge between 3 and 4.

Â It has an edge between 3 and 1.

Â So it has three edges and this is called degree.

Â So the degree of any of these nodes, in fact, they all had three edges.

Â So degree of,

Â for example, node 1 is 3.

Â In fact, the degree of any of them is 3.

Â In fact if I have the graph K4, then

Â the degree of each node is one less than four, three.

Â And for K5, what do you think?

Â It would be four.

Â The degree of K5 would be four.

Â The degree of K10 would be nine.

Â Degree of K a million would be 999,999 though that's going

Â to take a while to draw, so I'm not going to ask you to draw K a million.

Â Anyway, that's why we have computers.

Â So this is our answer.

Â I just want to give you a little flavor of where this all came from.

Â This came from in some ways a fancy problem.

Â Almost a real world problem actually and

Â graph theory was invented by a very famous mathematician, Euler.

Â Leonhard Euler, 1735.

Â Euler was incredibly prolific,

Â maybe the most important mathematician of the 18th century.

Â And he was studying a problem in his region, and

Â it was called the Seven Bridges of Konigsberg problem.

Â And in trying to solve that problem, he uses mathematical

Â genius to figure out an abstraction that let him

Â logically approach this problem of crossing seven bridges.

Â So let me show you what that problem is.

Â There was a city, Konigsberg.

Â There was a river in the city.

Â Several forks in it, and there were seven bridges crossing the river,

Â and they are shown here in the slide.

Â And the typical Sunday afternoon stroll, so if you were young lovers and

Â you wanted to do something on a Sunday afternoon,

Â you decided to stroll in a way that got you across all seven bridges.

Â And that got you into every area of the city.

Â The conundrum, for the strollers was, can I go and

Â cross every bridge, once and only once?

Â And cover all these sections of the city.

Â Is there a way to do this?

Â And nobody knew how to do it.

Â And indeed by converting it into an abstract problem,

Â Euler was able to show that no such path existed.

Â That later, a path like that was later called an Euler path in his honor,

Â That's the origins, a good story, those are the origins of graph theory.

Â And graph theory was a mathematical concept useful for

Â many years, used by mathematicians, but

Â not that important to real world applications Until the 20th century.

Â The 20th century coupled with computers, many computational problems,

Â including optimization problems, including deduction problems,

Â including matching problems, including looking things up and databases,

Â all could be seen at, you could get incredible insights in these problems

Â by representing these things as graph theory prompts.

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