algorithms.java

============================================================================================================
1. Sort:
- Merge Sort
- Quick Sort
- Bucket Sort
- Heap Sort
- Counting Sort
When to use: http://stackoverflow.com/questions/1933759/when-is-each-sorting-algorithm-used

2. Search:
- Linear Search [O(n)]
- Binary Search [Ο(log n)](array needs to be sorted)
- Interpolation Search (improved variant of binary search)
- Depth/Breadth First Search - e.g. find the fewest number of steps (or the shortest path) needed to reach a certain end point (state) from the starting one

Other:
 Traversing
 Insertion
 Deletion
 Merging

3. Hashing
A hash function is a function that takes a key (for example, an string of arbritrary length) and returns 
a number as unique as possible. The same key must always return the same hash.

4. Dynamic Programming - method for solving a complex problem by breaking it down into simpler subproblems. 
We solve the subproblems, remember their results and using them we make our way to solve the complex problem, quickly. 
(przykład z "1+1+1+...=")

5. Exponentiation by squaring
=========================================== ABSTRACT DATA TYPES ============================================
LinkedList [TODO]:
 - 

Stack() [LIFO]:
- push() insert from top
- pop() delete from top
- top()/peek() get element from top
- isFull()
- isEmpty()

Queue() [FIFO]:
- enqueue() insert from back
- dequeue() take out from front of queue 
- peek() get the front element
- isFull() 
- isEmpty()

Graph(): ?
- addVertex()
- addEdge()
- displayVertex()
============================================================================================================
Non-linear
 * Balanced Binary Search Tree (BST) [TreeMap] - given root x, elements on the left are
 smaller, on the right are greater (or equal)
	+ O(log n) insertion, search, delete (only works if the BST is balanced)
 * Heap [PriorityQueue] - In each subtree rooted at x, items on the left and the right 
   subtrees of x are smaller than x
	+ insertion and deletion, which can be easily done by traversing a O(log n) leaf-to-root 
	or root-to-leaf path
	+ useful to model Priority Queue, where item with highest priority can be deleted in
    O(log n) and new item can be inserted into priority queue also in O(log n).
 * Hash Table [HashMap, HashSet] 
 
Own implementation:
-------
|Graph|
-------
Graph is collection of vertices and edges (that store connectivity information between those vertices)
Formally, a graph is a pair of sets (V, E), where V is the set of vertices and E is the collection of edges, 
connecting the pairs of vertices.
Order – The number of vertices in a graph 
Size – The number of edges in a graph
============================================================================================================
Problems class:
 - Kruskal’s Minimum Spanning Tree (MST)
 - Dijkstra’s for Single-Source Shortest Paths (SSSP)
 
 General:
 - Hash key : http://howtodoinjava.com/core-java/collections/how-to-design-a-good-key-for-hashmap/
 - 
 
Greedy approach to find an optimum solution:
- Travelling Salesman Problem
- Prim's Minimal Spanning Tree Algorithm
- Kruskal's Minimal Spanning Tree Algorithm
- Dijkstra's Minimal Spanning Tree Algorithm
- Graph - Map Coloring
- Graph - Vertex Cover
- Knapsack Problem
- Job Scheduling Problem

Divide-and-conquer:
- Merge Sort
- Quick Sort
- Binary Search
- Strassen's Matrix Multiplication
- Closest pair (points)

Dynamic programming:
- Fibonacci number series
- Knapsack problem
- Tower of Hanoi
- All pair shortest path by Floyd-Warshall
- Shortest path by Dijkstra
- Project scheduling
============================================================================================================
Asymptotic Notations
	constant	−	Ο(1)
	logarithmic	−	Ο(log n)
	linear		−	Ο(n)
	n log n		−	Ο(n log n)
	quadratic	−	Ο(n2)
	cubic		−	Ο(n3)
	polynomial	−	n^Ο(1)
	exponential	−	2^Ο(n)
============================================ Competitive programming =======================================
* Basic data sturctures (arrays, queues, linked lists, etc.).
* Bit manipulation.
* Advanced data structures:
	a. Union-Find Disjoint Sets.
	b. Segment Tree.
	c. Binary Indexed Tree (a.k.a Fenwik Tree).
	d. Graph.
	e. Treap.
	f. Skip Lists.
	e. Some self balanced Binary Search trees (e.g. Red Black Trees).
* Brute force and it's tricks and advanced techniques (such as, pruning, bitmasks, meet in the middle, iterative deepining etc.)
* Binary Search (not only the basic code).
* Greedy.
* Dynamic programming and it's tricks and optimisations (Knuth optimisation, convex hull optimisation, bitmasks, etc.).
* Graph algorithms:
	a. Traversal (DFS & BFS) algorithms and how to use them.
	b. Finding Connected Components.
	c. Flood Fill.
	d. Topological Sorting (the famous algorithm uses DFS but you should also know Kahn's algorithm that uses BFS as it has much applications).
	e. Bipartite Check.
	d. Finding Strongly Connected Components.
	f. Kruskal's and Prim's algorithms for finding the Minimum Spanning Tree of a graph and the variants of the problem.
	g. Dijkstra's algorithm for solving the Single Source Shortest Path (SSSP) Problem with out negaitive cycles.
	h. Bellman-Ford's algorithm for solving the SSSP problem with negative sycles.
	i. Floyd-Warshall's algorithm for solving the All Pairs Shortest Path (APSP) problem and it's variants.
	j. Network Flow problem (all it's algorithms, variants and the problems reducable to it).
* Mathematics:
	a. You should be familiar with the BigInteger class in Java (maybe write your own if you are in love with C++).
	b. Some Combinatorics.
	c. Number Theory (all what you can learn about it).
	d. Probability Theory.
	e. Floyd-Cycle detection algorithm.
	f. Game Theory (especially impartial games and Sprague-Grundy Theorem).
* Strings:
	a. Basic Manipulation.
	b. Z-Algorithm for finding a pattern in a text.
	c. Knuth-Morris-Pratt Algorithm for finding a pattern in a text.
	d. Hashing and Rabin-Karp Algorithm for finding a pattern in a text.
	e. Trie data structure.
	f. Aho-Corasick Algorithm for finding multiple patterns in a text.
	g. Suffix Array data structure.
	h. Suffix Automaton data structure.
* Computational Geometry Algorithms.