[go: up one dir, main page]
Scribd
Upload
18 views1 page

Dynamic Programming Applications

Dynamic programming works by breaking down problems into smaller subproblems and storing the results of already solved subproblems, avoiding redundant calculations. It has applications in finding shortest paths like in Google Maps, data transfer optimization in networking, and optimization problems like the travelling salesman problem. The core idea is to cache and reuse results to dramatically improve performance with little work by preventing fetching or recalculating the same data multiple times.

Uploaded by

DR MAITHILI
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
18 views1 page

Dynamic Programming Applications

Dynamic programming works by breaking down problems into smaller subproblems and storing the results of already solved subproblems, avoiding redundant calculations. It has applications in finding shortest paths like in Google Maps, data transfer optimization in networking, and optimization problems like the travelling salesman problem. The core idea is to cache and reuse results to dramatically improve performance with little work by preventing fetching or recalculating the same data multiple times.

Uploaded by

DR MAITHILI
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 1

Dynamic Programming works on the principle of Optimality- If we have reached an optimal

solution, then it's individual components must also be optimized.

Here are some of the applications of Dynamic Programming that I've studied so far:

1. Real life examples


 In Google Maps to find the shortest path between source and the series of
destination (one by one) out of the various available paths.
 In networking to transfer data from a sender to various receivers in a
sequential manner.
2 . Applications in Computer science

 Multi stage graph


 Travelling salesman problem
 Largest common subsequence - to identify similar videos used by youtube
 Optimal search binary tree- to et optimized search results in
 Single source shortest path- Bellman Ford Algorithm.
 Document Distance Algorithms- to identify the extent of similarity between
two text documents used by Search engines like Google, Wikipedia, Quora
and other websites.

The core idea of dynamic programming is to avoid repeated work by remembering partial
results. This is a very common technique whenever performance problems arise. In fact
figuring out how to effectively cache stuff is the single most leveraged thing you can do to
often dramatically improve performance with a small amount of work.

I'm sure you can find examples in any complex enough piece of software.
At facebook we love using DP, and most of the requests you make will execute many
instances of it.
Starting with databases caching common queries in memory, through dedicated cache tiers
storing data to avoid DB access, webservers store common data like configuration that can be
used across requests. Then multiple levels of caching in code abstractions within every single
request, that prevent fetching the same data multiple times and save CPU cycles by avoiding
recomputation. Finally caches within your browser or mobile phones that keep the data that
doesn't need to be fetched from the server every time.

Dynamic programming is basically not repeating calculations.

Considering a real life example:


I go from home to work everyday. If I calculate the shortest path just once and then memorize
it and follow that route everyday I will not do the calculation everyday. Where as if I do not
remember I will have to calculate everyday. It sounds easy to us but when a computer has to
do it, its not that easy.

Google maps (find paths), search engines, recommendations are good examples of dynamic
programming that we are using in real life.

7606454

You might also like