Showing posts with label Data Structures. Show all posts
Showing posts with label Data Structures. Show all posts

Tuesday, November 12, 2013

CPSIG Week 4: String Algorithms and Range Querying

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

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: 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:
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:
Implementation: 
B) Kruskals: 

Practice Problems

Basic Track:

Advanced Track: