Thursday, October 17, 2013

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
For reference: (very useful during coding if you forget something)
Pre-requisite for Graph Algorithms: Representing graphs as adjacency lists, adjacency matrices etc. 

2) Depth First Search
3) Breadth First Search

4) Floyd-Warshall

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

Advanced Track:
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:
2) Single Source Shortest Paths(with negative weights) - Bellman-Ford:
3) Topological Sorting:

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

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

6) Minimum Spanning Tree - Prims or Kruskals algorithms.
A) Prims:
B) Kruskals: 

Practice Problems

Basic Track:

Advanced Track:

1 comment:

  1. Thank you for the sources.

    You can also learn from TekSlate tutorials teaches the fundamentals of Data Structures and algorithms with many workout examples