Resources for the Advanced Level in Certification

Heaps (priority queue)

Practice Problems


Disjoint Set Union

Practice Problems


Segment Trees

Practice Problems

Problems on segment tree with lazy propogation


Binary Index Tree (Fenwick tree)

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 peformed 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.


Trees (traversals)

Practice Problems


Finding Lowest Common Ancestors (O(log N) solution where N is number of nodes).


Depth First Search, Breadth First Search (Finding connected components and transitive closures).

Practice Problems


Shortest-path algorithms (Dijkstra, Bellman-Ford, Floyd-Warshall)

Practice Problems


Bellman Ford Algorithm

**Practice Problems


Minimum spanning tree (Prim and Kruskal algorithms)

Problems


Biconnectivity in undirected graphs (bridges, articulation points)

Practice Problems


Strongly connected components in directed graphs


Topological Sorting

Practice Problems


Euler path, tour/cycle.

Practice Problems


Modular arithmetic including division, inverse


Amortized Analysis


Divide and Conquer

Practice Problems


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.)

Problems for Advanced DP


Sieve of Eratosthenes

Practice Problems

//