CPSIG Week 3: Basic Data Structures and Graph Theory

Knowledge and usage of Basic Data Structures are the bare minimum skills every Sport Programmer needs to be equipped with. Graph theory is another  important domain which provides an alternate view of problems and facilitates one to reduce these problems into graphs and solve them using classical algorithms. Here some basic topics, learning materials and practice problems are listed to get you started into these topics.

Learning Material
 

Basic Track:

1) C++ STL: Vector, Stack, Queue, List(Linked List), Set, Map, Priority Queue

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=standardTemplateLibrary 

For reference: http://www.cplusplus.com/reference/stl/ (very useful during coding if you forget something)

Pre-requisite for Graph Algorithms: Representing graphs as adjacency lists, adjacency matrices etc. 

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=graphsDataStrucs1

2) Depth First Search

3) Breadth First Search

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=graphsDataStrucs2

4) Floyd-Warshall

http://machlearner.blogspot.in/2013/10/all-pairs-shortest-paths-floyd-warshall.html

5) Single Source Shortest Paths - Dijkstra's in O(V^2)

http://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/

Advanced Track:

Advanced STL uses: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=standardTemplateLibrary2
 

1) Single Source Shortest Paths - Dijkstra's in O(V+E*logV) - Refer to priority queue or set approach in Advanced STL uses mentioned above or read this tutorial:

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=graphsDataStrucs3
 

2) Single Source Shortest Paths(with negative weights) - Bellman-Ford:

http://www.geeksforgeeks.org/dynamic-programming-set-23-bellman-ford-algorithm/

3) Topological Sorting:

Reading: http://en.wikipedia.org/wiki/Topological_sorting

Implementation: http://machlearner.blogspot.in/2013/01/topological-sort-and-strongly-connected.html

4) Strongly Connected Components - Kosaraju's or Tarjan's algorithm.

A) Kosaraju's:

Reading: http://en.wikipedia.org/wiki/Kosaraju%27s_algorithm

Implementation: http://machlearner.blogspot.in/2013/01/topological-sort-and-strongly-connected.html

B) Tarjan's:

Reading: http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

Implementation: http://zobayer2009.wordpress.com/code/

5) Bi-Connected Components, finding Articulation Points and Bridges.

Reading: http://en.wikipedia.org/wiki/Biconnected_component

http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/

Implementation: http://zobayer2009.wordpress.com/code/

6) Minimum Spanning Tree - Prims or Kruskals algorithms.

A) Prims:

Reading: http://en.wikipedia.org/wiki/Prim%27s_algorithm

Implementation: 

B) Kruskals: 

Reading: http://en.wikipedia.org/wiki/Kruskal%27s_algorithm

Implementation: http://machlearner.blogspot.in/2013/01/kruskals-algorithm-is-greedy-algorithm.html

Practice Problems

Basic Track:

STPAR, SHOP, POSTERS, PRO, EXPEDI, CTRICK, PPATH, ONEZERO, NAKANJ, ABCPATH, BITMAP

Advanced Track:

SHPATH, CAPCITY, BOTTOM, BLINNET