Importance of Design Analysis of Algorithms(DAA) for being a good programmer
Design and analysis techniques according to me plays a vital role in the programming world.
For me, the biggest highlight is the ability to show how we can make certain adjustments in our code to make the existing algorithm much more efficient by certain methods like divide and conquer, dynamic programming etc. And the ability to make improvements in the form of decreased computational complexity, time complexity and memory usage, can only be achieved with help of a deep understanding of existing algorithms for different scenarios.
This simple yet intriguing argument can only be explained with the help of few examples.
Let us take the example of sorting techniques. By default, sorting an array is not a complex task. But the actual juicy portion comes when we start comparing each possible sorting algorithm in different situations. A programmer with a not so thorough understanding of design and analysis techniques would be satisfied with an algo having time complexity as O(n). But if you are familiar the DAA techniques, you would know there are other algorithms with lesser complexities. For instance, average time complexity of bubble sort in O(n²) which gets inefficient for larger lists but still gets the job done. But for a good programmer you would opt for a more efficient ways like merge sort having O(nlogn) as average time complexity. Furthermore, the overall algorithm can be improved by using quick sort which is an in-place and does not require any extra space to execute.
Also, as quick sort is an in-place sorting algorithms, it is preferred for smaller arrays and merge sort for larger arrays. So, the devil is in the details. A real programmer analyzes all the possible options and goes with the most efficient one. Hence, Design and analysis techniques are important for becoming a good programmer.
We shall be going through different examples in order to prove the statement further.
Design and analysis also include complexity classes which are beneficial in many situations. With complexity classes we can effectively provide divisions of computational problem types that give us a great idea on how tackle these different problems based on the division, which is beneficial in practice.
By dividing problem, we get a brief idea on how we should approach them.
For instance, if a problem comes under NP class, we will know it is going to take polynomial-time to solve by a non-deterministic algorithm. So, in those scenarios it would be better to follow approximation algorithms. Suppose we take an example of optimization problem where we must find the least-cost cycle route through all nodes of a weighted graph which is also known as travelling salesman problem. If we aim to find the exact solution instead of approximation, it is going to take polynomial-time, which we can avoid if we know it belongs to the NP complexity class beforehand. So, it is very much helpful in many similar situations.
There are further complexity classes like NP like hard, NP-complete which further provides clarification in situations where the problems are right near the boundaries of NP and NP hard.
If we take another example where if the problem is of R class, finding approximation would give us the worse result as problems coming under this class can be solvable and it does not need polynomial time. So, a proper knowledge of different classes can guide us towards the optimal method that should be taken to find the solution by using the least possible computational resources. Hence, in my opinion even if the concepts of complexity class are theoretical, it is very much used in practical scenarios.
There are many situations where we could use divide and conquer and dynamic programming instead of normal approach to decrease time complexities which is important for any programmer.
In divide and conquer, a problem is broken down into two or multiple sub-problems which are like each other in a recursive manner. And this process of recursion continues as the problem becomes simple enough to be solved directly.
Whereas Dynamic programming algorithm is also like divide and-conquer method. It also breaks down the problem into multiple subproblems but rather than solving the each subproblem repetitively it stores the previous solution. So, for the next subproblem, instead of recomputing the entire solution, is simply takes reference from the previously solved problem and thereby saving time and computational resource. So essentially it is an improvement on the concept of divide and conquer as it does more work on subproblems resulting in more time consumption. Whereas dynamic programing solves subproblems only once and stores the solution. Also divide and conquer is used when the subproblems are independent of each other whereas dynamic programming when they are dependent. So, it is essential TO know which algorithm to use in different scenarios for optimal solutions.
If we take the example of Fibonacci series, in case of divide and conquer we simply use a recursive function to find the sum of previous two values. But in dynamic programming we store the answer of previous output and store it in an array for comparisons. And if a similar case arises in another subproblem we simply use the previous output and hence saving a lot of time. So, a good programmer who has a deep knowledge of DAA will know dynamic programming is better in this situation.
Another vital advantage of knowing design and analysis is the usage of approximation algorithm. According to science, approximation can be referred as to use a simpler model and actual model which is supposed to give the correct result is too difficult to use. So, in general approximation is used to ease calculations. An approximation algorithm returns a solution to every optimization problem which is probably closed to optimal rather than heuristic which may or may not find a proper solution. It is also preferable in certain tough computational problems because sometimes finding a near optimal solution is just easier than finding the exact solution which might require a lot of computational resources. Let us take an example:
Suppose we are given an NP-complete problem to solve. As we know in order to get exact solution of such complexity class problems would be quite difficult as it would take polynomial-time to complete by a non-deterministic solution. So instead of finding the best solution, we can opt for a decent solution which might be within 10% optimal which proves to be more productive. However, the difficulty of getting a decent approximation to different solutions is also quite difficult but its always a better choice in tackling tough computational problems.
As I said the more examples we find, we are clearer the answer becomes. A job of a good programmer is not only to solution to a problem, but to find the best possible one in that scenario which is only possible when we have a deep understanding of design and analysis techniques.
Hence, I wholeheartedly agree on the statement that Design and analysis techniques are important for becoming a good programmer.
