CODEWITHSUNDEEP
calgorithmdynamic-programming
EsotericMe
EsotericMe

Reputation: 811

Dynamic Programming resources in C?

I'll be writing the online Google test tomorrow as a fresher. Apparently, they definitely ask one problem on Dynamic Programming?

Does anyone know of a good resource for collection of DP problems in C along with solutions? I know what DP is & have used it on an occasion or twice. However I feel to crack a DP problem in test, prior practice of typical problems will make it easier to approach.

Any good resources or problem sets with solutions in C will be highly appreciated. Thanks.

Upvotes: 5

Views: 1748

Answers (4)

kuszi
kuszi

Reputation: 2079

To practice you can take one of the available problems at SPOJ. To recognize DP ones easily you can check at Problems Classifier (keyword: dp).

Upvotes: 1

saiful103a
saiful103a

Reputation: 1129

I suggest u,collect a book "An Introduction to Bioinformatics Algorithms".This has a chapter fully on DP.As @templatetypedef mentioned Minimum edit distance,Optimal sequence alignment it has other problem with them.Though there is no implementation in it.You have to do it on your own.But you will find pretty interesting reading them.

Upvotes: 1

j_random_hacker
j_random_hacker

Reputation: 51316

The Topcoder website is amazing. Not all of the problems use DP, but many do. Free full access to all problems from past competitions, which are at 3 different difficulty levels, as well as after-match explanations of every single problem from the problem author. Not only that, but you can quickly dig up the source code solution submitted by any coder in the competition.

Haven't been back there for a while, but they allow at least C++, Java, C# and I believe several other languages now.

Upvotes: 1

templatetypedef
templatetypedef

Reputation: 373102

Okay, so I really hope this doesn't count as "shameless self-promotion," since all of these links are to code snippets I've posted on my personal site. If this is inappropriate, please let me know and I can take them down.

Here are a few fun DP problems that are pretty much classics:

  1. Minimum edit distance: Given two strings A and B, find the shortest number of edits (insertions, deletions, or substitutions) necessary to convert A into B. This is called the Levenshtein distance. (My solution)
  2. Optimal sequence alignment: Given two strings A and B, find the minimum number of gaps that must be inserted into the sequence to align A and B. This is called the Needleman-Wunsch algorithm. (My solution)
  3. Single-source shortest paths: Given a directed graph G and a single node s, find the lengths of the shortest paths from s to each other node in the graph, assuming edges can be positive or negative but that no cycles exist. This is the Bellman-Ford algorithm. (My solution)
  4. All-pairs shortest paths: Given a directed graph G, find the minimum distances between all pairs of nodes. This is the Floyd-Warshall algorithm. (My solution)

Hopefully this is somewhat useful, and best of luck tomorrow!

Upvotes: 8

Related Questions