Soumik's Tech Blog

Both of the paradigm divide the main problem into sub-problems and solve sub-problems. But in Dynamic Programming approach sub-problems are not solved independently. In this case, results of the sub-problems are remembered and used for similar sub-problems. When to choose which one? Divide and Conquer should be used when small sub-problems are not evaluated many times. In this scenario, we should use Dynamic Programming approach or Memorization. For example, in Binary Search, we never evaluate the same sub-problems again. So, we should use Divide and Conquer approach here. On the other hand, for calculating nth number of Fibonacci series, we need to remember the previous calculation because its next number always comes by adding the previous two numbers. Like: 0  1   1  2  3  5  8  13  21........ So, in this type of scenario we should use Dynamic Programming approach. Some standard algorithms that use Divide and Conquer approach are: Binary Search Merge Sort Quick

Recursive function is the function that, as part of its execution, it invokes itself. For example, if we at a function fact(n) that does factorial of number n.    fact(1) = 1    fact(2) =2 * 1    fact(3) =3 * 2 * 1    fact(4) =4 * 3 * 2 * 1    fact(5) =5 * 4 * 3 * 2 * 1    ...... We can define the above lines like this:    fact(1) = 1    fact(2) =2 * fact(1)    fact(3) =3 * fact(2)    fact(4) =4 * fact(3)    fact(5) =5 * fact(4)     ........  So, we can say that,   fact(n) = n * fact(n-1)    is the formula to find the factorial of any number. Every recursive function has two parts: Base Case: It terminates the recursive process. Recursive Case: Where the recursion actually occurs. In other words, where it calls the function itself. From this case, the program keeps running, means it keeps calling the function. To terminate the program from this state, we the base case. When, program faces the base case, it stops calling the function. In this example for b

Yes, a constructor can be private. A private constructor can be useful in many ways. It prevents instantiation outside the object. If we make the constructor private then it can only be accessed inside that class. For example, in the following software design patterns we can use it:             - Singleton Patter            - Factory Pattern It prevents sub-classing.  If we make an private constructor, no other classes can extend that class. It's kind of using the final  keyword.  Lets, look at the code of a Singleton Pattern:

Insertion sort always maintains a sorted sublist at the beginning of a list. New items are then again "inserted" back into the previous sorted sublist such that the sublist remain sorted and it becomes just one item larger. Time Complexity:         Worst Case and Average Case: O(n²)         Best Case: O(n) It works as the same way we arrange cards. Look at the example of swapping items in insertion sort below:  Consider [3, 2, 1] The loop starts with 3. Since it is the first item in the list there is nothing else to do. [ 3 , 2 , 1 ] The next item is 2. It compares 2 to 3 and since 2 is less than 3 it swaps them, first putting 3 in the second position and then placing 2 in the first position. [ 2 , 3 , 1 ] The last item is 1. Since 1 is less than 3 it moves 3 over. [ 2 , 3 , 3 ] Since 1 is less than 2 it swaps moves 2 over. [ 2 , 2 , 3 ] Then it inserts 1 at the beginning. [ 1 , 2 , 3 ]     Let's see the python implementation of Insertion sort.

  In Asymptotic analysis, We evaluate the performance of an algorithm by the input size, not by the actual running time. For example, if we want to search an item from an sorted array, we can do this by two ways: Linear Search - Takes linear time. Binary Search -Takes logarithmic time Now let's assume we are running the linear search in a fast computer and the binary search in a slow computer . For small inputs, the fast computer may take less time to find the item, but as the input size increases and for a larger input the slow computer with binary search will take less time to find the item. The reason is that binary search takes logarithmic time. So, the machine dependency can be ignored after a certain size of inputs. So, is it always gives perfect result? No. But that's the best way available to evaluate an algorithm. Let's say, two algorithms take 2000nLogn 5nLogn In asymptotic analysis, we always ignore constants. So, both of the above becomes: nL