C Code for Longest Common Subsequence Using Dynamic Programming

Here's the C Code for LCS using Dynamic programming :-


Output:-

Output:-

Matrix Generated

0 |0 |0 |0 |0 |
0 |0 |0 |0 |0 |
0 |1 |1 |1 |1 |
0 |1 |2 |2 |2 |
0 |1 |2 |3 |3 |
0 |1 |2 |3 |4 |

Length of Longest Common Subsequence = 4

Continue Reading →

C Code for Knapsack Problem using Dynamic Programming

Knapsack problem (Photo credit: Wikipedia)

Knapsack Problem using Dynamic Programming.

Code:-


Sample Output:- 

Enter the number of elements : 3

Enter the profit and weights of the elements

Item no : 1

4 6

Item no : 2

1 2

Item no : 3

7 3

Enter the capacity

7

Items in the KnapSack are :

Sl.no    weight          profit

----------------------------------------

1        2                1

2        3                7

Total profit = 8

Continue Reading →

String Permutations Algorithm with example code in C/C++

Permutations of 3 balls (Photo credit: Wikipedia)

Hello Everyone,

Today I will be telling you how to print all the possible permutations of a string provided by the user. I will show you the recursive way to do this. The programming paradigm that we use in case of Recursion is backtracking.

What do you mean by Permutations ?

A permutation, also called an “arrangement number” or “order,” is a rearrangement of the elements of an ordered list S into a one-to-one correspondence with S itself. A string of length n has n! permutation.

For more info visit here --> http://mathworld.wolfram.com/Permutation.html

Recursion

This is a bad method for printing permutations since its time complex i.e. it takes more time to execute than the iterative method this is because of the extensive use of the call stack. Now the following image explains the recursion technique. The image presents the recursion tree of the method of permutations generation. We take the example string that we permute as "GOD".

In order to find all possible combinations for a given string, then start at a position i, then find and place all possible letters in position i. Every time we put a new letter in position i, we should then find all the possible combinations at position i+1 – this would be the recursive call that we make.

Here's the C++ implementation string permutation.

Now the above code will print all the permutations of the string "GOD" without repetition. But if you want to print them lexicographic manner i.e where the repetitions of the characters are included then read the matter below.

Since we are going in lexicographic order, so we have to do the following ,its pretty much understandable. (Note : the numbers represent index and 1 means the starting index , we will not use 0 for the first index as we do it in programming.)

• Start with index '1' and then recurse over rest of the 'n - 1' numbers.
                 
  • Start with '2' and then recurse over rest of the 'n - 2' numbers.
  • Start with '3' and then recurse over rest of the 'n - 2' numbers.
    :
    :
  • Start with 'i' and then recurse over rest of the 'n - 2' numbers.
    :
    :
  • Start with 'n' and then recurse over rest of the 'n - 2' numbers.
    
• Start with a '2' and then recurse over rest of the 'n - 1' numbers.
  
  
  • Start with '1' and then recurse over rest of the 'n - 2' numbers.
  • Start with '3' and then recurse over rest of the 'n - 2' numbers.
    :
    :
  • Start with 'i' and then recurse over rest of the 'n - 2' numbers.
    :
    :
  • Start with 'n' and then recurse over rest of the 'n - 2' numbers.
    
• :
  :
• Start with 'i' and then recurse over rest of the 'n - 1' numbers.
  :
  :
• Start with 'n' and then recurse over rest of the 'n - 1' numbers.

Important thing to note is, in every recursion you start with the minimum numbers left, to be printed, and then keep picking the next minimum, and so on, till you exhaust all the 'n' numbers.

Here's the C Code for Lexicographical Permutations.

Related articles

• How To copy a Very large file to a flash drive in Linux
• 3D Rotating Square with WebGL in Three.js
• Example of Path class in Java NIO
• Don't Call Yourself A Programmer
• The Hackers Manifesto - Conscience of a Hacker
• Java Code to implement a Stack using Java Generics

Continue Reading →

Comma as Sequential-Evaluation Operator in C/C++

In C and C++, comma (,) can be used in two ways:

Syntax

expression:
             assignment-expression
             expression , assignment-expression

The left operand of the sequential-evaluation operator is evaluated as a void expression. The result of the operation has the same value and type as the right operand. Each operand can be of any type. The sequential-evaluation operator does not perform type conversions between its operands, and it does not yield an l-value. There is a sequence point after the first operand, which means all side effects from the evaluation of the left operand are completed before beginning evaluation of the right operand.

The sequential-evaluation operator is typically used to evaluate two or more expressions in contexts where only one expression is allowed.

Commas can be used as separators in some contexts. However, you must be careful not to confuse the use of the comma as a separator with its use as an operator; the two uses are completely different.

1) Comma as an operator:

The comma operator (represented by the token ,) is a binary operator that evaluates its first operand and discards the result, it then evaluates the second operand and returns this value (and type). The comma operator has the lowest precedence of any C operator, and acts as a sequence point.

A sequence point defines any point in a computer program's execution at which it is guaranteed that all side effects of previous evaluations will have been performed, and no side effects from subsequent evaluations have yet been performed.

/* comma as an operator */

int i = (5, 10);  /* 10 is assigned to i*/

int j = (func1(), func2());  /* func1() is evaluated first followed by func2(). The returned value of func2() is assigned to j */

2) Comma as a separator:

Comma also acts as a separator when used with function calls and definitions, function like macros, variable declarations, enum declarations, and similar constructs.

/* comma as a separator */

int a = 1, b = 2;
void func(x, y);

The use of comma as a separator should not be confused with the use as an operator. For example, in below statement, func1() and func2() can be called in any order.

/* Comma acts as a separator here and doesn't enforce any sequence. Therefore, either f1() or f2() can be called first */

void func(func1(), func2());

Have a look at this :- http://stackoverflow.com/questions/2087026/effect-of-using-a-comma-instead-of-a-semi-colon-in-c-and-c

See the programs below to check your understanding of comma in C.

#include<stdio.h>
int main()
{
   int x = 10;
   int y = 15;

   printf("%d", (x, y));
   return 0;
}

#include<stdio.h>
int main()
{
    int x = 10, y;

    //Equavalent to y = x++
    y = (x++, printf("x = %d\n", x), ++x, printf("x = %d\n", x), x++);

    // Note that last expression is evaluated
    // but side effect is not updated to y
    printf("y = %d\n", y);
    printf("x = %d\n", x);
    return 0;
}

References:

http://en.wikipedia.org/wiki/Comma_operator
http://msdn.microsoft.com/en-us/library/zs06xbxh.aspx

Related articles

• How To copy a Very large file to a flash drive in Linux
• Write a File using Java NIO
• 3D Rotating Square with WebGL in Three.js
• LaTeX Math Symbols
• Generate Wordlists in Backtrack 5 R3 using Crunch

Continue Reading →