Part 2 of 2: The Charm of Computational Theory and Algorithm Design

Welcome to Part II of this article. For reference, Part I is available in the link below:

https://www.dhirubhai.net/pulse/charm-computational-theory-algorithm-design-part-1-2-srini-rajam

In the first part, we touched on the eternal charm of designing the most elegant and efficient algorithm to solve a given problem, even in these days when enormous computational resources are available through gigahertz processors, massively parallel compute engines, broadband networks and terabyte storages. We looked at the key metric of an algorithm’s goodness is its computational time complexity, measuring how the run time of the algorithm varies with the problem size. The problem size is denoted by ‘n’ and the computational time complexity of the algorithm is expressed as a ‘Function of n’.

The first part covered a range of algorithms coming under the Class of P (Polynomial Time Algorithms). It concluded with an intriguing note on the Class of NP (Nondeterministic Polynomial Time Algorithms): the massive challenge and importance that they simultaneously represent.

In this part, we will continue from where we left off in the first part. While the picture shown in Part 1 continues to be a good reference, the one provided in this article illustrates the concepts covered here.

6. Nondeterministic Polynomial Time Algorithms, Class of NP

When we leave the class of P (Polynomial Time Algorithms), we enter the most challenging class of NP (Nondeterministic Polynomial) algorithms. These are algorithms that require exponential run times, such as, 2-power-n or n! (Factorial of n).

The question “is P = NP?” (“P vs NP problem”) is one of the principal unresolved problems in Computer Science. It’s widely believed that P is not equal to NP. Research efforts continue to be invested around the world to answer this question either way, without any success so far.

To recap an important point mentioned in Part I of this article, the inherent challenge in NP is due to combinatorial explosion. For example, if there are n locations on a map and roads connecting the locations, the shortest route to go from location A to location B can be computed in polynomial time, since it does not involve combinatorial factors. The famous shortest path algorithm by computer scientist E W Dijkstra runs in O(n-power-2) time where n is the number of nodes (locations) in a graph. However, if the problem is re-defined as finding the shortest route from location A to location B, while also visiting every other location exactly once, it becomes a combinatorial challenge. There are literally exponential number of combinations (of how the n locations can be ordered to form the overall route) which all need to be checked to arrive at the shortest (optimal) route.

7. NP Decision Problems, NP Complete Problems and NP Hard Problems

Within the class of NP, it’s important to understand three related sub-classes: NP Decision Problems, NP Complete and NP Hard, which go up in the computational time complexity stack.

For an NP Decision Problem, known algorithms take exponential run time but a given solution can be easily verified to be Yes or No (correct or not) in polynomial time. As an example, consider an arbitrary graph with n nodes where each of the nodes can have a varying degree, i.e. connected to different sets other nodes in the graph. The problem whether you can find a circuit in which you start with any node and return to the same node by visiting every other node in the graph once and exactly once is an NP Decision Problem. For an arbitrary graph, the computational run time to find the solution will be exponential. However, if an instance of the circuit is presented, it can be easily verified, in just linear time in this case, whether it meets the solution criterion of the problem or not.

NP Complete class contains problems in NP where one problem can be reduced to any other problem in that class in polynomial time. That is, if you find a solution to one problem, it can be used to solve all other problems in that class, by problem reduction in polynomial time. This means a polynomial solution claimed for one NP Complete problem will also lead to polynomial time solution for others in that class.

NP Hard is the class of problems which are at least as difficult as NP Complete problems but need not belong to NP Decision Problems. This means any problem in NP Complete class can be reduced to an NP Hard problem.

One of the most famous NP Complete problems which is also proven to be NP Hard is the Traveling Salesman Problem (TSP). The best known algorithm for TSP has a time complexity of O(n-power-2 * 2-power-n). Even a basic treatment of TSP would require a dedicated article.

8. Quasi-Polynomial Algorithms

These are algorithms whose run time grows much faster than polynomial but far less than exponential. In general, their time complexity can be expressed as a power of 2, where the power itself is of the order of log(n) raised to the power of constant ‘c’. One can see how slowly the function would grow with n, compared to a complexity function that is just of the form 2-power-n. Quasi-Polynomial algorithms are typically useful to solve certain graph theory problems and create approximate solutions for NP Hard problems.

It’s of interest to note that when c = 1, the function just becomes linear.

9. Power of Heuristics

For practical usage in software applications, an algorithm needs to have polynomial time complexity, that too of a very small degree. However, several problems that belong to the NP class have major real-life applications in cryptography, social graph, VLSI design, drug discovery, network design, etc. So, algorithms to solve such problems in practical software applications use heuristics, which run efficiently in polynomial time, but only produce approximate results which are quite appropriate for the given situation. They also typically guarantee that the solution falls within a reasonably acceptable bound of the ultimate optimal solution that would have been found by the exponential time algorithm.

Heuristic solutions derive their strength from the fact that they typically exploit the context of the application (domain knowledge) for which the algorithm is deployed. Consider an example problem of how the large number of circuit blocks in a VLSI design be placed on the chip floor plan in order to minimize the overall space occupied (chip area). In a straightforward mapping, this problem would be like the “Bin Packing (Ordering)” problem which has a combinatorial solution space. However, the domain knowledge that can be used here is how the circuit blocks are connected between themselves through their respective input-output points based on the logic design. A “function” can be defined to represent the “proximity” between two blocks based on the number and type of connections between them. And, the algorithm can employ the heuristic that “higher the proximity, closer the blocks be placed (ordered)”. This will definitely speed up the algorithm to execute much faster with reasonably good results for the application at hand, albeit not guaranteeing to produce the ultimate optimum result that can be obtained by checking every point in the exponential search space.

10. Power of Parallel Processing

Today we have the availability of powerful parallel processing architectures either as compute servers on the cloud or as dedicated machines. These resources can simultaneously provide a number of CPU Cores: 16, 32, 64, 128, 256, etc.

Depending on how parallelizable an algorithm is, it can be designed to execute on parallel machines to significantly reduce the run time. A complex job that may require computational run time in days can come down to hours or even sub-hour with this approach. The actual time reduction achieved will have an upper bound given by the equation T(n) / # Compute Engines, where T(n) is the time complexity running on a single CPU. In actual usage, whether the algorithm can execute different portions of the large data (size n) simultaneously in different CPUs and the inter-processor communication overhead will determine the actual time reduction achieved.

It’s to be noted that polynomial time algorithms (complete solutions to problems in P or approximate solutions to problems in NP) can derive the maximum benefit through parallel processing. If a given problem inherently falls in NP and an exponential time complexity algorithm is implemented, it does not really matter whether it is running on a single CPU or parallel compute engine, as the algorithm would not finish running anyway even after years for large value of n.

11. Data Structures and Time-Storage Tradeoff

Design of algorithm goes hand in hand with the design of appropriate data structures and the secret of certain algorithms depend directly on the data structure. There are also scenarios where algorithm compute time can be traded off (reduced or increased) for data storage (increased or reduced, respectively). Conceptually, once can visualize scaling down the time complexity (say, the degree of the time complexity polynomial reducing) while scaling up the amount of storage needed, as a factor of the input date size and/or intermediate data created in the processing.

That tradeoff choice depends on which of the two costs – compute cost or storage cost – is more expensive in the given system or application. The general trend in cloud computing infrastructure is that compute cost is more expensive than storage, however, it’s still an application or system specific tradeoff decision to be made.

12. Time-Bandwidth Tradeoff

With more and more software applications running online with communication across the cloud server and user client, another important tradeoff to consider is between computational time and bandwidth usage. Even through broadband is more and more prevalent, cellular broadband networks are still expensive. This means higher processing effort spent at both the server and client can minimize the data traffic sent across the network, and consequently the cost of network usage. This brings yet another dimension to algorithm design in saving huge communication costs.

Putting it all together.

A good algorithm design starts with the understanding of the class to which the problem belongs and employing or creating the most optimal algorithm for that case. The aim of the algorithm design should be to: a) do everything needed to solve the problem and b) not do anything else, however minimal it may be, which is not required to solve the problem.

The phenomenal growth of social media and online applications has raised the importance of algorithm design to the next level. For example, it’s one level of time complexity to plot the route for a taxi hailing application between two locations, but it becomes much more complex when ride sharing and pooling are to be facilitated (recall earlier point made about how a problem re-definition can change the algorithm’s complexity). Similarly, with social media applications leveraging the underlying social graph extensively to provide better predictions and recommendations, there is explosive growth in the number of options to be analyzed in the social network. These trends put an even greater price on the quality of algorithm design.

Finally, the note of ultimate importance: an efficient design of algorithm not only enables applications running faster and cheaper, but also saves so much of precious computation power (energy) either on dedicated machines or compute clusters on the cloud. So it’s indeed the coolest thing to do!