Explore
For Enterprise
Join for Free
Log In

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

Core: Eulerian graphs, an algorithm

Loading...

Advanced Data Structures in Java

Universidad de California en San Diego

4.8 (1,036 calificaciones) | 59K estudiantes inscritos

Curso 3 de 5 en Object Oriented Java Programming: Data Structures and Beyond Programa Especializado

How does Google Maps plan the best route for getting around town given current traffic conditions? How does an internet router forward packets of network traffic to minimize delay? How does an aid group allocate resources to its affiliated local partners? To solve such problems, we first represent the key pieces of data in a complex data structure. In this course, you’ll learn about data structures, like graphs, that are fundamental for working with structured real world data. You will develop, implement, and analyze algorithms for working with this data to solve real world problems. In addition, as the programs you develop in this course become more complex, we’ll examine what makes for good code and class hierarchy design so that you can not only write correct code, but also share it with other people and maintain it in the future. The backbone project in this course will be a route planning application. You will apply the concepts from each Module directly to building an application that allows an autonomous agent (or a human driver!) to navigate its environment. And as usual we have our different video series to help tie the content back to its importance in the real world and to provide tiered levels of support to meet your personal needs.

Destrezas que aprenderás

Graphs, Search Algorithm, Graph Algorithms, Graph Data Structures

Revisiones

4.8 (1,036 calificaciones)

5 stars
840 ratings
4 stars
157 ratings
3 stars
28 ratings
2 stars
7 ratings
1 star
4 ratings

MK

Jul 18, 2017

Excellent course. I have a 32 year old CS degree and needed a Java Course which did not cover the basics of programming but rather covered advanced CS topics in a Java Context. This is the course.

BS

Jan 12, 2016

Splendidly covers path finding basics. Enjoyed the course.\n\nIt would be great to go into advanced algorithms useful for programming challenges (like SPOJ) with the same instructors.

De la lección

Route planning and NP-hard graph problems

In this week, we'll go beyond the problem of finding a path between two points, and focus on problems requiring overall path planning. For example, if you wanted to go on errands and visit 6 different locations before returning home, what is the optimal route? This problem is actually a really well known problem in computer science known as the Travelling Salesperson Problem (TSP). Attempting to solve the problem will lead us to explore complexity theory, what it means to be NP-Hard, and how to solve "hard" problems using heuristics and approximation algorithms. We'll end the week by showing how reformulating a problem can have a huge impact: making something which was effectively unsolvable before, now solvable!

Core: Hamiltonian Graphs6:38

Core: Eulerian graphs4:42

Core: Eulerian graphs, an algorithm3:28

Core: An application in bioinformatics4:48

Impartido por:

Leo Porter
Associate Teaching Professor
Mia Minnes
Assistant Teaching Professor
Christine Alvarado
Associate Teaching Professor

Transcripción

[MUSIC] And so now we can ask the same question we asked before, is there an algorithm that determines, given a graph, whether it's Eulerian or not? And that brute force approach that we talked about before would still work, right. We could still generate all sequences of vertices, check whether they're paths and check whether they're Eulerian. And that's fine, but we talked about how it wasn't efficient. And in fact for Eulerian graphs, there's an easier way. And so, if we think back to our two examples of Eulerian graphs from those just toy, basic examples, we can think about how we may have come up with the Eulerian paths that visit every edge exactly once in these graphs. And notice that when we were thinking about these Eulerian paths, It was important which vertex we started with. So for example, in the one graph, we can't start at one of the side vertices. We have to start in one of the two middle vertices, because if we try to start on one of the sides, then we're gonna get stuck and not be able to come to visit every edge. And the algorithm is based on the observation That when we have an Eulerian path we have to have each edge traverse exactly once and so we can think about these edges as taking us to and from vertices. And so what we're doing is we're partitioning all of the edges in the graph and based on the sequence of edges that we traverse in the path and some of these edges bring us into vertices and some of these edges take us out of vertices. And so if we're focused on any one vertex, in order to have an Eulerian path we have to have the same number of edges going into that vertex as are going out of that vertex. And so what that means is that most of the vertices in the graph need to be of even degree in order for there to be an Eulerian path through this graph. And We might be able to accommodate two exceptions. Our starting vertex is allowed to have more outgoing edges than incoming edges, and our ending vertex is allowed to have more incoming edges than outgoing edges. And so the criterion for being is that there's, at most, two vertices of odd degree in the graph. And it turns out that If we have at most 2 vertices of odd degree, then we can come up with algorithmically an Eulerian path through this graph. Just starting at one of those odd degree vertices and figuring out how to go from there. And ditto If we know that our graph is Eulerian we can guarantee that it has at most two vertices of odd degree, and so it's a really cool theoretical theorem that you can prove about this equivalence between this notion of Eulerian and the degree structure of the graph, and, well who cares? One reason is that it gives us a much faster algorithm for determining whether a graph is Eulerian but again who cares. And the reason we care is that, A, we see the small changes in the definition lead to really big algorithmic differences, and, B, what that does is it gives us a direction to go. If we're trying to use graphs to solve real world problems, then what we want to do is model our real world problems in ways that lead themselves to solutions via looking for Eulerian paths or looking for other graph properties that are efficient to determine or have efficient algorithms for them. What we notice is that, when we're looking at the theory of the graphs, that's great. But we want to keep in mind, when those theoretical choices lead to efficient implementations, and those efficient implementations can help us in practice, as you'll see next.

Explora nuestro catálogo

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

Coursera

Acerca de
Liderazgo
Empleo
Catálogo
Certificados
Certificados MasterTrack™
Grados
For Enterprise
For Government
Para el campus

Comunidad

Estudiantes
Socios
Desarrolladores
Probador beta
Traductores
Blog
Blog de Tecnología

Más

Términos
Privacidad
Ayuda
Accesibilidad
Prensa
Contacto
Directorio
Afiliados

Aprende en cualquier lado

Síguenos

© 2019 Coursera Inc. Todos los derechos reservados.