Old wine, new bottle : dynamic programming.

As a part of my grad coursework , I came across this topic... dynamic programming. There's already a lot of description of this topic all over the web, and some of it is truly cool. But when I hear about dynamic programming, I just think its not a new trick at all....its kind of an improved version of divide and conquer..... that reduces time requirement by storing results to the so called "common sub problems".

Well I didnt realize something as old as dynamic programming could be fun to read, I mean one of the descriptions that I read was about dividing a problem into sub solutions. This is basically done using what is called "copy and paste" or something , and the argument in general is:

"Suppose I have optimal solution, then I view this solution as answer of a function with args as two sub solutions"

Optimal(best) Answer to main problem =
Combine((optimal)best ans subprob 1, optimal(best) ans subprob 2)



And to prove this, the argument, we generally say

if the answers to subprob 1 and 2 were not optimal , then we would have taken other solutions that were optimal,and resulting answer would be different(read optimal).
but this cant be, cause we are considering that our main answer is optimal.


eg. consider a shortest path problem.

We say I know the optimal answer of shortest path from a to z.

Then I say, I know that this path is combination of shortest path from a to g and g to z.

sp(a,z) = Combine( SP(a,g) , SP(g,z))

now why should combination of Sp(a,g) and sp(g,z) result always into shortest path? why?

The sub problems are independent. ie. the shortest path from a to g, does not change based on selecting of shortest path from g to z.
Now because of above stmt,in this case, we can easily combine the distances of SP(a,g) and SP(g,z) and that would give us the shortest distance.


But might this always be the case ?

Not really. Consider now for eg. a longest path subproblem. In this we need to find the longest path from a to z, which has no cycles. ie. a simple path.

Now suppose we decide g.
then LP(a,g) is longest simple path from a to g
and LP(g,z) is the longest simple path from g to z.

Now just imagine, that both of this paths actually go through a vertex k....

now lets try to join the two paths.

(a-----k-----g) + (g----k-----z) = a-----k----g----k------z.


Now clearly k---g---k is a cycle and hence this solution is not valid(we dont want cycles).

Shitty feeling isnt it?

now what is really happening here is, the optimal solutions to the subproblems arent independant.

ie. if LP(a,g) involves k, then LP(g,z) should not involve k for all k element of (a-z) -{a,z,g}


This is a dependancy among sub problems, and these problems are called dependant subproblem.




Now next what, now as far as this, dynamic programming is similar to d& c. The difference is that dynamic programming makes use of previously calculated results in order to generate newer ones, thus avoiding repeated calculation, in our shortest path example, this isnt so visible, but for problems like knapsack etc, you can easily see that.


So now, how to excell in the "dynamic programming" , imho you just need to know d&c by heart in order to do this stuff....after all,

dynamic programming isnt something new, its just d&c with some optimizations.

Linux and NICs (bringing up the NIC)

Hello,
Today I will post about detection of NIC (h/w) and if a driver was installed .

Like windows, there is no central way on linux to check if something happened.

To check if NIC is present :

use lspci (list pci devices) : generally nic is connected thru pci bus (if you have one on usb, use lsusb)

ls is a general command to list things on linux, prolly ls+pci is listing pci devices and so on.

Then check if the driver was loaded:

The simplest way of do this is to grep eth lines on /var/log/dmesg file.
dmsg would prolly contain bootup messages.

cat /var/log/dmesg | grep eth

the output should be:

[xxx.xxx] eth0 : registered xyzcompany name etc.

Now simply bringup the network

For this, you need to add entries to /etc/network/interfaces file.
add:
auto eth0
iface eth0 inet dhcp

save.(you can do this via gedit, or vi or any other editor you want)
even cat > would do.
after this, use ifup -a

ifup -a

brings up all interfaces.

try pinging, traceroute and if its replying then your network is up and running!

Wonders of Virtualization

The last time I had to install linux, I had to work out partitioning the hard disk, installing the boot sector on the appropriate partition, and 10k other things. Along with the tension that if I mess something, that would prolly mean reinstalling the whole system again (ie.wasting 2-3hrs) or then complete loss of data :) , if the partition was done absent mindedly,and I boast(in a sarcastic way) a long tradition of making absent minded mistakes.

Now here comes the saviour : FULL VIRTUILIZATION.

As the name suggests , full virtuilization provides virtuilization at level of machine lvl instructions (or machine code), by doing so, a single pc could host a dozen os at a time in complete relative isolation, which is totally rad(ical).


For users like me , who like to try out all that new distros have to offer, this comes as a unparalled boon, now i dont need to toggle my actualy h/w settings, instead i just "virtually-install" any operating system I need to.Thus eleminating any risk that the os installation/running may have brought to the other ones installed.

Ofcourse there are thousands of reasons why virtuilization was actually so important, some being ability of a single hardware to provide multiple guest level operating systems- the primary goal .

Currently virtuilization is important because it helps isolate the hardware and software, by providing a level of virtuilization in between, so processor p0 on a virtual os, may not really exsist. Where is all this heading to ? Well, this is one of the principles of security called diffusion.
Something that diffuses a central attack target into many splinters only one of which is true, or each share 1/nth risk the original, if there were n virtual processors in this particular case.

The downtime is reduced to ~"0" by making use of virtuilization, the answer being obvious that, any damage that occours , ocours to a part of the system rather than the whole system, so next time you jam out a nic, its just the virtual nic, not the real one, so your attack would bring down only part of the operating system.

This added complexity results into security-by-ignorance.


All in all, this is the new beginning of computers ,where a single laptop would host a mac, linux, solaris, and any other os one would like....all at a time.

That is impressive!!!



Try out Virtual Box, one of the coolest full vir s/w available for FREE!