Sorting in Linear time

1. Counting Sort (input consists of integers in a small range)
2. Radix Sort
3. Bucket Sort (input is uniformly distributed)

Any comparison sort algorithm requires nlgn comparisons in the worse case.

Counting Sort (Running time: theta(n))

Counting sort assume that each of the n input elements is an integer in the range 0 to k, for some integer k. The basic idea of counting sort is to determine, for each input element x, the number of elements less than x. This information can be used to place element x directly into its position in the output array. We need to do a slight modification to handle the situation in which several elements have the same value. In practice, we usually use counting sort when we have k = O(n), the running time is theta(n).

Counting sort is stable: numbers with the same value appear in the output array in the same order as they do in the input array, which is very important since counting sort is often used as a subroutine in radix sort.

Counting sort requires two other arrays: the array B[1...n] holds the sorted output, and the array C[0...k] provides temporary working storage.

The algorithm itself is not complicated, watch out boundary errors when you try to implement it.

Radix Sort

Radix-Sort(A, d)
1. for i <-- 1 to d
2. do use a stable sort to sort array A on digit i

Radix sort can be used to sort records of information that are keyed by multiple fields.

Given n d-digit numbers in which each digit can take on up to k possible values, Radix-Sort correctly sorts these numbers in theta(d(n+k)) time. When d is constant and k = O(n), radix sort runs in linear time.

Bucket Sort

Bucket sort, or bin sort, is a sorting algorithm that works by partitioning an array into a finite number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. Bucket sort is a generalization of pigeonhole sort.

WinCVS

http://www.devdaily.com/wincvs/HowToUseWinCVS/

http://ikon.as/wincvs-howto/#startingnew

TightVNC

An enhanced version of VNC (an abbreviation for Virtual Network Computing) is a great client/server software package allowing remote network access to graphical desktops.

TightVNC can be used to perform remote control and administration tasks in Windows, Unix and mixed network environments.

http://www.tightvnc.com/

Dead Lock

Network Flow

Terms:

• A Flow in graph G must satisify 1) capacity conditions. For each e belong to G, 0<=f(e)<=Ce. 2) conservation conditions. For each node v other than s and t, the flow value over all edges entering node v equals the sum of flow values over all edges leaving node v.
  
• The capacity of a cut, denoted as c(A, B), is the sum of the capacities of all edges out of A.
  

Properties:

• The residual graph Gf has at most twice as many edges as G.
  

The value of every flow is upper-bounded by the capacity of every cut. Let f be any s-t flow, and (A, B) any s-t cut, Then the value of flow v(f) <= c(A, B) , which is the capacity of a cut (A, B).

Max-Flow Min-Cut Theorem

In every flow network, there is a maximum flow f and a minimum cut (A, B) so that v(f) = c(A,B). There can be many minimum-capacity cuts in a graph G. All edges out of A are completed saturated with flow, while all edges into A are completely unused.

Ford-Fulkerson Algorithm: this algorithm will terminate when there is no s-t path in the residual graph. The algorithm is as follows.

Initially f(e)=0 for all e in G
While there is an s-t path in the residual graph Gf
...Let P be a simple s-t path in Gf
...f'=augment(f,P) // the running time for this helper function is O(m)
...Update f to f'
...Update the residual graph Gf to be Gf'
Endwhile
Return f

Helper function
augment(f,P)
..Let b = bottleneck(P,f)
..For each edge (u,v) in P
....If e=(u,v) is a forward edge then then
......increase f(e) in G by b
....Else ((u,v) is a backward edge, and let e=(v,u))
.....decrease f(e) in G by b
....Endif
..Endfor
..Return ()






Edmonds-Karp Algorithm

LaTeX

A very power formatter, you should not miss it.

Good tutorial on the website:

http://www.maths.tcd.ie/~dwilkins/LaTeXPrimer/

Associative array: Hash Table vs BST

An associative array (also map, mapping, hash, dictionary, finite map, lookup table, and in query-processing an index or index file) is an abstract data type composed of a collection of keys and a collection of values, where each key is associated with one value. The operation of finding the value associated with a key is called a lookup or indexing, and this is the most important operation supported by an associative array. The relationship between a key and its value is sometimes called a mapping or binding.

Associative arrays are usually used when lookup is the most frequent operation. For this reason, implementations are usually designed to allow speedy lookup, at the expense of slower insertion and a larger storage footprint than other data structures.

Representations: Hash Table vs Binary Search Tree (self-balancing)

There are two main efficient data structures used to represent associative arrays, the hash table and the self-balancing binary search tree. Skip lists are also an alternative, though relatively new and not as widely used. Relative advantages and disadvantages include:

• Hash tables have faster average lookup and insertion time (O(1)), while some kinds of binary search tree have faster worst-case lookup and insertion time (O(log n) instead of O(n)). Hash tables have seen extensive use in real time systems, but trees can be useful in high-security real time systems where untrusted users may deliberately supply information that triggers worst-case performance in a hash table, although careful design can remove that issue. Hash tables shine in very large arrays, where O(1) performance is important. Skip lists have worst-case operation time of O(n), but average-case of O(log n), with much less insertion and deletion overhead than balanced binary trees.

• Hash tables can have more compact storage for small value types, especially when the values are bits.

• There are simple persistent versions of balanced binary trees, which are especially prominent in functional languages.

• Building a hash table requires a reasonable hash function for the key type, which can be difficult to write well, while balanced binary trees and skip lists only require a total ordering on the keys. On the other hand, with hash tables the data may be cyclically or partially ordered without any problems.

• Balanced binary trees and skip lists preserve ordering — allowing one to efficiently iterate over the keys in order or to efficiently locate an association whose key is nearest to a given value. Hash tables do not preserve ordering and therefore cannot perform these operations as efficiently.

• Balanced binary trees can be easily adapted to efficiently assign a single value to a large ordered range of keys, or to count the number of keys in an ordered range.

http://en.wikipedia.org/wiki/Associative_array