As a tutor you can connect with more than a million students and grow your network.

Feed

Overview

Lessons 15

Total Shares

Lesson Posted on 03 Jan Tuition/BTech Tuition/BTech Information Science Engineering

Debraj Paul Study Champion

I had completed B.tech,M.tech (D). I am an experienced, qualified ICSE BOARD SCHOOL TEACHER with over...

Heat transfer mechanism in which no medium is required is called radiation. It refers to the movement of heat in waves, as it does not need molecules to travel through. The object need not be in direct contact with one another to transmit heat. Whenever you feel heat without actually touching the object,... read more

Like 0

Comments Lesson Posted on 05/07/2017 Tuition/BTech Tuition/BTech Computer Science Engineering Tuition/BTech Tuition/BTech Information Science Engineering Tuition/BSc Tuition/BSc Computer Science

An Interesting Discussion About Malloc And Calloc

Shiladitya Munshi

Well, I love spending time with students and to transfer whatever computing knowledge I have acquired...

What are malloc and calloc? Simply putting they are the predefined functions in C language. Malloc( ) and calloc( ) are two such functions which are used for more or less identical purpose and that is to allocate memories for any variable dynamically during execution time of the program. Give me a... read more

**What are malloc and calloc?**

Simply putting they are the predefined functions in C language.

Malloc( ) and calloc( ) are two such functions which are used for more or less identical purpose and that is to allocate memories for any variable dynamically during execution time of the program.

**Give me a brief of malloc:**

So as I have said malloc is a function; malloc must have three valid components as all other functions do have. These are (a) function name (b) function arguments and (c) function return type, that is, malloc must have a signature or prototype. Now what is the prototype of malloc? It is like following:

**(void*) malloc(unsigned int)** [Note: The actual prototype is slightly different than this, but for the time being this simplification will work]

It shows that the function name is malloc itself, it expects an unsigned integer as argument and it returns a void pointer or generic pointer. So let us discuss a bit about them.

As per the prototype, malloc expects an unsigned integer. To assimilate this, let us recall why should we use malloc? Malloc is used to allocate a chunk of memory at program run time dynamically. So we must let malloc know what the size of that chunk of memory is. Suppose we want malloc to allocate a chunk of memory where we can store 10 integers. In this case, we actually want malloc to allocate 20 bytes of memory (if we are running our program on windows). And we do it by supplying the size 20 as an argument. So the unsigned integer that is passed to malloc is actually the requirement of memory in bytes; and it is evident that the memory requirement cannot be negative any time, so the data type is unsigned.

Now what that void pointer is doing at the beginning as return type? To understand this, we have to recall that a function gives a feedback to its caller through the return type. So after allocating the memory (I admit, you do not how) malloc has to return the base pointer, I,e, the address of the starting location of the memory chunk allocated. Though void pointer, malloc actually returns this base address.

I am sure you will scream out “why void?” Wait a minute. Answer me, who has written this malloc function? Is it you or someone else? Obviously it is not you, malloc function is written by someone else. Now the original developer of malloc had no idea for which purpose you would be using this malloc. Currently, you can use malloc to allocate memory for storing some integers, or some floats or some structures defined by you. There are so many options and those options are equally likely for you. You as a programmer currently know that this malloc is being used for storing some integers or whatever else, but the original programmer had no idea about that. So malloc returns void pointer or generic pointer, a special one which can point to any type of memory generically. So it is your responsibility to properly type cast this void pointer. If you are using it to store some integers, cast void* as int*, if you are using malloc to store some Node type structures, then cast it to Struct Node*. Got it?

One last point still exists. You must have seen malloc argument to contain sizeof(), right? Why it is so?

As I have mentioned that the memory requirement is informed through the argument, it is highly possible that the memory requirement may change as the OS changes. For example in one system you may require 20 bytes to store 10 integers, while it may be 40 bytes in other system or OS. So if I hardcode my memory requirement as 20 or 40 for any specific platform, it won’t suffice the scenarios generated by other systems. So to meet the portability issue, that may rise up later, we as a programmer should not deal with the memory requirement directly. We should inform the compiler that that we need to store n number of elements only and let the compiler decide what the size of each such element is by using sizeof.

So we should call malloc with an argument (n * sizeof(int)) if we want to store n number of integers. By doing this, we are actually letting the C compiler to calculate the memory requirement (under the current OS) of one element and multiplying this with n, compiler can compute the exact memory requirement as per the current system.

As a good programmer you should never hardcode your memory requirement, it may end up in a serious problem if your program gets ported to any other OS.

Look at the following example for clear undestanding:

**To store 15 characters, do like:**

*char *pointerToCharArray;*

*int size = 15;*

*pointerToCharArray = (char*)malloc(size*sizeof(char));*

**To store n numbers of MyStructure type of structure, do like:**

*struct MyStructure *pointerToMyStructureArray;*

*pointerToMyStructureArray = (struct MyStructure*)malloc(n*sizeof(struct MyStructure));*

**To store k numbers of integers, do like:**

*int* point;*

*point = (int*)malloc(k*sizeof(int));*

Once you are done with these, you can use your pointer (like *pointerToCharArray* or *pointerToMyStructureArray* or *point as seen in the examples*) like an array with indexing. That means now *point[5]*** **will give you the integer stored at 5^{th} index of point or the sixth integer stored within the memory chunk, base address of which, is being pointed by a pointer *point***.**

**So what is calloc then? How it is different from malloc?**

Calloc is another function which, like malloc, is used for dynamic memory allocations.

Malloc if called to allocate a memory space that can store 10 integers (under windows),occupies the memory as a single chunk of 20 bytes, where calloc, if called for the same purpose, occupies 20 bytes, but not as a single chunk of memory, rather , it occupies 10 blocks of memory, each having 2 bytes (as it is under windows, as we have supposed). Hence calloc has the following prototype:

**(void*) calloc(unsigned int, unsigned int)**

The first *unsigned int* is for number of elements that you want to store and the second *unsigned int* is for memory allocation needed for storing a single element.

This is why calloc can occupy the memory space with multiple blocks, each of equal size. The void* is doing the same thing as that of malloc

So look at the following example for clear understanding:

**To store 15 characters, do like**

*char *pointerToCharArray;*

*int size = 15;*

*pointerToCharArray = (char*)calloc(size, sizeof(char));*

**To store n numbers of MyStructure type of structure, do like:**

*struct MyStructure *pointerToMyStructureArray;*

*pointerToMyStructureArray = (struct MyStructure*)calloc(n, sizeof(struct MyStructure));*

**To store k numbers of integers, do like:**

*int* point;*

*point = (int*)calloc(k, sizeof(int));*

So the syntactical difference is malloc takes one argument, while calloc takes two. But you need to have an idea why it is so. I think the above discussion tells you that.

Another point of difference is like following:

Malloc allocates the memory chunk and initializes the memory with garbage values, whereas calloc allocates the multiple block of memory chunks and initializes those with 0s (zeros)

*So we come to an end of this discussion. I am open to clear your doubts if any.*

Like 0

Comments Lesson Posted on 05/07/2017 Tuition/BTech Tuition/BTech Computer Science Engineering Tuition/BTech Tuition/BTech Information Science Engineering Tuition/BSc Tuition/BSc Computer Science

What Are The Two Forms Of #Include?

Shiladitya Munshi

Well, I love spending time with students and to transfer whatever computing knowledge I have acquired...

There are two variants of #include. The one is #include and the other one is #include”file”. In general the first form that is #include is used to include system defined header files which are searched in the standard list of system directories. The second form i,e #include”file”... read more

Like 0

Comments Lesson Posted on 05/07/2017 Tuition/BTech Tuition/BTech Computer Science Engineering Tuition/BTech Tuition/BTech Information Science Engineering Tuition/BCA Tuition

What Is the Difference Between Function And Subroutine?

Shiladitya Munshi

Well, I love spending time with students and to transfer whatever computing knowledge I have acquired...

The difference is indeed very thin and it depends on the context. In general Function is a piece of code with a name, inputs (arguments) and an output (return types). That is function should always return. Some programming languages are there which uniquely maps inputs to the corresponding outputs. But... read more

Like 0

Comments Lesson Posted on 05/07/2017 Tuition/BTech Tuition/BTech Computer Science Engineering Tuition/BTech Tuition/BTech Information Science Engineering Tuition/BCA Tuition

Do You Give Enough Importance In Writing Main () In C Language?

Shiladitya Munshi

I am sure; you guys are quite familiar with C programming, especially, while it comes to write the first line of your main function. In my class, I have seen many of my students are writing main function with many different forms. Some portion of students write like main(), some write main(void), again... read more

I am sure; you guys are quite familiar with C programming, especially, while it comes to write the first line of your main function. In my class, I have seen many of my students are writing main function with many different forms.

Some portion of students write like **main()**, some write **main(void)**, again some of the students write **void main(void)** and **int main(void)**. Now the question is which one is right?

All are right. Generally you write your C programs with Turbo C editor, or with any other, and generally they do not complain if you write any of them. But still, there is a factor of theoretical perfection. Trivial programming exercises may not be affected with whatever way you follow to declare **main** function, but in critical cases, your decision may make differences. This is why you should know which one is theoretically perfect.

As we always know that **main** is a function which gets called at the beginning of execution of any program. So like other functions, **main** must have a return type and it must expect arguments. If you are not calling your program (or your **main** likewise) from the command prompt, your **main**function should not bother for any arguments, so actually you should call your **main** with **void **argument, like **main(void)**.

Now you may raise a point that **main()** itself suggest that no arguments are passed, so what is wrong with it? See one thing, in your current compiler, the default argument is **void**, but the same may not be true with other compilers or platforms. So you may end up with portability issues! Keep in mind, A Good Programmer Never Rely On Defaults. So please don’t rely on default things any more, clearly write that your main function is not expecting any arguments by writing **main(void)**.

You already have an idea that a function can never work unless and until it is being called by any other program component. This is true for **main **also. The function main must be called by someone! Who is that? Who calls main function? It is the operating system who calls main function. Now the thing is, your operating system may decide to do any other job according to the success or failure of running your main function. It may so happen that if your program runs successfully, operating system will call a program P1, and if your program does not work, your operating system will call another program P2. So what if your operating system has no idea that your program did run actually or not? There lies the importance of return type of main. Your main function should return something to your operating system back to indicate whether it has ran successfully or not. The rule is if operating system gets an integer 0 back, it takes as main has ran successfully and any non zero value indicates the opposite. So your main program should return an integer. Hence you should write **int main(void)**. Just to add with this, don’t forget to **return 0 **at the end of your main program so that, if all of your codes run successfully, your main function is capable of returning 0 to the operating system back, indicating that it was a success.

In this point you may argue, that your programs runs quite well even if you do not provide return type to main and you just write **main(void).** How come it is possible?

Once again, at your age, you are writing just some of trivial academic codes. The situations here are not such critical that your operating system may decide any other thing depending on the success or failure of your **main(). **But, in near future, you are to write such critical programs, so get prepared from now.

Cool, so to conclude, **int main(void) **is perfect to write and I encourage you to write like that along with a return 0 at the last line.

Like 0

Comments Lesson Posted on 05/07/2017 Tuition/BTech Tuition/Design & Analysis of Algorithms Tuition/BTech Tuition/BTech Computer Science Engineering Tuition/BTech Tuition/BTech Information Science Engineering

A Tutorial On Dynamic Programming

Shiladitya Munshi

What is Dynamic Programming? Dynamic Programming, DP in short, is an intelligent way of solving a special type of complex problems which otherwise would hardly be solved in realistic time frame. What is that special type of problems? DP is not best fit for all types of complex problems, it is well... read more

**What is Dynamic Programming?**

Dynamic Programming, DP in short, is an intelligent way of solving a special type of complex problems which otherwise would hardly be solved in realistic time frame.

**What is that special type of problems?**

DP is not best fit for all types of complex problems, it is well suited for the problems with following characteristics only:

- The given problem must be decomposable in multiple smaller sub problems with similar nature.
- Sub problems must also be decomposable into still sub problems and this nesting should continue till a stage arises when the current sub problems could be solved with least cost.
- At any particular stage, the sub problems must be interdependent.
- At any specific stage the problem could be solved by solving its sub problems.

Wait. Don't jump into any conclusion right now. We have not studied the DP procedures yet! we are currently studying the nature of DP problems only. So it will be too early to compare Divide and Conquer with DP.

But this is true, that just a mere look at the characteristics of DP problems gives a feeling that DP is close to Divide and Conquer. But there is a MAJOR difference, in Divide and Conquer, at any stage, the sub problems enjoy No Inter-Dependencies.

Let us put this on hold. We will revert back to this topic once more only after we have got some experience in DP. But for the time being, take it from me that DP and Divide & Conquer are not same.

**Why do not you say how DP works?**

DP works as simple as possible. After the problem is broken down to trivial sub-problems in levels, DP starts solving the sub problems bottom up. Once a sub problem is solved, solution is written down (saved) into a table so that if the same sub problem reappears, we get a ready made solution. This is done in every level.

**What is so special about this process?**

Yes.** **It is special. See while you decompose a problems into sub problems, sub problems into sub sub problems and so on, you ultimately reach to a point when you need to solve the same sub problems many a times. And this "many" is not a child's play in real life. Lots of computational resources are unnecessarily spent on this which makes the process sluggish with poor time complexity values.

With DP you can avoid the re computations of the same sub problems.This will save a lot of time and other computational resources. But there are table look ups for solving reappearing sub problems, and this is not going to offer a bed of roses. This will surely take some time, but with hashing and some other smart alternatives, table look ups can be made easy.

**Getting out of my head! Show me how DP works with an example.**

Lets think of Fibonacci series. We know that Fib(n) = Fib(n-1) + Fib(n-2). Hence to compute Fib(4),

Fib(4) = Fib(3) + Fib(2)

= (Fib(2) + Fib(1)) + Fib(2)

= ((Fib(1) + Fib(0)) + Fib(1)) + Fib(2)

= ((Fib(1) + Fib(0)) + Fib(1)) + (Fib(1) + Fib(0))

This could easily be done with Divide and Conquer with recursion. But there will be several call for the trivial case Fib(1) and Fib(0).

But in DP style we can think that

Fib(4) ------------------- level 0

Fib(3) + Fib(2) ------------------ level 1

Fib(2) + Fib(1)-------------------------- level 2

Fib(1) + Fib(0) -------------------------------- level 3

There will be only two calls of Fib(1) and Fib(0) altogether (shown in violet at level 3). The second Fib(1) (shown in red at level 2) will not be called at all as the result of that is already with us. Similarly Fib(2) (shown in green at level 1) will not be called at all as it has already been computed at level 2. In this way we could avoid re-computations in two occasions.

This is the strength of DP. This strength seems trivial with this trivial example, but as the problem size will grow, this strength will seem to have prominent advantage. Just Think of fib(100)

**Is Dynamic Programming a process to find solution quicker?**

Yes it is, but the nature of the solution we are talking to is an optimal solution not the exact one. The principle of optimality applies if the optimal solution to a problem always contains optimal solutions to all subproblems . Take the following example:

Let us consider the problem of making N Rupees with the fewest number of Rupee coins.

Either there is a coin of value N Rupees (Exact Solution), or the set of coins making up an optimal solution for N Rupees can be divided into two nonempty subsets, n_{1} Rupees and n_{2} Rupees (Optimal Solution).

If any of the n_{1} Rupees or n_{2 }Rupees, can be made with fewer number of coins, then clearly N can be made with fewer coins, hence solution was *not* optimal.

**Tell me more on Principle of Optimality:**

*The principle of optimality holds if*

Every optimal solution to a problem contains optimal solutions to all subproblems

*The principle of optimality does not say*

If you have optimal solutions to all subproblems then you can combine them to get an optimal solution

**Example: **If we have infinite numbers of coins of 1cents, 5 cents, 10 cents only then optimal solution to make 7 cents is 5 cents + 1 cent + 1 cent, and the optimal solution to make 6 cents is 5 cents + 1 cent, but the optimal solution to make 13 cent is NOT 5 cents + 1 cent + 1 cent + 5 cents + 1 cent

But there is a way of dividing up 13 cents into subsets with optimal solutions (say, 11 cents + 2 cents) that will give an optimal solution for 13 cents. Hence, the principle of optimality holds for this problem.

Let us see one example where Principle of Optimality does not hold.

In the following graph

The longest simple path (path not containing a cycle) from A to D is A->B->C->D. However, the sub path A->B is not the longest simple path from A to B (A->C->B is longer)

The principle of optimality is not satisfied for this problem. Hence, the longest simple path problem cannot be solved by a dynamic programming approach.

**Can you give me a thorough example of DP? **

Why not! Following is an example of working of Dynamic Programming. It presents a comparative analysis of working of DP with the working of Divide & Conquer.

Let us consider the Coin Counting Problem. It is to find the minimum number of coins to make any amount, given a set of coins.

If we are given with a set of coin of 1 unit, 10 units and 25 units, then to make 31, how many minimum numbers of coins are required?

Let us check whether the greedy method will work or not. Greedy Method says that just choose the largest coin that does not overshoot the desired amount. So at the first step, we will take one coin of 25 units and then successively in each of next six steps, we will take one 1 unit coin. So ultimately the solution of Greedy Method is 31 = 25 + 1 + 1 + 1 + 1 + 1 + 1 (Total 7 nk!umbers of coins needed)

But evidently there is better solution like 31 = 10 + 10 + 10 + 1 (only 4 numbers of coins are needed).

Hence Greedy Method will never work.

Now let us check whether any better algorithm exists or not! What about the following?

*To make K units:*

*If there is a K unit coin, then that one coin is the minimum*

*Otherwise, for each value i < K,*

*Find the minimum number of coins needed to make i units*

*Find the minimum number of coins needed to make K - i units*

*Choose the value of i that minimizes this sum*

* *Yes. This will work. This is actually following Divide & Conquer Principle but there are two problems with this. This solution is very recursive and it requires exponential amount of work to be done.

Now, if we fix the given set of coins as 1, 5, 10, 21, 25 and if the desired amount is 63, then the previous solution will require solving 62 recursive sub problems.

What If we think to choose the best solution among?

- One 1 unit coin plus the best solution for 62 units
- One 5 units coin plus the best solution for 58 units
- One 10 units coin plus the best solution for 53 units
- One 21 units coin plus the best solution for 42 units
- One 25 units coin plus the best solution for 38 units

In this case, we need to solve only 5 recursive sub problems. So obviously, this second solution is better than the first solution. But still, this second solution is also very expensive.

Now let us check how DP can solve it!

To make it shorter in length, let us think that desired value is 13 units and the set of coin given is 1 unit, 3 units, and 4 units.

DP solves first for one unit, then two units, then three units, etc., up to the desired amount and saves each answer in a table (Memoization). Hence it goes like

**For each new amount N, compute all the possible pairs of previous answers which sum to N**

For example, to find the solution for 13 units,

First, solve for all of 1 unit, 2 units, 3 units, ..., 12 units

Next, choose the best solution among:

- Solution for 1unit + solution for 12 units
- Solution for 2 units + solution for 11 units
- Solution for 3 units + solution for 10 units
- Solution for 4 units + solution for 9 units
- Solution for 5 units + solution for 8 units
- Solution for 6 units + solution for 7 units

This will run like following:

There’s only one way to make 1unit (one coin)

To make 2 units, try 1 unit +1 unit (one coin + one coin = 2 coins)

To make 3 units, just use the 3 units coin (one coin)

To make 4 units, just use the 4 units coin (one coin)

To make 5 units, try

- 1 unit + 4 units (1 coin + 1 coin = 2 coins)
- 2 units + 3 units (2 coins + 1 coin = 3 coins)
- The first solution is better, so best solution is 2 coins

To make 6 units, try

- 1 unit + 5 units (1 coin + 2 coins = 3 coins)
- 2 units + 4 units (2 coins + 1 coin = 3 coins)
- 3 units + 3 units (1 coin + 1 coin = 2 coins) – best solution

Etc.

**Ok. I got it but how could you say that computationally this is the best?**

The first algorithm is recursive, with a branching factor of up to 62. Possibly the average branching factor is somewhere around half of that (31). So the algorithm takes exponential time, with a large base.

The second algorithm is much better—it has a branching factor of 5. Still this is exponential time, with base 5.

The dynamic programming algorithm is O(N*K), where N is the desired amount and K is the number of different kinds of coins.

So I don’t hesitate to say that computationally, DP algorithm works best among these threes.

**What is this Matrix Chain Multiplication Problem?**

Suppose we have a sequence or chain A_{1}, A_{2}, …, A_{n} of n matrices to be multiplied. That is, we want to compute the product A_{1}A_{2}…A_{n}. Now there are many possible ways (parenthesizations) to compute the product.

Let us consider the chain A_{1}, A_{2}, A_{3}, A_{4} of 4 matrices. Now to compute the product A_{1}A_{2}A_{3}A_{4,}there are 5 possible ways as described below:

(A_{1}(A_{2}(A_{3}A_{4}))), (A_{1}((A_{2}A_{3})A_{4})), ((A_{1}A_{2})(A_{3}A_{4})), ((A_{1}(A_{2}A_{3}))A_{4}), (((A_{1}A_{2})A_{3})A_{4})

Each of these options may lead to the different number of scalar multiplications, and we have to select the best one (option resulting fewer number of Scalar Multiplications)

Hence the problem statement looks something like: “Parenthesize the product A_{1}A_{2}…A* _{n }*such that the total number of scalar multiplications is minimized”

Please remember that the objective of Matrix Chain Multiplication is not to do the multiplication physically, rather the objective is to fix the way of that multiplication ordering so that the number of scalar multiplication gets minimized.

**Give me one real example:**

Ok. But before I show you one real example, let us revisit the algorithm which multiplies two matrices. It goes like following:

*Input**: Matrices A _{p×q} and B_{q×r} (with dimensions p×q and q×r)*

*Result**: Matrix C _{p×r} resulting from the product A·B*

*MATRIX-MULTIPLY**(A _{p×q }, B_{q×r})*

**for**i ← 1**to**p**for**j ← 1**to**r*C[i, j] ← 0***for**k ← 1**to**q*C[i, j] ← C[i, j] + A[i, k] · B[k, j]***return**C

In the above algorithm, scalar multiplication in line 5 dominates time to compute *C *Number of scalar multiplications = *pqr*

Now on the basis of above algorithm what if we try to multiply three matrices A_{10}_{´100}, B_{100}_{´5}, and C_{5}_{´50}?

There are 2 ways to parenthesize

– ((AB)C) = D_{10}_{´5} · C_{5}_{´50}

- AB Þ 10·100·5=5,000 scalar multiplications
- DC Þ 10·5·50 =2,500 scalar multiplications
- Total number of scalar multiplications 7,500

– (A(BC)) = A_{10}_{´100} · E_{100}_{´50}

- BC Þ 100·5·50=25,000 scalar multiplications
- AE Þ 10·100·50 =50,000 scalar multiplications
- Total number of scalar multiplications 75,000

It is evident that the first option will result the fewer number of scalar multiplication and it is the best one for computational easiness.

Hope now you understand what I mean.

**How do you know that this problem could be solved through Dynamic Programming?**

See, there are some clear evidences that this problem is perfect fit to be solved through Dynamic Programming.

In connection to the Matrix Chain Multiplication, the optimal solution to the problem contains within it the optimal solution to subproblems. That is why we can say that this problem will better be solved by Dynamic Programming. Now the question is how we came to a conclusion that the principle of optimality holds true in this case?

Looking back to the problem, we are given with a chain A_{1}, A_{2}, …, A_{n} of n matrices, where for i=1, 2, …, n, matrix A_{i} has dimension p_{i-1}´p_{i. }We need to search for optimal solution of parenthesization in order to minimize the scalar computation.

Hence to find the structure of the optimal solution :

- Let us use the notation A
_{i}_{..j}for the matrix that results from the product AA_{i}_{i}_{+1}… A_{j}

Let us admit that an optimal parenthesization of the product A_{1}A_{2}…A* _{n}* splits the product between A

- So we have to compute matrices A
_{1..k}and A_{k}_{+1..n}first; then multiply them to get the final matrix A_{1..n}

The Key observation here is the** **parenthesizations of the subchains A_{1}A_{2}…A* _{k }*and A

Hence Dynamic Programming Principle could effectively be used for Matrix Chain Multiplication problem.

**What is the Dynamic Programming approach particularly for this problem?**

Let m[i, j] be the minimum number of scalar multiplications necessary to compute A_{i..j} . So minimum cost to compute A_{1..n} is m[1, n]

Suppose the optimal parenthesization of A_{i..j} splits the product between A_{k} and A_{k+1} for some integer k where i ≤ k < j. Hence A_{i..j} = (A_{i }A_{i+1}…A_{k})·(A_{k+1}A_{k+2}…A_{j})= A_{i..k} · A_{k+1..j}

We get Cost of computing A_{i..j} = cost of computing A_{i..k} + cost of computing A_{k+1..j} + cost of multiplying A_{i..k} and A_{k+1..j}

Now Cost of multiplying A_{i..k} and A_{k+1..j }is p_{i-1}p_{k }p_{j}

So evidently m[i, j ] = m[i, k] + m[k+1, j ] + p_{i-1}p_{k }p_{j } for i ≤ k < j and m[i, i ] = 0 for i=1,2,…,n

But optimal parenthesization occurs at one value of k among all possible i ≤ k < j, so check all these and select the best one.

So the optimal substructure relation is like following:

m[i, j ] = 0 if i=j

min {m[i, k] + m[k+1, j ] + p_{i-1}p_{k} p_{j} } if i<j

* i ≤ k< j*

To keep track of how to construct an optimal solution, we use a table s. s[i, j ] = value of k at which A_{i} A_{i+1} … A_{j} is split for optimal parenthesization.

**Wait a minute, I got almost everything except that p array what is it? Where did it come from?**

The P array stores the dimensions of the matrices. Suppose we are to multiply 3 matrices of dimension 5* 10, 10* 3 and 3*8, in this case the length of p array will be (3+1) 4 and it will be like P[0] = 5, p[1] = 10, p[2] = 3 and p[3]=8.

So generalizing, if you have n matrices to be multiplied, take the length of p as n+1, then fill p[0] with row number of 1^{st} matrix, fill p[n] with column no of nth matrix, and for the intermediate indices go like following

P[1] = col no of 1^{st} matrix or row no of 2^{nd} matrix

P[2] = col no of 2^{nd} matrix or row no of 3^{rd} matrix

P[3] = col no of 3^{rd} matrix or row no of 4^{th} matrix

…….

P[n-1] = col no of (n-1)th matrix or row no of nth matrix.

**Now I got it. Anyways, how is the algorithm?**

*Input:* Array *p*[0…*n*] containing matrix dimensions and *n*

*Result*: Minimum-cost table *m* and split table *s*

*MATRIX-CHAIN-ORDER(p[ ], n)*

**for ***i *← 1 **to** *n*

* m*[*i, i*]* *← 0

**for ***l *← 2 **to** *n*

**for ***i *← 1 **to** *n-l+*1

*j* * *← *i*+*l*-1

*m*[*i, j*]* *← **¥**

**for ***k *← *i* **to** *j-*1

*q* ← *m*[*i, k*]* + m*[*k*+1*, j*]* + p*[*i*-1] *p*[*k*] *p*[*j*]

* ***if** *q* < *m*[*i, j*]

* m*[*i, j*]* *← *q*

*s*[*i, j*]* *← *k*

* return* *m* and *s*

Like 0

Comments Lesson Posted on 05/07/2017 Tuition/BTech Tuition/Design & Analysis of Algorithms Tuition/BTech Tuition/BTech Computer Science Engineering Tuition/BTech Tuition/BTech Information Science Engineering

Understanding Big Omega (?), Big Theta (?), Small Oh (o) And Small Omega (?) Notations

Shiladitya Munshi

How to describe Big Omega(Ω) ? If run time of an algorithm is of Ω(g(n)), it means that the running time of the algorithm (as n gets larger) is at least proportional to g(n). Hence it helps in estimating a lower bound of the number of basic operations to be performed. More specifically,... read more

If run time of an algorithm is of Ω(g(n)), it means that the running time of the algorithm (as n gets larger) is at least proportional to g(n). Hence it helps in estimating a lower bound of the number of basic operations to be performed.

More specifically,

`f(x) = Ω(g(x))`

(big-omega) means that the growth rate of `f(x)`

is asymptotically greater than or equal to the growth rate of `g(x)`

Mathematically, a function f(x) is equal to Big Omega of another function g(x), i,e f(x) = Ω(g(x) is true if and only if there exists two constants (C1 and C2)such that

a) C1 and C2 are always positive

b) 0<= C1*g(n) <= f(n) for any value of n => C2

If run time of an algorithm is of Θ(g(n)), it means that the running time of the algorithm (as n gets larger) is equal to the growth rate of g(n). Hence it helps in estimating a tight bound of the number of basic operations to be performed.

Hence

`f(x) = Θ(g(x))`

(big - theta) means that the growth rate of `f(x)`

is asymptotically equal to the growth rate of `g(x)`

Mathematically, a function f(x) is equal to Big Theta of another function g(x), i,e f(x) = Θ(g(x) is true if and only if there exists three constants (C1 and C2 and C3)such that

a) C1, C2 and C3 are always positive

`b) 0<= C1*g(n) <= f(n) <= C2*g(n) for any value of n => C3`

`What are Small Oh and Small Omega?`

`f(x) = o(g(x)) (small-oh) means that the growth rate of f(x) is asymptotically less than to the growth rate of g(x).`

Mathematically, a function f(x) is equal to Small Oh of another function g(x), i,e f(x) = o(g(x) is true if and only if there exists two constants (C1 and C2)such that

a) C1 and C2 are always positive

b) 0<= f(n) <C1*g(n) for any value of n => C2

So this gives a loose upper bound for complexities of f(x).

`On the other hand, f(x) = ω(g(x))`

(small-omega) means that the growth rate of `f(x)`

is asymptotically greater than the growth rate of `g(x).`

Mathematically, a function f(x) is equal to Small Omega of another function g(x), i,e f(x) = ω(g(x) is true if and only if there exists two constants (C1 and C2)such that

a) C1 and C2 are always positive

`b) 0<= C1*g(n) < f(n) for any value of n => C2`

`So this gives a loose lower bound for complexities of f(x).`

Like 0

Comments Lesson Posted on 05/07/2017 Tuition/BTech Tuition/Design & Analysis of Algorithms Tuition/BTech Tuition/BTech Computer Science Engineering Tuition/BTech Tuition/BTech Information Science Engineering

Understanding Asymptotic Notations And Big Oh(O)

Shiladitya Munshi

What are asymptotic notations for complexity analysis?A problem may have numerous algorithmic solutions. In order to choose the best algorithm for a particular task, you need to be able to judge how long a particular solution will take to run. Or, more accurately, you need to be able to judge how long... read more

**What are asymptotic notations for complexity analysis?**

A problem may have numerous algorithmic solutions. In order to choose the best algorithm for a particular task, you need to be able to judge how long a particular solution will take to run. Or, more accurately, you need to be able to judge how long two solutions will take to run, and choose the better of the two. You don't need to know how many minutes and seconds they will take, but you do need some way to compare algorithms against one another.

Asymptotic notations are just used for this, i,e they are used for comparing two functions of two different algorithms.

Let us suppose I write f(n) = W(g(n)) where W is an asymptotic notation. Here this expression says how the function f(x) grows in comparison to another function g(n).**What are the most common Asymptotic Notations used in Complexity Analysis? **

Most common asymptotic notations used for time complexity analysis are Big Oh (O), Big Theta (Θ), Big Omega (Ω), Small Oh (o) and Small Omega (ω). Let us discuss them one by one**How to describe Big Oh (O) ?**

If run time of an algorithm is of O(g(n)), it means that the running time of the algorithm (as n gets larger) is at most proportional to g(n). Hence it helps in estimating an upper bound of the number of basic operations to be performed.

Mathematically, a function f(x) is equal to Big Oh of another function g(x), i,e f(x) = O(g(x) is true if and only if there exists two constants (C1 and C2)such that

a) C1 and C2 are always positive

b) 0<= f(n) <= C1*g(n) for any value of n => C2

Let us have an example for this with f(n) being 2n^2 and g(n) being n^3.

Let us check whether 2n^2 = O(n^3) is true or not

if we take C1 = 1 and C2 = 2 (all positive maintaining condition described in a), then for n = 3 (that is value of n greater than value of C2), we have the following relation true

0<= 1*(2*3^2)<= 3^3.

Hence 2n^2 = O(n^3) is true for C1 = 1 and C2 = 2.

Like 0

Comments Getting A Bit Deeper Into Time Complexity Analysis

Shiladitya Munshi

What is Time Complexity Analysis? In the last blog, you got a rough idea about the Time Complexity and that was all about to judge how fast the algorithm can run, or putting it in another way, how much time an algorithm should require while running. Suppose, someone asks you that how fast you can do... read more

**What is Time Complexity Analysis?**

In the last blog, you got a rough idea about the Time Complexity and that was all about to judge how fast the algorithm can run, or putting it in another way, how much time an algorithm should require while running.

Suppose, someone asks you that how fast you can do a job or how much time do you require finishing a job. Most probably, your answer will be any of these threes (A) at most time t or (B) at least time t or (C) exactly time t. Whatever your answer might be, your answer must have been guided by identification of the number of basic operation needed to complete the job. So unless and until you do have a clear cut idea of how many basic operations are needed to be performed, you cannot say how much time you do require finishing a job, Right?

Similar is the case of answering how much time is required executing an algorithm. You need to identify first that how many basic operations (like comparison, memory access etc.) this algorithm performs. Once you figure it out, then you are all set to compute how fast you can do these all.

This computation is not an easy business. It is done through establishing a relationship between the run time (execution time) of the given algorithm and the input size of the problem, which the given algorithm is supposed to solve. Sounds weird? You might be wondering what about the “*number of basic operations needed*”? Why did you identified that all?

Genuine, your doubts are well accepted. But the thing is, the number of basic operations needed for an algorithm depends on the input size of the problem and that is why we are really interested to have a relationship between the run time and the input size. This relationship actually gives you a clear idea about the time required to run an algorithm and hence about the time complexity.

**What is the physical significance of this relationship? What are its features?**

Well, a relationship between the run time and input size gives you the nature of the growth of time complexity. The growth indicates physically that on increasing the input size, how the run time changes. This relationship has a form of function which does not deal with any exact quantification; rather, it is expressed as a proportion called the “Order”. Suppose, if the run time of an algorithm increases with the same proportion of the increase in input size, then the run time is of *linear* order.

**Why do we need to know about the run time complexity? What are the objectives?**

The objective of computing run time complexity is twofold. Firstly it gives a measure of efficiency of an algorithm with respect to run/execution time and secondly, in presence of multiple algorithms for a specific problem, it helps in deciding which one to choose for implementation. That means comparison among different algorithms for the same problem is a huge benefit that we can derive from Time Complexity analysis.

**How does the Time Complexity Analysis get realized?**

There are mainly three classes of Time Complexity Analysis. (A) *Worst Case Analysis* – It estimates the *upper bound* of the number of basic operations needed to be performed if the algorithm is to be executed, and (B) *Best Case Analysis* – It estimates the lower bound of the number of operations needed to be performed if the algorithm is to be executed, and lastly (C) Average Case Analysis – any estimation in between.

If not said otherwise, in the rest of all our discussions, Time Complexity Analysis will always indicate the Worst Case Analysis.

**Characteristics of computing Time Complexity**

While computing time complexity, generally following characteristics are maintained –

- If any number of basic operations get identified which are independent of input size of the problem, the time complexity for that gets identified with
*Constant*order. - While comparing multiple algorithms, the Time Complexity analysis should ignore the common tasks
- If the Time Complexity expression is realized with a polynomial, then the order of time complexity is dictated by the highest order of the polynomial

**Give me one example**

Let us suppose we need to compute f(x) = 7x^4 + 6x^3 -5x^2 + 8x -5.

To compute this polynomial, we can consider two algorithms, (A) Brute Force Algorithm and (B) Horner’s Algorithm.

Brute Force Algorithm computes f(x) as 7*x*x*x*x + 6*x*x*x - 5*x*x + 8*x -5 and Horner’s Algorithm computes f(x) as (((7*x + 6)*x – 5)*x + 8)*x – 5.

Both the algorithms perform two additions and two subtractions apart from some number of multiplications which are different for the two cases. Hence we will ignore the basic operations addition and subtraction and will concentrate only on the number of multiplications.

Brute Force Algorithm, according to the example, for an input size n does k number of multiplications where k = n + (n-1)+(n-2)+……+2+1+0 = (n(n-1))/2.

On the other hand Horner’s Algorithm, as seen in the example, for an input size n, does k’ number of multiplications where k’ = n.

So the order of Time Complexity of Brute Force Algorithm is expressed by the polynomial (n(n-1))/2 I,e n^2/2 + n/2. Hence finally the order of time complexity for Brute Force Algorithm will be dictated by n^2. It means the run time complexity of the Brute Force Algorithm increases proportional to the square of the input size.

In comparison, the time complexity of Horner’s algorithm is dictated by the term n only, which means that the increase in run time of Horner’s algorithm is linearly proportional to the input size.

It is evident from the discussion that the Horner’s Algorithm has a better run time than Brute Force Algorithm for computation of polynomial expressions.

read less Like 0

Comments Introductory Discussions On Complexity Analysis

Shiladitya Munshi

What is Complexity Analysis of Algorithm? Complexity Analysis, simply put, is a technique through which you can judge about how good one particular algorithm is. Now the term “good” can mean many things at different times. Suppose you have to go from your home to the Esplanade! There are... read more

**What is Complexity Analysis of Algorithm?**

Complexity Analysis, simply put, is a technique through which you can judge about how good one particular algorithm is. Now the term “*good*” can mean many things at different times.

Suppose you have to go from your home to the Esplanade! There are many ways from your home that may lead to Esplanade. Take any one, and ask whether this route is good or bad. It may so happen that this route is *good* if the time of travel is concerned (that is the route is short enough), but at the same time, it may be considered *bad* taking the comfort into considerations (This route may have many speed breakers leading to discomforts). So, the goodness (or badness as well) of any solution depends on the situations and whatever is *good* to you right now, may seem as *bad* if the situation changes. In a nutshell, the goodness/badness or the efficiency of a particular solution depends on some criteria of measurements.

**So what are the criteria while analyzing complexities of algorithms?**

Focusing only on algorithms, the criteria are *Time* and *Space*. The criteria *Time*, judges how fast or slow the algorithms run when executed; and the criteria *Space *judges how big or small amount of memory (on primary/hard disks) is required to execute the algorithm. Depending on these two measuring criteria, two type of Algorithm Analysis are done; one is called *Time Complexity Analysis* and the second one is *Space Complexity Analysis*.

**Which one is more important over the other?**

I am sorry! I do not know the answer; rather there is no straight forward answer to this question. Think of yourself. Thinking of the previous example of many solutions that you have for travelling from your home to Esplanade, which criteria is most important? Is it *Time of Travel*, or is it *Comfort*? Or is it *Financial Cost*? It depends actually. While you are in hurry for shopping at New Market, the *Time Taken* would probably be your choice. If you have enough time in your hand, if you are in jolly mood and if you are going for a delicious dinner with your friends, probably you would choose *Comfort*; and at the end of the month, when you are running short with your pocket money, the *Financial Cost* would be most important to you. So the most important criterion is a dynamic notion that evolves with time.

Twenty or thirty years back, when the pace of advancement of Electronics and Computer Hardware was timid, computer programs were forced to run with lesser amount of memory. Today you may have gigantic memory even as RAM, but that time, thinking of a very large hard disk was a day dreaming! So at that time, *Space Complexity* was much more important than the *Time Complexity, *because we had lesser memory but ample times.

Now the time has changed! Now a day, we generally enjoy large memories but sorry, we don’t have enough time with us. We need every program to run as quick as possible! So currently, *Time Complexity* wins over *Space Complexity*. Honestly, both of these options are equally important from theoretical perspective but the changing time has an effect to these. ** **

Like 0

Comments UrbanPro.com helps you to connect with the best BTech Tuition in India. Post Your Requirement today and get connected.

x

Ask a Question