Practice Problems

If u have seen my Competitive Programming Resources page, u will notice that there are a lot of problems/sites which u can use for practice. It is good to systematically learn as many algorithms as possible and have fun solving unknown problems in Programming Contests, which are conducted multiple times every week - Programming Contest Calendar. So here i will post practice problems on several programming techniques (mostly on SPOJ). The tutorials for these techniques can be found on my Algorithm Tutorials page.

1) Brute Force Techniques/Adhoc Problems

• Basic

Backtracking

Generating all possible subsets using bitmasks

• Intermediate

2) Sorting Techniques

• Basic

Selection Sort, Bubble Sort, Insertion Sort

Merge sort

Quick sort

STL Sort - sort()

3) Searching Techniques

• Basic

Binary Search on a list

• Intermediate

Discrete binary search (on a range of numbers)

AGGRCOW

Ternary Search

KOPC12A

4) Data Structures

• Basic

Stack

Queue

Priority Queue

• Intermediate

Union Find / Disjoint Set Data Structure

Hash Tables

BIT

INVCNT , MATSUM

Segment Tree

GSS1 , GSS3

Trie

•  Advanced

5) Dynamic Programming

• Basic

LCS

IOIPALIN, AIBOHP

LIS

Edit Distance

Matrix Chain Multiplication

0/1 Knapsack

Coin Change

Rod Cutting

Box Stacking

• Intermediate

Matrix Exponentiation

Bitmasking

6) Graphs

• Basic

Depth First Search

Breadth First Search

Floyd-Warshall's Algorithm for All Pairs Shortest Paths

Topological Sort

Dijkstra's Algorithm for Single Source Shortest Path (only positive edge weights)

• Intermediate

Minimum Spanning Tree - Prim's, Kruskals

BLINNET

Strongly Connected Components

CAPCITY

Articulation Points/Bridges

Bellman Ford's Algorithm for Single Source Shortest Path with negative edge weights

• Advanced

Maximum Flow

7) Mathematics

• Basic

GCD - Euclid's Algorithm

Modular Exponentiation

Sieve Of Eratosthenes - Primality testing for numbers in a range

PRIME1

• Intermediate

Extended GCD

Miller Rabin - Primality Testing for a single number

8) Strings

• Intermediate

Knuth Morris Pratt (KMP) Algorithm

9) Computational Geometry

• Basic

• Intermediate

Convex Hull

BSHEEP

Line Sweep

CLOPPAIR

10) NP Complete Problems

Traveling Salesman Problem - Dynamic Programming