Learning Material
Basic Track:
String Algorithms:
Regular Expressions:
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=regularExpressions
Knuth Morris Pratt (KMP) Algorithm:
Concept:
http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=stringSearching
Implementation:
http://machlearner.blogspot.in/2013/11/knuth-morris-pratt-kmp-algorithm.html
Range Querying:
Sparse Table (ST) Algorithm:
http://www.topcoder.com/tc?d1=tutorials&d2=lowestCommonAncestor&module=Static
Segment Tree:
http://www.topcoder.com/tc?d1=tutorials&d2=lowestCommonAncestor&module=Static
http://letuskode.blogspot.in/2013/01/segtrees.html
Binary Indexed Tree:
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees
Advanced Track:
String Algorithms:
Suffix Array:
O(n*(logn)^2) - Easier to implement in a contest scenario.
Explanation of the Algorithm:
http://discuss.codechef.com/questions/21385/a-tutorial-on-suffix-arrays
Good Examples:
http://www.stanford.edu/class/cs97si/suffix-array.pdf
O(n*logn) - Manber and Myers Algorithm
http://apps.topcoder.com/forums/?module=RevisionHistory&messageID=1171511
O(n) - DC3 Algorithm
http://algo2.iti.kit.edu/documents/jacm05-revised.pdf
A resource where you can find a compilation of resources and problems:
http://qr.ae/GTA78
Practice Problems
Basic Track:
KMP: NHAY, PERIOD, EPALIN, FINDSR, VPALIN
Segment Tree: BRCKTS, LITE, GSS1, GSS3, HORRIBLE, ORDERSET
BIT: INVCNT, MATSUM, YODANESS
Advanced Track:
SARRAY
Showing posts with label Data Structures. Show all posts
Showing posts with label Data Structures. Show all posts
Tuesday, November 12, 2013
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
Practice Problems
Basic Track:
Learning Material
Basic Track:
1) C++ STL: Vector, Stack, Queue, List(Linked List), Set, Map, Priority Queue
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.
2) Depth First Search
3) Breadth First Search
4) Floyd-Warshall
5) Single Source Shortest Paths - Dijkstra's in O(V^2)
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:
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:
Implementation: http://zobayer2009.wordpress.com/code/
5) Bi-Connected Components, finding Articulation Points and Bridges.
Implementation: http://zobayer2009.wordpress.com/code/
6) Minimum Spanning Tree - Prims or Kruskals algorithms.
A) Prims:
Implementation:
B) Kruskals:
Practice Problems
Basic Track:
Advanced Track:
Labels:
Algorithm,
Competitive Programming,
CPSIG,
Data Structures,
Graph Theory
Subscribe to:
Posts (Atom)