PART-2
ROADMAP TO LEARN
DATA STRUCTURES
& ALGORITHMS
STEP-BY-STEP
Curated By-
HIMANSHU KUMAR(LINKEDIN) http://www.linkedin.com/in/himanshukumarmahuri
Telegram channel- https://t.me/the_rising_engineers
TOPICS COVERED -
➢ Heaps (priority queue)
➢ Disjoint Set Union
➢ Segment Trees
➢ Binary Index Tree (Fenwick tree)
➢ Trees (traversals, tree dynamic programming)
➢ Finding Lowest Common Ancestors (O(log N) solution
where N is number of nodes).
➢ Graph Algorithms:
o Finding connected components and transitive
closures.
pg. 1
PART-2
o Shortest-path algorithms (Dijkstra, Bellman-Ford,
Floyd-Warshall)
o Minimum spanning tree (Prim and Kruskal
algorithms)
o Biconnectivity in undirected graphs (bridges,
articulation points)
o Strongly connected components in directed graphs
o Topological Sorting
o Euler path, tour/cycle.
➢ Modular arithmetic including division, inverse
➢ Amortized Analysis
➢ Divide and Conquer
➢ Advanced Dynamic Programming problems (excluding
the dp optimizations which are added in expert level)
➢ Sieve of Eratosthenes
Heaps (priority queue)
Resources
1. cs.cmu.edu
2. eecs.wsu.edu
3. geeksforgeeks.org
4. visualgo.net
5. iarcs.org.in
pg. 2
PART-2
Practice Problems
1. codechef.com - IPCTRAIN, editorial
2. codechef.com - ANUMLA, editorial
3. codechef.com - KSUBSUM, editorial
4. codechef.com - RRATING, editorial
5. codechef.com - TSECJ05, editorial
6. spoj.com - WEIRDFN
7. codechef.com - CAPIMOVE, editorial
8. spoj.com - RMID2
9. spoj.com - LAZYPROG
10. spoj.com - EXPEDI
11. acm.timus.ru
12. baylor.edu - Maze Checking and Visualization
13. codechef.com - MOSTDIST, editorial
Disjoint Set Union
Resources
1. topcoder.com
2. harvard.edu
3. ucdavis.edu
4. visualgo.net
Practice Problems
I. codechef.com - GALACTIK, editorial
II. codechef.com - DISHOWN, editorial
III. codechef.com - JABO, editorial
pg. 3
PART-2
IV. codechef.com - PARITREE, editorial
V. codechef.com - FILLMTR, editorial
VI. B. Mike and Feet
VII. D. Quantity of Strings
VIII. codechef.com - SETELE, editorial
IX. codechef.com - MAZE, editorial
X. codechef.com - MAGICSTR, editorial
XI. codechef.com - MTRWY, editorial
XII. codechef.com - BIGOF01, editorial
XIII. codechef.com - FIRESC, editorial
Segment Trees
Resources
I. wcipeg.com
II. topcoder.com
III. kartikkukreja.wordpress.com
IV. visualgo.net
V. iarcs.org.in
Practice Problems
1. spoj.com - GSS1
2. spoj.com - GSS2
3. codeforces.com - Classic Segment Tree (Expert Level)
4. spoj.com - IOPC1207
5. spoj.com - ORDERSET
6. spoj.com - HELPR2D2
7. spoj.com - ANDROUND
8. spoj.com - HEAPULM
9. spoj.com - NICEDAY
pg. 4
PART-2
10. spoj.com - YODANESS
11. spoj.com - DQUERY
12. spoj.com - KQUERY
13. spoj.com - FREQUENT
14. spoj.com - GSS3
15. spoj.com - GSS4
16. spoj.com - GSS5
17. spoj.com - KGSS
18. spoj.com - HELPR2D2
19. spoj.com - BRCKTS
20. spoj.com - CTRICK
21. spoj.com - MATSUM
22. spoj.com - RATING
23. spoj.com - RRSCHED
24. spoj.com - SUPPER
25. spoj.com - ORDERS
26. codechef.com - LEBOBBLE
27. codechef.com - QUERY
28. spoj.com - TEMPLEQ
29. spoj.com - DISUBSTR
30. spoj.com - QTREE
31. spoj.com - QTREE2
32. spoj.com - QTREE3
33. spoj.com - QTREE4
34. spoj.com - QTREE5
Curated By-
HIMANSHU KUMAR(LINKEDIN) http://www.linkedin.com/in/himanshukumarmahuri
Telegram channel- https://t.me/the_rising_engineers
pg. 5
PART-2
Problems on segment tree with lazy propagation
I. spoj.com - HORRIBLE (must do basic lazy propagation
problem)
II. spoj.com - LITE (a nice lazy propagation problem)
III. spoj.com - MULTQ3 (another nice lazy propagation
problem)
IV. codechef.com - CHEFD
V. codechef.com - FUNAGP (a difficult lazy propagation
problem.)
VI. RPAR (a difficult and nice lazy propagation)
VII. codechef.com - ADDMUL
VIII. spoj.com - SEGSQRSS (a difficult lazy propagation
problem)
IX. spoj.com - KGSS
X. codeforces.com - C. Circular RMQ
XI. codeforces.com - E. Lucky Queries (must do hard problem
on lazy propagation)
XII. codeforces.com - E. A Simple Task
XIII. codeforces.com - C. DZY Loves Fibonacci
Numbers (important problem to do,introduces some nice
properties over lazy propagation)
XIV. codeforces.com - D. The Child and Sequence
XV. codeforces.com - E. Lucky Array
pg. 6
PART-2
Binary Index Tree (Fenwick tree)
Resources
1. topcoder.com
2. iarcs.org.in
3. visualgo.net
Practice Problems:
Please solve the problems mentioned in the above segment tree
practice problems section. Note that usually, it's difficult to do range
updates in binary indexed trees. Mostly, it is used for for range query
and point update. However, you can check the following article for
checking how some simple specific kind of range updates can be
performed on binary indexed tree (http://petr-
mitrichev.blogspot.in/2013/05/fenwick-tree-range-updates.html).
Note that range updates on BIT is not a part of the syllabus.
1. spoj.com - INVCNT
2. spoj.com - TRIPINV
Trees (traversals)
Resources
1. slideshare.net
2. iarcs.org.in
3. berkeley.edu
Practice Problems
1. spoj.com - TREEORD
pg. 7
PART-2
Finding Lowest Common Ancestors (O (log N)
solution where N is number of nodes)
Resources
i. topcoder.com
Depth First Search, Breadth First Search
(Finding connected components and transitive
closures)
Resources
1. geeksforgeeks.org - Connected Components in an
undirected graph
2. geeksforgeeks.org - Transitive closure of a graph
3. geeksforgeeks.org - Depth First Traversal or DFS for a
Graph
4. iarcs.org.in - Basic Graph Algorithms
5. visualgo.net - Graph Traversal
6. harvard.edu - Breadth-First Search
Practice Problems
I. codechef.com - FIRESC, editorial
II. spoj.com - BUGLIFE
III. spoj.com - CAM5
IV. spoj.com - GCPC11J
V. spoj.com - KFSTB
VI. spoj.com - PT07Y
VII. spoj.com - PT07Z
VIII. spoj.com - LABYR1
pg. 8
PART-2
IX. spoj.com - PARADOX
X. spoj.com - PPATH ;(must do bfs problem)
XI. spoj.com - ELEVTRBL (bfs)
XII. spoj.com - QUEEN (bfs)
XIII. spoj.com - SSORT ;(cycles in a graph)
XIV. spoj.com - ROBOTGRI ;(bfs)
Shortest-path algorithms
(Dijkstra, Bellman-Ford, Floyd-Warshall)
Resources
1. geeksforgeeks.org - Dijkstra’s shortest path
algorithm
2. Iarcs.org.in - Shortest paths
3. Visualgo.net - Single-Source Shortest Paths
(SSSP)
Practice Problems
I. codechef.com - DIGJUMP, editorial
II. codechef.com - AMR14B, editorial
III. codechef.com - INSQ15_F, editorial
IV. codechef.com - SPSHORT, editorial (slightly difficult
dijkstra's problem.)
V. codechef.com - RIVPILE, editorial
VI. spoj.com - SHPATH
VII. spoj.com - TRAFFICN
VIII. spoj.com - SAMER08A
IX. spoj.com - MICEMAZE
X. spoj.com - TRVCOST
XI. codechef.com - PAIRCLST, editorial
pg. 9
PART-2
Bellman Ford Algorithm
Resources
1. geeksforgeeks.org - Dynamic Programming - Bellman–Ford Algorithm
2. compprog.wordpress.com - ;One Source Shortest Path - Bellman-Ford
Algorithm
Practice Problem
1. community.topcoder.com - PeopleYouMayKnow
2. codeforces.com - D. Robot Control
3. spoj.com - ARBITRAG - Arbitrage ;(Floyd Warshall)
4. community.topcoder.com - NetworkSecurity ;(Floyd
Warshall)
Minimum spanning tree (Prim and
Kruskal algorithms)
Resources
1. algs4.cs.princeton.edu - Minimum Spanning Trees
2. iarcs.org.in - Spanning trees
3. visualgo.net - Spanning Tree
Practice Problem
I. spoj.com - MST
II. spoj.com - NITTROAD
III. spoj.com - BLINNET
IV. spoj.com - CSTREET
V. spoj.com - HIGHWAYS
pg. 10
PART-2
VI. spoj.com - IITWPC4I
VII. codechef.com - MSTQS, editorial
VIII. codechef.com - CHEFGAME, editorial
IX. codechef.com - GALACTIK, editorial
X. codechef.com - GOOGOL03, editorial
XI. spoj.com - KOICOST
Curated By-
HIMANSHU KUMAR(LINKEDIN) http://www.linkedin.com/in/himanshukumarmahuri
Telegram channel- https://t.me/the_rising_engineers
Biconnectivity in undirected graphs
(bridges, articulation points)
Resources
I. e-maxx-eng.appspot.com - Finding Bridges in a Graph
II. iarcs.org.in - Articulation Points
III. pisces.ck.tp.edu.tw - Articulation Points
Practice Problem
1. uva.onlinejudge.org - Network
2. icpcarchive.ecs.baylor.edu - Building Bridges
3. uva.onlinejudge.org - Tourist Guide
4. tzcoder.cn - Network
5. spoj.com - EC_P - Critical Edges
6. spoj.com - SUBMERGE - Submerging Islands
7. spoj.com - POLQUERY - Police Query
8. codeforces.com - A. Cutting Figure
pg. 11
PART-2
Strongly connected components
in directed graphs
Resources
1. iarcs.org.in - Strongly connected components
2. theory.stanford.edu - Strongly Connected Components
Practice Problem
1. spoj.com - ANTTT
2. spoj.com - CAPCITY
3. spoj.com - SUBMERGE
4. codechef.com - MCO16405, editorial
5. spoj.com - BOTTOM
6. spoj.com - BREAK
7. community.topcoder.com - Marble Collection Game
Topological Sorting
Resources
1. geeksforgeeks.org - Topological Sorting
Practice Problem
I. spoj.com - TOPOSORT ;
II. codeforces.com - C. Fox And Names ;
III. codechef.com - RRDAG, editorial
IV. spoj.com - RPLA
V. codechef.com - CL16BF (topological sort with dp), editorial
VI. spoj.com - MAKETREE
Curated By-
HIMANSHU KUMAR(LINKEDIN) http://www.linkedin.com/in/himanshukumarmahuri
Telegram channel- https://t.me/the_rising_engineers
pg. 12
PART-2
Euler path, tour/cycle.
Resources
1. math.ku.edu - Euler Paths and Euler Circuits
Practice Problem
I. spoj.com - WORDS1
II. codechef.com - CHEFPASS, editorial
III. codechef.com - TOURISTS, editorial
IV. codeforces.com - D. New Year Santa Network
V. B. Strongly Connected City
VI. codechef.com - PEOPLOVE
VII. codeforces.com - D. Tanya and Password
VIII. codeforces.com - E. One-Way Reform
IX. spoj.com - GCPC11C
X. spoj.com - MAKETREE
Modular arithmetic including division, inverse
Resources
I. codechef.com - Fast Modulo Multiplication (Exponential Squaring)
II. codechef.com - Best known algos for calculating nCr % M ;(only for expert level)
Amortized Analysis
Resources
I. ocw.mit.edu - Amortized Analysis
II. wikipedia.org - Amortized Analysis
III. iiitdm.ac.in - Amortized Analysis
Curated By-
HIMANSHU KUMAR(LINKEDIN) http://www.linkedin.com/in/himanshukumarmahuri
Telegram channel- https://t.me/the_rising_engineers
pg. 13
PART-2
Divide and Conquer
Resources
I. cs.cmu.edu - Divide-and-Conquer and Recurrences
II. geeksforgeeks.org - Divide-and-Conquer
Practice Problem
I. codechef.com - MRGSRT, editorial
II. spoj.com - HISTOGRA
III. codechef.com - TASTYD, editorial
IV. codechef.com - RESTPERM, editorial
V. codechef.com - ACM14KP1, editorial
Advanced Dynamic Programming
problems (excluding the dp optimizations which are added in expert level, Please go
through the basic DP resources and problems mentioned in foundation level resource.)
Resources
I. apps.topcoder.com - Commonly used DP state domains
II. apps.topcoder.com - Introducing Dynamic Programming
III. apps.topcoder.com - Optimizing DP solution
IV. codeforces.com - DP over Subsets and Paths
Problems for Advanced DP
1. spoj.com - HIST2 ;(dp bitmask)
2. spoj.com - LAZYCOWS ;(dp bitmask)
3. spoj.com - TRSTAGE ;(dp bitmask)
4. spoj.com - MARTIAN
5. spoj.com - SQRBR
6. spoj.com - ACMAKER
7. spoj.com - AEROLITE
8. spoj.com - BACKPACK
9. spoj.com - COURIER
10. spoj.com - DP
pg. 14
PART-2
11. spoj.com - EDIST
12. spoj.com - KRECT
13. spoj.com - GNY07H
14. spoj.com - LISA
15. spoj.com - MINUS
16. spoj.com - NAJKRACI
17. spoj.com - PHIDIAS
18. spoj.com - PIGBANK
19. spoj.com - PT07X
20. spoj.com - VOCV
21. spoj.com - TOURIST
22. spoj.com - MKBUDGET
23. spoj.com - MMAXPER
24. spoj.com - ANARC07G
25. spoj.com - MENU
26. spoj.com - RENT ;(dp with segment tree/BIT)
27. spoj.com - INCSEQ ;(dp with segment tree/BIT)
28. spoj.com - INCDSEQ ;(dp with segment tree/BIT)
29. You can solve some advanced problems from
30. codeforces.com - Dynamic Programming Type
Sieve of Eratosthenes
Resources:
I. codechef.com - Sieve Methods
Practice Problems
II. spoj.com - TDKPRIME
III. spoj.com - TDPRIMES
IV. spoj.com - ODDDIV ;(sieve + binary search)
V. spoj.com - NDIVPHI ;O(N) prime testing algorithm)
VI. spoj.com - DIV ;(divisor sieve)
pg. 15
PART-2
VII. codechef.com - LEVY, editorial
VIII. codechef.com - PRETNUM, editorial
IX. codechef.com - KPRIME, editorial
X. codechef.com - DIVMAC, editorial (segment tree with sieve)
XI. codechef.com - PPERM, editorial ;(a bit advanced sieve
application)
MUST JOIN THE TELEGRAM
CHANNEL FOR NOT MISSING
ANY FUTURES UPDATES.
Telegram channel- https://t.me/the_rising_engineers
You can also subscribe to my newsletter and get
access to regular exclusive job preparation resources.
https://tealfeed.com/path-learn-data-structure-algorithms-step-fkc2d
Curated By-
HIMANSHU KUMAR(LINKEDIN)
http://www.linkedin.com/in/himanshukumarmahuri
pg. 16
