# How much can you achieve in a century?!

I’ve always wondered how bad could an exponential-time algorithm be? Why are polynomial-time algorithms usually considered tractable compared to exponential- and factorial-time ones? I was recently reviewing Introduction to Algorithms when I came across the only problem in Chapter 1. It asks for the largest size $n$ of a problem that can be solved in unit time by an algorithm that takes $f(n)$ microseconds to run, where a unit of time could be a second, a minute, and so on. Here are the numbers I got:

 1 second 1 minute 1 hour 1 day 1 month $lg~n$ $2^{10^6}$ $2^{6\times10^7}$ $2^{3.6\times10^9}$ $2^{8.64\times10^{10}}$ $2^{2.592\times10^{12}}$ $\sqrt{n}$ $10^{12}$ $3.6\times10^{15}$ $1.296\times10^{19}$ $7.46496\times10^{21}$ $6.718464\times10^{24}$ $n$ $10^6$ $6\times10^7$ $3.6\times10^9$ $8.64\times10^{10}$ $2.592\times10^{12}$ $n~lg~n$ $62746$ $2801417$ $133378058$ $2755147513$ $71870856404$ $n^2$ $1000$ $7745$ $60000$ $293938$ $1609968$ $n^3$ $100$ $391$ $1532$ $4420$ $13736$ $2^n$ $19$ $25$ $31$ $36$ $41$ $n!$ $9$ $11$ $12$ $13$ $15$
 1 year 1 century $lg~n$ $2^{3.1104\times10^{13}}$ $2^{3.1104\times10^{15}}$ $\sqrt{n}$ $9.67458816\times10^{26}$ $9.67458816\times10^{30}$ $n$ $3.1104\times10^{13}$ $3.1104\times10^{15}$ $n~lg~n$ $787089606198$ $67699498463641$ $n^2$ $5577096$ $55770960$ $n^3$ $31448$ $145972$ $2^n$ $44$ $51$ $n!$ $16$ $17$

A picture is worth a thousand words! It’s always useful seeing the numbers than hearing stories about how slow an exponential-time algorithm could be.

This also illustrates how interesting NP-complete problems are. The fact that these seemingly simple problems are exponentially hard and that finding an efficient solution to one of them gives a solution to them all, makes them the most exciting riddles in the history of computer science. What’s more exciting is that while many researchers believe no efficient solution exists for this class of problems, no one has ever been able to prove it! This also reveals why P vs. NP was chosen to be the first of Clay Institue’s seven problems of the millennium.

# Implementing Client-Specific Interfaces

One thing I’ve been recently wondering about, is how to implement client-specific interfaces for a class. By client-specific, I mean that a client of class A would be granted access only to a subset of A‘s public interface. This could be useful when different entities are to be admitted different access rights to the services provided by A.

This isn’t in fact a new idea. It’s just a concrete implementation for the Interface Segregation Principle, one of the five SOLID principles of object-oriented design.

An example could be a NewsServer which has two types of clients, an Editor and a Reader. An Editor is allowed to submitNews() to the NewsServer, while a Reader can only readNews() from the NewsServer:

class NewsServer
{
public:
News getNews() const;

private:
List<News> serverNews_;
};

class Editor
{
public:

private:
NewsServer* pServer_;
News news_;
};

{
public:
void readNews() { news_ = pServer_->getNews(); }

private:
NewsServer* pServer_;
News news_;
};


However, since the NewsServer public interface is visible to all clients, nothing prevents a Reader from calling addNews() to submit news to the NewsServer.

One possible solution to prevent a Reader client from calling addNews() on a NewsServer is to prevent any editing to NewsServer from inside a Reader object:

class Reader
{
public:
void readNews() { news_ = pServer_->getNews(); }

private:
const NewsServer* pServer_;
News news_;
};


By letting pServer_ be a const NewsServer*, a Reader cannot addNews() to a NewsServer. This however restricts any write operations to NewsServer from a Reader. Suppose for example that we want to extend the NewsServer to allow a Reader to addComments() on submitted news. This extension would break this solution because a Reader would have to be able to edit a NewsServer.

A better way to approach this problem is similar, in some sense, to an SQL VIEW of a TABLE. The idea is basically to hide the raw interface of a NewsServer, and expose a “view” of it that is customized per client. So a Reader client would have to deal with a NewsServerReaderView and an Editor would have to deal with a NewsServerEditorView. A view is simply a new interface for a NewsServer that only exposes the services relevant to a specific client. This is also a good place for using aggregation through private inheritance:

class NewsServer
{
protected:
News rawGetNews() const;

private:
List<News> serverNews_;
};

class NewsServerEditorView: private NewsServer
{
public:
};

{
public:
News getNews() const { return rawGetNews(); }
};

class Editor
{
public:

private:
NewsServerEditorView* pServer_;
News news_;
};

{
public:
void readNews() { news_ = pServer_->getNews(); }

private:
News news_;
};


This way, read and write access are both preserved for all clients and every client is only granted access to services relevant to itself. Notice that NewsServer‘s old public interface is now protected. This prevents any client from accessing the raw NewsServer interface and forces it to use one of the available views (or possibly add a new view).

# Welcome to my weblog!

Hello everyone,

Welcome to my weblog! Here’s where I publish my ideas, insights and cool things I occasionally stumble upon.

Stay tuned!

Thanks for visiting,

Haitham