51–60 of 102 posts
All of this is explained very intuitively in speech.zone
In the wikipedia entry there is a fun (really) explanation of why its creator called it like this.
Why use monospace font?????
> Memorisation It is memoization, not memorisation! Although for two weeks in algorithms class I did in fact think our prof was just pronouncing memorize in a cutesy manner.
Honestly though, we should just switch to using "memorization". It's a less obscure word that communicates the intended meaning better, IMHO.
One important takeaway is that dynamic programming in the Bellman formulation is a discrete analogue of Hamilton-Jacobi theory in how it writes down an equation for the optimal value as a function of a given endpoint rather than writing down an equation for the path as with the Euler-Lagrange equations. (You can reconstruct the path from the value function after the fact by gradient descent.) The relationship between Hamilton-Jacobi and Euler-Lagrange is the classical version of wave-particle duality. A concrete example in geometrical optics is the eikonal equation, a Hamilton-Jacobi type PDE, versus the geodesic equation, an Euler-Lagrange type ODE. Not coincidentally, one common numerical method for the eikonal equation called the fast marching method is a dynamic programming algorithm, very similar to Dijkstra's algorithm for shortest paths.
It should be mentioned that any "local" equation like a PDE or ODE cannot describe a globally optimal solution without strong assumptions such as convexity. In fact, satisfying the Euler-Lagrange equation isn't even sufficient for local optimality without further qualifications (Weierstrass conditions). But the Bellman dynamic programming equation, being recursive, can describe globally optimal solutions.
Earlier quoted context omitted.
Same. Probably the worst class I ever took was my algorithms and data structures class. I swear the professor transcribed most of CLRS onto the blackboard over 10 weeks verbatim, and we never so much as touched a keyboard.
Is paper programming in pseudocode bad, though? I mean, computing science is not about computers, and all that.
Earlier quoted context omitted.
What were you supposed to use instead? My impression is that dynamic programming is sometimes sluggish but often better than the alternatives.
Most optimization problems use Linear Programming if the problem has linear/continuous variables and Mixed Integer Programming if binary values (turning something on or off) is part of the solution. These are used in production pretty much everywhere. LP (linear programming) problems are extremely fast too. My company has a HUGE LP & MIP problems and the LPs are still only a few minutes to solve on nice hardware. MIP…
I don't understand this part, can anybody explain?
Earlier quoted context omitted.
It’s odd that there would be algorithms classes that don’t require some implementations.
When I took Algorithms II in college at a top 10 CS program, our entire class involved ZERO coding or programming of any sort.
It was also the class that introduced us to unit tests, by having the code delivered as C library, that the teacher would link against to run her tests.
I learned it as part of speech processing, first for Dynamic Time Warping and then as the Viterbi and Baum Welch algorithms. Together with Hidden Markov Models it's a thing of beauty how it is used to model speech. All of this is explained very intuitively in speech.zone In the wikipedia entry there is a fun (really) explanation of why its creator called it like this.