Dynamic Programming

Dynamic programming refers to a problem solving approach, in which we precompute and store simpler, similar subproblems, in order to build up the solution to a complex problem. It is similar to recursion, in which calculating the base cases allow us to inductively determine the final value. This bottom-up approach works well when the new value depends only on previously calculated values.

An important property of a problem that is being solved through dynamic programming is that it should have overlapping subproblems. This is what distinguishes DP from Divide and Conquer in which storing the simpler values aren't necessary.

To show how powerful the technique can be, here are some of the most famous problems commonly approached through Dynamic Programming:

1. Backpack Problem Given a set of treasures with known values and weights, which of them should you pick to maximize your profit whilst not damaging your backpack which has a fixed capacity?
2. Egg Dropping What is the best way to drop n eggs from an m floored building to figure out the lowest height from which the eggs when dropped cracks?
3. Longest Common Subsequence Given two sequences, which is the longest subsequence common to both of them.
4. Subset Sum Problem Given a set and a value n, is there a subset the sum of whose elements is n?
5. Fibonacci Numbers Is there a better way to compute fibonacci numbers than plain recursion?

In a contest environment dynamic programming almost always comes up (and often in a surprising way, no matter how familiar the contestant is with it).

GPS becomes accurate down to a few centimeters

When you stop to think about it, it's amazing how integrated GPS technology has become with our everyday lives. We're constantly using it to get directions and countless smartphone apps use it to suggest nearby restaurants, show us how far we've run and more.
First developed in the 1960's, the Global Positioning System allows a user to determine their location by measuring the time it takes to receive radio signals from four or more overhead satellites. Receivers in our smartphones, navigational systems and more can compute location and velocity based on these measurements. Standard GPS is accurate to within 10 meters, while Differential GPS has improved accuracy to one meter.
While this has been wonderfully sufficient for what we've used the technology for so far, self-driving cars will require even more precise location measurements.
"To fulfill both the automation and safety needs of driverless cars, some applications need to know not only which lane a car is in, but also where it is in that lane—and need to know it continuously at high rates and high bandwidth for the duration of the trip," said Jay Farrell, professor and chair of electrical and computer engineering in University of California, Riverside's Bourns College of Engineering
Farrell and his colleagues have tackled this issue and have developed a way to process data from GPS that delivers accuracy down to a few centimeters. Not only is this method more precise, but it's also more computationally efficient.

According to UC Riverside, "The approach involves reformulating a series of equations that are used to determine a GPS receiver's position, resulting in reduced computational effort being required to attain centimeter accuracy."
This improved process can be used in the development of not just self-driving cars, but improved aviation, naval navigation systems and precision farming. Of course, it will likely also make its way to our gadgets, like smartphones and smart watches as a way to provide even better location data without requiring more processing power.
In order to improve navigational systems in self-driving cars, this new technology will need to be combined with an inertial measurement unit (IMU) to achieve high sample rates and high bandwidth continuously. So far, this combination hasn't been possible because of the need for greater processing power, but because this new method uses several orders of magnitude fewer computations to process the GPS data, this could finally be possible.