P, NP, NP-Hard, NP-Complete

P: Problems that can be solved in polynomial time ex: testing if a number is prime.

NP : Problems that can be solved by non deterministic turing machine in polynomial time, or more simply the problems whose solutions can be verified in Polynomial time but cannot themselves be solved in polynomial time. ex: integer factoring. Easy to verify if 2 numbers multiply to a number.

NP-Hard: Take a problem and reduce it in polynomial time into another problem which can be solved (really fast) and the solution can be converted back to the solution of the original problem in polynomial time. This is of some importance as some problems in NP-Hard are themselves not actually NP! ex: TSP (given cities and their pairwise distances, find the shortest path that visits each city once and returns to its starting point.)

NP-Complete: Those problems that are in NP and also are NP-Hard are known as NP-Complete. ex: decision version of TSP (if there is a route shorter than length L).

If P=NP, it would imply that for every problem to which we can verify a solution in polyomial time, you can also solve it in polynomial time. This is neither proved nor disproved.

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

http://www.udacity.com/overview/Course/cs313/CourseRev/1

Advertisements

Kevin Slavin talks about how algorithms shape our world

Notable points:

blackbox/algo trading (70% of stock market trading on algo trading , at the time of the talk).

progams to hide some large transaction and progams to sew back those broken transactions to look at the actual picture.

nanex(trading), epagogix(movie script evaluating), Roomba, Neato (Cleaning)

the knife, the carnival, the boston shuffler, twilight,

(netflix) cinematch, dinosaur planet, gravity, pragmatic chaos

destination control elevator bin packing algorithm

Heap Sort

  1. Heap Property: Parent is always greater than child
  2. child for parent i are 2i+1 & 2i+2 (zero based starting index).
  3. height of tree is log(n) where n is number of elements.
  4. heap: is a B-Tree with heap property.

Operations:

Inserting element to a Heap: Add the element to the last available position and keep swapping with parent till you find its position.

Heapify a tree A at inex i means make the tree at index i into heap:

Compare A[i] with large of the 2 children and swap if necessary. this MAY break the heap property of the child, so repeat the process with the swap child. O(logn)

Building a Heap: start at n/2 and down to 1 run Heapify at every node. Runs in linear time.

Heap Sort: exchange the last element with max element and decrease the length of the array and repeat the whole process.

 

 

java.nio summary

Buffer:

instantiate using allocate, wrap &  allocateDirect ( can also be obtained by mapping a portion of file into MappedByteBuffer)

invariant:  0 <= mark <= position <= limit <= capacity

transferring data: Relative (Buffer Overflow & Underflow Exception) , Absolute (Index out of bounds exception) & bulk

clear, flip & rewind

Thread Safety: (for ByteBuffer interally thread safety is not provided) Need to provide exteral synchronization

Others: ReadOnlyBuffer, DirectBuffer, compact, duplicate, Slicing

FileChannel:

fc.read(ByteBuffer)

fc.write(ByteBuffer)

fc.force() similar to flush for a strem

fc.map(MapMode, position, size); MapModes are read, write & private (copy on write)

fc.lock() –> exclusive

fc.lock(position,size,shared) -> shared/exclusive on a portion

use lock() in tandem with release()

*Interruptible: means a “blocking operation” can be interrupted using interrupt() method of the blocked thread.

Channels can be tested for interruptibility using instanceof java.nio.channels.InterruptibleChannel (means can be closed asynchronously and can be interrrupted).

if a thread is IO blocked uisng an interruptible channel then 2 things can be done:

1) Another thread can cause channel.colse() which causes the thread to receive AsynchoronousCloseException

2) Another thread can interrupt the blocked thread causing ClosedByInterruptionException and set interrupt status.

3) If thread’s interrupt status is already set performing a blocked IO operation causes ClosedByInterruptionException and interrupt status will remain set.

Character Sets:

charset or charset encoding is “named mapping between sequences of 16-bit unicode character and sequences of bytes” (now explain that!)

CharsetDecoder is used to convert bit-by-bit representation of a string into actual char (java primitive) values.

CharsetEncoder is used to convert char values into bit by bit representation.

Charset.forName(“UTF-8”);

charset.newDecoder();

charset.newEncoder();

Bonus:

http://stackoverflow.com/questions/2533097/java-unicode-encoding

Variable Width Encodings: UTF-8 & UTF-16 (UTF-32 is fixed width) to make it easy for encoding, decoding the bit representation is divided into singeltons, lead untis & trail units.

BOM (Zero-width non-breaking space): Now you think you know all about charsets, till you try to understand endianess and BOM.  http://www.unicode.org/faq/utf_bom.html#BOM

More to cover later:

Buffer Bulk Reads

Scatter, Gather IO

File Locking

Networking and AsynchronousIO

Tree Traversal

BFS:

if(root == null){
return;
}

q.enQueue(root);
process(root);
while(!q.isEmpty()){
Node n = q.deQueue():
process(n);
if(n.left != null) {
q.enQueue(n.left);
}
if(n.right != null){
q.enQueue(n.right);
}
}

DFS:

innode: left, root, right

innode(node){
if(node == null){
return;
}
innode(node.left);
process(node);
innode(node.right);
}

 

prenode: root, left, right

prenode(node){
if(node == null){
return;
}
process(node);
prenode(node.left);
prenode(node.right);
}

 

postnode: left, right, root

postnode(node){
if(node == null){
return;
}
postnode(node.left);
postnode(node.right);
process(node);
}