how should i learn dp and graphs for inoi?

i find difficulty solving graphing and dp based problems.
what should i do??

1 Like

i can help with the part of solving graph problems, as i am not much familiar with DP.

As far as geeks for geeks is concerned, i don’t think the code that they provide is quite readable for a competitive programmer, they unnecessarily use class and objects to explain BFS and DFS, moreover, most of their provided codes have a lot of bugs, as one would be familiar who has given recent codeforces round.

To learn graphs, you can read THIS book. In fact this book covers the entire topic of Competitive programming more or less. The pseudo codes are well written and easy to understand.

For problems, there is SPOJ, codeforces, and as you know codechef. However if you want to cover topics and practice topic wise, i would say UVA online judge is the best for that as all the problems over there are categorized under each topic.

This is all i can say, as i am myself a noob and i follow these things, Hope this helps.

1 Like

DP is a very difficult to get a good grasp on. It requires a lot of practice.

Regarding graphs, you should be at least knowing the standard ones such as DFS, BFS, Dijkstra, Bellmen-Ford, FLoyd-Warshall, Johnson’s algo, SCC, MST, topological sorting.

http://www.geeksforgeeks.org/ surely has varied problems on dp and also the standard implementations of those standard graph algos. It contains around 35-45 different dp problems which vary largely in understand and difficulty and also provide reasonable (not so good IMO) explanation of the dp algo. I haven’t practiced much graph algos. from there so I don’t have extensive info. about that.

You may watch the video lectures of this course on greedy algos and dp (You can audit the course) : https://www.coursera.org/learn/algorithms-greedy/
This course will introduce you to DP and how to catch its concept since it is not at all easy to understand which problems are DP based! Tim Roughgarden is really an amazing instructor!
You may also take his other courses which would make you familiar with beginner graph algos, such as, DFS, BFS and SCC…

Books like Intro. to Algorithms by Thomas Cormen and CLRS should help you in getting started in DP and graph problems. They provide a very good explanation and also pseudo-code.

Topcoder’s Full fledged tutorial dedicated entirely to dp is really great.

Mit ocw’s also has good collection of dp tutorial available here.

//