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

Subproblems

Loading...

Algorithmic Toolbox

Universidad de California en San Diego

4.7 (4,635 calificaciones) | 150K estudiantes inscritos

Curso 1 de 6 en Estructuras de datos y algoritmos Programa Especializado

The course covers basic algorithmic techniques and ideas for computational problems arising frequently in practical applications: sorting and searching, divide and conquer, greedy algorithms, dynamic programming. We will learn a lot of theory: how to sort data and how it helps for searching; how to break a large problem into pieces and solve them recursively; when it makes sense to proceed greedily; how dynamic programming is used in genomic studies. You will practice solving computational problems, designing new algorithms, and implementing solutions efficiently (so that they run in less than a second).

Destrezas que aprenderás

Dynamic Programming, Debugging, Software Testing, Algorithms, Computer Programming

Revisiones

4.7 (4,635 calificaciones)

5 stars
3,458 ratings
4 stars
937 ratings
3 stars
166 ratings
2 stars
34 ratings
1 star
40 ratings

PR

Feb 10, 2019

The course is perfectly designed. The perfect start for those who start with data structures and algorithms. The Dynamic programming was a little bit tough but overall course is perfectly designed

RS

Dec 23, 2018

This course is just awesome and outstanding in every term. Teachers are very good at explaining even the toughest of problems and really helped throughout the course, i enjoyed and leaned a lot.

De la lección

Dynamic Programming 2

In this module, we continue practicing implementing dynamic programming solutions.

Problem Overview7:01

Subproblems6:57

Reconstructing a Solution8:56

Impartido por:

Alexander S. Kulikov
Visiting Professor
Michael Levin
Lecturer
Neil Rhodes
Adjunct Faculty
Pavel Pevzner
Professor
Daniel M Kane
Assistant Professor

Transcripción

As usual, we start designing our dynamic program in algorithm

by defining a subproblem in a way that allows us to solve

a subproblem by solving smaller sub subproblem.

As we said already, this is probably the most important step

in designing dynamic programming solutions.

So before doing this, we define our problem formally.

So the input consists of n digits.

d1, d2, and so on, dn.

And then -1 operations between them, which we call op1, op2, and so on, opn.

Each operation is either summation, subtraction, or multiplication.

And our goal is to find an order of applying these operations so

that the value of the resulting expression is maximized.

As we discussed already,

we can specify this order just by placing parentheses into our expression.

We start building our intuition by reconsidering our toy example.

So assume that the multiplication is the last operation in some optimal ordering

in an ordering leading to an optimal value in this toy example.

Well this means that in this expression we already have to pairs of parentheses.

And our goal is to parenthesize the initial sub-expression and

the second sub-expression, so as to maximize the value.

This means that it would be good for us to know what is an optimal value for

the first subexpression and the second subexpression, right?

And in general if you have an expression and

if you select a realistic operation, which is the last one,

then it splits your initial expression into two subexpressions, right?

And for both of them it would be good to know an optimal value.

And, in turn, each of these two subexpressions are split into two

sub subexpressions by the last arithmetic operations, and so on.

So this suggests Very good problem in our case would be find an optimal value for

any subexpression or former initial expression.

So we've just realized that it would be good to know the optimal values for

all subexpressions of our initial expression.

What do we mean however, by saying optimal values for all subexpressions?

Assume for example that we need to compute the optimal, the maximal value for

the sum of two subexpressions, subexpression one and subexpression two.

Well this obviously means that we would like this subexpression to be

as large as possible and this subexpression to be as large as possible.

If on the other hand we would like to compute

the maximum value of subexpression one minus subexpression two.

Well this means that we would like subexpression one to be

as large as possible while we would like the value of subexpression two

to be as small as possible, right?

Just because we compute subexpression one minus subexpression two.

This suggests that knowing just the maximal value for

each subexpression would not be enough.

And this usually happens when designing a dynamic programming solution.

This also suggests that, instead of computing just maximal,

we will maintain what is the maximum value and

the minimum possible value for each subexpression.

Let's illustrate this reasoning once again with our previous toy example.

So in this case we are maximizing the product of two small subexpressions.

In this case these two subexpressions, so

small, that it is not difficult to compute their minimal and maximal values.

For example, for subexpression 5- 8 + 7,

the minimum value is- 10 and the maximal value is 4, right?

At the same time, for the second subexpression,

(4-(8+9)), the minimum value is- 13, while the maximum value is 5, right?

Now we would like to parenthesis both subexpressions, so

that their product is maximal.

Well it is not difficult to see, that in this case the optimal way to do this is

to take the minimal values of both sub expressions, right?

So this will give us- 10 multiplied by -13, which is equal to 130.

Right?

Which is much larger than the product of the maximum

values of these two sub expressions which is 4 by 5, which is 20 in turn.

Okay, we are now ready to write down the recurrent relation for our subproblems.

Before this, let's formally define E of ij to be the subexpression of our initial

expression resulting by taking digits from i to j and all operations between them.

Then our goal is to compute the maximum value of the subexpression which we denote

by capital M(i,j) and the minimum value of the sub expression denoted by m(i,j).

Okay, can you see that our initial subexpression from I to J and

assumes that we would like to compute one of the extreme

values of the subexpression and implies there is a minimum or the maximum.

Well we know that in many ordering for this subexpression there is some

last operation, say okay so this separation splits our

initial subexpression into two sub subexpression namely,

subexpression i, k and subexpression k plus 1j.

Right?

To compute the maximum value, we just go through all possible such case,

from i to j- 1, and through all possible extreme values for two subexpressions.

I mean, either we apply operation k to the maximum values of these two

subexpressions or we apply operation K to minimum value,

the minimum values of these two subexpressions.

Or we apply it to the maximum value of one subexpression and

the minimum value of another or vice versa.

To compute the maximum value of sub expression i j,

we just select the maximum among all these possibilities.

While to compute it's minimum value,

we simply select the minimum among all such possibilities.

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