CSSE Seminar Series (CSSESS)

Quick links: Past seminars,  future seminars,  CSSESS Home

Suppose the computer suddenly stops due to power-cut while executing an algorithm, and resumes computation after recovery of power. We assume all the environment of computation is saved and restored after recovery. Then obviously the data are partially modified toward the solution. How much more time is needed to get to the final solution? We try to estimate the time for completion based on the partially solved data.

We measure the degree of partial solution by entropy. As an example, take up the example of sorting, where a partially sorted data set is given by a set, S, of ascending runs of length n1, ..., nk. Then the entropy is defined by H(S)=-(p1log(p1)+...+pklog(pk)), where pi=ni/n. We can show the time for completing sorting is O(nH(S)). If ni=1 for all i, we hit the classical complexity of O(nlog(n)). Entropy here measures the uncertainty in the given data, similar to that of thermo dynamics and Shannon's information theory. The more entropy, the more time for computation. In other words, we capture computation as a process of reducing entropy.

We discuss just a few example algorithms for entropy analysis, including sorting, minimum spanning trees and shortest paths. Almost all existing algorithms can go through entropy analysis, although some may be challenging when partial solutions are to be properly defined.

Quick links: Past seminars,  future seminars,  CSSESS Home