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

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.

 

 

A stitch in a time saves nine.

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

Stop Learning & Start Thinking.

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);
}

Some Notable things about Java equals

equals() is not symmetric with treatment of null. From spec x.equals(null) should return false for all x not null, but the other way round just throws NPE!

When comparing arrays for equality use 2 helper methods: Arrays.equals() & Arrays.deepEquals.

Gauva Objects.equal(a,b) can be used to check equality based on member variables. Some pit falls:

If member variables are arrays make sure to use “Arrays” as Objects.equal checks for null and delegate back to equals in the object. The default implementation for Array equals is identity check.

Make sure to check a & b or not null before delegating to Objects.equal() if you are “inlining” referring to member variables of a or b.

Prefer, to use instanceof instead of getClass() as instanceof will return true for subclasses as well which will not break the euals contract when new subclass is written to modify behavior but not state!

Finally, Don’t forget to override hashcode when you override equals!

 

Click to access JavaEquals-ACCU-2002.pdf

Fearless

Any one can  cook, but only the fearless can be great.

– Auguste Gusteau

 

 

Not everyone can become a great artist, but a great artist can come from anywhere.

– Anton Ego

Panic Reset Button

http://www.businessinsider.com/how-to-be-successful-under-stress-sharon-melnick-2012-12

 

• In a situation divide what can you control and what you can’t. Work on the part you can control.
• Mental Reset: Great Yogi’s breath for 20 seconds, hold for 20 seconds and release for 20 seconds. We can start with 5 seconds
• Breath into feet.
• Press the Accupunture point in between 2nd & 3rd knuckle of middle finger to reset the PANIC Button.

 

Turn Obstacles into Opportunities.