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;
      void addNews(const News& news);

   private:
      List<News> serverNews_;
};

class Editor
{
   public:
      void submitNews() { pServer_->addNews(news_); }

   private:
      NewsServer* pServer_;
      News news_;
};

class Reader
{
   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;
      void rawAddNews(const News& news);
      void rawAddComments(const Comments& comments);

   private:
      List<News> serverNews_;
      List<Comments> serverComments_;
};

class NewsServerEditorView: private NewsServer
{
   public:
      void addNews(const News& news) { rawAddNews(news); }
};

class NewsServerReaderView: private NewsServer
{
   public:
      News getNews() const { return rawGetNews(); }
      void addComments(const Comments& comments) { rawAddComments(comments); }
};

class Editor
{
   public:
      void submitNews() { pServer_->addNews(news_); }

   private:
      NewsServerEditorView* pServer_;
      News news_;
};

class Reader
{
   public:
      void readNews() { news_ = pServer_->getNews(); }
      void commentOnNews(const Comments& comments) { pServer_->addComments(comments); }

   private:
      NewsServerReaderView* pServer_;
      News news_;
      Comments comments_;
};

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).