Category: Subjects

Bubble Sort Algorithm | Example | Time Complexity

Bubble Sort-

 

  • Bubble sort is the easiest sorting algorithm to implement.
  • It is inspired by observing the behavior of air bubbles over foam.
  • It is an in-place sorting algorithm.
  • It uses no auxiliary data structures (extra space) while sorting.

 

How Bubble Sort Works?

 

  • Bubble sort uses multiple passes (scans) through an array.
  • In each pass, bubble sort compares the adjacent elements of the array.
  • It then swaps the two elements if they are in the wrong order.
  • In each pass, bubble sort places the next largest element to its proper position.
  • In short, it bubbles down the largest element to its correct position.

 

Bubble Sort Algorithm-

 

The bubble sort algorithm is given below-

 

for(int pass=1 ; pass<=n-1 ; ++pass)     // Making passes through array
{
    for(int i=0 ; i<=n-2 ; ++i)
    {
        if(A[i] > A[i+1])                // If adjacent elements are in wrong order
            swap(i,i+1,A);               // Swap them
    }
}

//swap function : Exchange elements from array A at position x,y

void swap(int x, int y, int[] A)
{
    int temp = A[x];
    A[x] = A[y];
    A[y] = temp;
    return ;
}

// pass : Variable to count the number of passes that are done till now
// n : Size of the array
// i : Variable to traverse the array A
// swap() : Function to swap two numbers from the array
// x,y : Indices of the array that needs to be swapped

 

Bubble Sort Example-

 

Consider the following array A-

 

 

Now, we shall implement the above bubble sort algorithm on this array.

 

Step-01:

 

  • We have pass=1 and i=0.
  • We perform the comparison A[0] > A[1] and swaps if the 0th element is greater than the 1th element.
  • Since 6 > 2, so we swap the two elements.

 

 

Step-02:

 

  • We have pass=1 and i=1.
  • We perform the comparison A[1] > A[2] and swaps if the 1th element is greater than the 2th element.
  • Since 6 < 11, so no swapping is required.

 

 

Step-03:

 

  • We have pass=1 and i=2.
  • We perform the comparison A[2] > A[3] and swaps if the 2nd element is greater than the 3rd element.
  • Since 11 > 7, so we swap the two elements.

 

 

Step-04:

 

  • We have pass=1 and i=3.
  • We perform the comparison A[3] > A[4] and swaps if the 3rd element is greater than the 4th element.
  • Since 11 > 5, so we swap the two elements.

 

 

Finally after the first pass, we see that the largest element 11 reaches its correct position.

 

Step-05:

 

  • Similarly after pass=2, element 7 reaches its correct position.
  • The modified array after pass=2 is shown below-

 

 

Step-06:

 

  • Similarly after pass=3, element 6 reaches its correct position.
  • The modified array after pass=3 is shown below-

 

 

Step-07:

 

  • No further improvement is done in pass=4.
  • This is because at this point, elements 2 and 5 are already present at their correct positions.
  • The loop terminates after pass=4.
  • Finally, the array after pass=4 is shown below-

 

 

Optimization Of Bubble Sort Algorithm-

 

  • If the array gets sorted after a few passes like one or two, then ideally the algorithm should terminate.
  • But still the above algorithm executes the remaining passes which costs extra comparisons.

 

Optimized Bubble Sort Algorithm-

 

The optimized bubble sort algorithm is shown below-

 

for (int pass=1 ; pass<=n-1 ; ++pass)
{
    flag=0                                // flag denotes are there any swaps done in pass

    for (int i=0 ; i<=n-2 ; ++i)
    {
        if(A[i] > A[i+1])
        {
            swap(i,i+1,A);
            flag=1                        // After swap, set flag to 1
        }
    }

    if(flag == 0) break;                  // No swaps indicates we can terminate loop
}

void swap(int x, int y, int[] A)
{
    int temp = A[x];
    A[x] = A[y];
    A[y] = temp;
    return;
}

 

Explanation-

 

  • To avoid extra comparisons, we maintain a flag variable.
  • The flag variable helps to break the outer loop of passes after obtaining the sorted array.
  • The initial value of the flag variable is set to 0.
  • The zero value of flag variable denotes that we have not encountered any swaps.
  • Once we need to swap adjacent values for correcting their wrong order, the value of flag variable is set to 1.
  • If we encounter a pass where flag == 0, then it is safe to break the outer loop and declare the array is sorted.

 

Time Complexity Analysis-

 

  • Bubble sort uses two loops- inner loop and outer loop.
  • The inner loop deterministically performs O(n) comparisons.

 

Worst Case-

 

  • In worst case, the outer loop runs O(n) times.
  • Hence, the worst case time complexity of bubble sort is O(n x n) = O(n2).

 

Best Case-

 

  • In best case, the array is already sorted but still to check, bubble sort performs O(n) comparisons.
  • Hence, the best case time complexity of bubble sort is O(n).

 

Average Case-

 

  • In average case, bubble sort may require (n/2) passes and O(n) comparisons for each pass.
  • Hence, the average case time complexity of bubble sort is O(n/2 x n) = Θ(n2).

 

The following table summarizes the time complexities of bubble sort in each case-

 

Time Complexity
Best CaseO(n)
Average CaseΘ(n2)
Worst CaseO(n2)

 

From here, it is clear that bubble sort is not at all efficient in terms of time complexity of its algorithm.

 

Space Complexity Analysis-

 

  • Bubble sort uses only a constant amount of extra space for variables like flag, i, n.
  • Hence, the space complexity of bubble sort is O(1).
  • It is an in-place sorting algorithm i.e. it modifies elements of the original array to sort the given array.

 

Properties-

 

Some of the important properties of bubble sort algorithm are-

  • Bubble sort is a stable sorting algorithm.
  • Bubble sort is an in-place sorting algorithm.
  • The worst case time complexity of bubble sort algorithm is O(n2).
  • The space complexity of bubble sort algorithm is O(1).
  • Number of swaps in bubble sort = Number of inversion pairs present in the given array.
  • Bubble sort is beneficial when array elements are less and the array is nearly sorted.

 

PRACTICE PROBLEMS BASED ON MERGE SORT ALGORITHM-

 

Problem-01:

 

The number of swapping needed to sort the numbers 8, 22, 7, 9, 31, 5, 13 in ascending order using bubble sort is-  (ISRO CS 2017)

  1. 11
  2. 12
  3. 13
  4. 10

 

Solution-

 

In bubble sort, Number of swaps required = Number of inversion pairs.

Here, there are 10 inversion pairs present which are-

  1. (8,7)
  2. (22,7)
  3. (22,9)
  4. (8,5)
  5. (22,5)
  6. (7,5)
  7. (9,5)
  8. (31,5)
  9. (22,13)
  10. (31,13)

 

Thus, Option (D) is correct.

 

Problem-02:

 

When will bubble sort take worst-case time complexity?

  1. The array is sorted in ascending order.
  2. The array is sorted in descending order.
  3. Only the first half of the array is sorted.
  4. Only the second half of the array is sorted.

 

Solution-

 

  • In bubble sort, Number of swaps required = Number of inversion pairs.
  • When an array is sorted in descending order, the number of inversion pairs = n(n-1)/2 which is maximum for any permutation of array.

 

Thus, Option (B) is correct.

 

To gain better understanding about Bubble Sort Algorithm,

Watch this Video Lecture

 

Next Article- Insertion Sort

 

Other Popular Sorting Algorithms-

 

 

Get more notes and other study material of Design and Analysis of Algorithms.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Merge Sort Algorithm | Example | Time Complexity

Merge Sort-

 

  • Merge sort is a famous sorting algorithm.
  • It uses a divide and conquer paradigm for sorting.
  • It divides the problem into sub problems and solves them individually.
  • It then combines the results of sub problems to get the solution of the original problem.

 

How Merge Sort Works?

 

Before learning how merge sort works, let us learn about the merge procedure of merge sort algorithm.

The merge procedure of merge sort algorithm is used to merge two sorted arrays into a third array in sorted order.

 

Consider we want to merge the following two sorted sub arrays into a third array in sorted order-

 

 

The merge procedure of merge sort algorithm is given below-

 

// L : Left Sub Array , R : Right Sub Array , A : Array

merge(L, R, A)
{
    nL = length(L)    // Size of Left Sub Array
    nR = length(R)    // Size of Right Sub Array

    i = j = k = 0

    while(i<nL && j<nR)
    {
      /* When both i and j are valid i.e. when both the sub arrays have elements to insert in A */
      
       if(L[i] <= R[j])
       {
          A[k] = L[i]
          k = k+1
          i = i+1
       }
       else
       {
          A[k] = R[j]
          k = k+1
          j = j+1
       }
    }

    // Adding Remaining elements from left sub array to array A
    while(i<nL)
    {
       A[k] = L[i]
       i = i+1
       k = k+1
    }

    // Adding Remaining elements from right sub array to array A
    while(j<nR)
    {
       A[k] = R[j]
       j = j+1
       k = k+1
    }
}

 

The above merge procedure of merge sort algorithm is explained in the following steps-

 

Step-01:

 

  • Create two variables i and j for left and right sub arrays.
  • Create variable k for sorted output array.

 

 

Step-02:

 

  • We have i = 0, j = 0, k = 0.
  • Since L[0] < R[0], so we perform A[0] = L[0] i.e. we copy the first element from left sub array to our sorted output array.
  • Then, we increment i and k by 1.

 

Then, we have-

 

 

Step-03:

 

  • We have i = 1, j = 0, k = 1.
  • Since L[1] > R[0], so we perform A[1] = R[0] i.e. we copy the first element from right sub array to our sorted output array.
  • Then, we increment j and k by 1.

 

Then, we have-

 

 

Step-04:

 

  • We have i = 1, j = 1, k = 2.
  • Since L[1] > R[1], so we perform A[2] = R[1].
  • Then, we increment j and k by 1.

 

Then, we have-

 

 

Step-05:

 

  • We have i = 1, j = 2, k = 3.
  • Since L[1] < R[2], so we perform A[3] = L[1].
  • Then, we increment i and k by 1.

 

Then, we have-

 

 

Step-06:

 

  • We have i = 2, j = 2, k = 4.
  • Since L[2] > R[2], so we perform A[4] = R[2].
  • Then, we increment j and k by 1.

 

Then, we have-

 

 

Step-07:

 

  • Clearly, all the elements from right sub array have been added to the sorted output array.
  • So, we exit the first while loop with the condition while(i<nL && j<nR) since now j>nR.
  • Then, we add remaining elements from the left sub array to the sorted output array using next while loop.

 

Finally, our sorted output array is-

 

 

Basically,

  • After finishing elements from any of the sub arrays, we can add the remaining elements from the other sub array to our sorted output array as it is.
  • This is because left and right sub arrays are already sorted.

 

Time Complexity

The above mentioned merge procedure takes Θ(n) time.

This is because we are just filling an array of size n from left & right sub arrays by incrementing i and j at most Θ(n) times.

 

Merge Sort Algorithm-

 

Merge Sort Algorithm works in the following steps-

  • It divides the given unsorted array into two halves- left and right sub arrays.
  • The sub arrays are divided recursively.
  • This division continues until the size of each sub array becomes 1.
  • After each sub array contains only a single element, each sub array is sorted trivially.
  • Then, the above discussed merge procedure is called.
  • The merge procedure combines these trivially sorted arrays to produce a final sorted array.

 

The division procedure of merge sort algorithm which uses recursion is given below-

 

// A : Array that needs to be sorted

MergeSort(A)
{
   n = length(A)
   if n<2 return
   mid = n/2
   left = new_array_of_size(mid)       // Creating temporary array for left
   right = new_array_of_size(n-mid)    // and right sub arrays

   for(int i=0 ; i<=mid-1 ; ++i)
   {
      left[i] = A[i]                  // Copying elements from A to left
   }

   for(int i=mid ; i<=n-1 ; ++i)
   {
      right[i-mid] = A[i]             // Copying elements from A to right
   }

   MergeSort(left)                    // Recursively solving for left sub array
   MergeSort(right)                   // Recursively solving for right sub array

   merge(left, right, A)              // Merging two sorted left/right sub array to final array
}

 

Merge Sort Example-

 

Consider the following elements have to be sorted in ascending order-

6, 2, 11, 7, 5, 4

 

The merge sort algorithm works as-

 

 

Time Complexity Analysis-

 

In merge sort, we divide the array into two (nearly) equal halves and solve them recursively using merge sort only.

So, we have-

 

 

Finally, we merge these two sub arrays using merge procedure which takes Θ(n) time as explained above.

 

If T(n) is the time required by merge sort for sorting an array of size n, then the recurrence relation for time complexity of merge sort is-

 

 

On solving this recurrence relation, we get T(n) = Θ(nlogn).

Thus, time complexity of merge sort algorithm is T(n) = Θ(nlogn).

 

Also Read- Master’s Theorem for Solving Recurrence Relations

 

Space Complexity Analysis-

 

  • Merge sort uses additional memory for left and right sub arrays.
  • Hence, total Θ(n) extra memory is needed.

 

Properties-

 

Some of the important properties of merge sort algorithm are-

  • Merge sort uses a divide and conquer paradigm for sorting.
  • Merge sort is a recursive sorting algorithm.
  • Merge sort is a stable sorting algorithm.
  • Merge sort is not an in-place sorting algorithm.
  • The time complexity of merge sort algorithm is Θ(nlogn).
  • The space complexity of merge sort algorithm is Θ(n).

 

NOTE

Merge sort is the best sorting algorithm in terms of time complexity Θ(nlogn)

if we are not concerned with auxiliary space used.

 

PRACTICE PROBLEMS BASED ON MERGE SORT ALGORITHM-

 

Problem-

 

Assume that a merge sort algorithm in the worst case takes 30 seconds for an input of size 64. Which of the following most closely approximates the maximum input size of a problem that can be solved in 6 minutes? (GATE 2015)

  1. 256
  2. 512
  3. 1024
  4. 2048

 

Solution-

 

We know, time complexity of merge sort algorithm is Θ(nlogn).

 

Step-01:

 

It is given that a merge sort algorithm in the worst case takes 30 seconds for an input of size 64.

So, we have-

 

k x nlogn = 30                   (for n = 64)

k x 64 log64 = 30

k x 64 x 6 = 30

From here, k = 5 / 64.

 

Step-02:

 

Let n be the maximum input size of a problem that can be solved in 6 minutes (or 360 seconds).

Then, we have-

 

k x nlogn = 360

(5/64) x nlogn = 360         { Using Result of Step-01 }

nlogn = 72 x 64

nlogn = 4608

On solving this equation, we get n = 512.

 

Thus, correct option is (B).

 

To gain better understanding about Merge Sort Algorithm,

Watch this Video Lecture

 

Next Article- Quick Sort

 

Other Popular Sorting Algorithms-

 

 

Get more notes and other study material of Design and Analysis of Algorithms.

Watch video lectures by visiting our YouTube channel LearnVidFun.

K Maps | karnaugh Maps | Solved Examples

Minimization Of Boolean Expressions-

 

There are following two methods of minimizing or reducing the boolean expressions-

 

 

  1. By using laws of Boolean Algebra
  2. By using Karnaugh Maps also called as K Maps

 

In this article, we will discuss about Karnaugh Maps or K Maps.

 

Karnaugh Map-

 

The Karnaugh Map also called as K Map is a graphical representation

that provides a systematic method for simplifying the boolean expressions.

 

For a boolean expression consisting of n-variables, number of cells required in K Map = 2n cells.

 

Two Variable K Map-

 

  • Two variable K Map is drawn for a boolean expression consisting of two variables.
  • The number of cells present in two variable K Map = 22 = 4 cells.
  • So, for a boolean function consisting of two variables, we draw a 2 x 2 K Map.

 

Two variable K Map may be represented as-

 

 

Here, A and B are the two variables of the given boolean function.

 

Three Variable K Map-

 

  • Three variable K Map is drawn for a boolean expression consisting of three variables.
  • The number of cells present in three variable K Map = 23 = 8 cells.
  • So, for a boolean function consisting of three variables, we draw a 2 x 4 K Map.

 

Three variable K Map may be represented as-

 

 

Here, A, B and C are the three variables of the given boolean function.

 

Four Variable K Map-

 

  • Four variable K Map is drawn for a boolean expression consisting of four variables.
  • The number of cells present in four variable K Map = 24 = 16 cells.
  • So, for a boolean function consisting of four variables, we draw a 4 x 4 K Map.

 

Four variable K Map may be represented as-

 

 

Here, A, B, C and D are the four variables of the given boolean function.

 

Karnaugh Map Simplification Rules-

 

To minimize the given boolean function,

  • We draw a K Map according to the number of variables it contains.
  • We fill the K Map with 0’s and 1’s according to its function.
  • Then, we minimize the function in accordance with the following rules.

 

Rule-01:

 

  • We can either group 0’s with 0’s or 1’s with 1’s but we can not group 0’s and 1’s together.
  • X representing don’t care can be grouped with 0’s as well as 1’s.

 

NOTE

There is no need of separately grouping X’s i.e. they can be ignored if all 0’s and 1’s are already grouped.

 

Rule-02:

 

  • Groups may overlap each other.

 

Rule-03:

 

  • We can only create a group whose number of cells can be represented in the power of 2.
  • In other words, a group can only contain 2n i.e. 1, 2, 4, 8, 16 and so on number of cells.

 

Example-

 

 

Rule-04:

 

  • Groups can be only either horizontal or vertical.
  • We can not create groups of diagonal or any other shape.

 

 

Rule-05:

 

  • Each group should be as large as possible.

 

Example-

 

 

Rule-06:

 

  • Opposite grouping and corner grouping are allowed.
  • The example of opposite grouping is shown illustrated in Rule-05.
  • The example of corner grouping is shown below.

 

Example-

 

 

Rule-07:

 

  • There should be as few groups as possible.

 

PROBLEMS BASED ON KARNAUGH MAP-

 

Problem-01:

 

Minimize the following boolean function-

F(A, B, C, D) = Σm(0, 1, 2, 5, 7, 8, 9, 10, 13, 15)

 

Solution-

 

  • Since the given boolean expression has 4 variables, so we draw a 4 x 4 K Map.
  • We fill the cells of K Map in accordance with the given boolean function.
  • Then, we form the groups in accordance with the above rules.

 

Then, we have-

 

 

Now,

F(A, B, C, D)

= (A’B + AB)(C’D + CD) + (A’B’ + A’B + AB + AB’)C’D + (A’B’ + AB’)(C’D’ + CD’)

= BD + C’D + B’D’

 

Thus, minimized boolean expression is-

F(A, B, C, D) = BD + C’D + B’D’

 

Problem-02:

 

Minimize the following boolean function-

F(A, B, C, D) = Σm(0, 1, 3, 5, 7, 8, 9, 11, 13, 15)

 

Solution-

 

  • Since the given boolean expression has 4 variables, so we draw a 4 x 4 K Map.
  • We fill the cells of K Map in accordance with the given boolean function.
  • Then, we form the groups in accordance with the above rules.

 

Then, we have-

 

 

Now,

F(A, B, C, D)

= (A’B’ + A’B + AB + AB’)(C’D + CD) + (A’B’ + AB’)(C’D’ + C’D)

= D + B’C’

 

Thus, minimized boolean expression is-

F(A, B, C, D) = B’C’ + D

 

Problem-03:

 

Minimize the following boolean function-

F(A, B, C, D) = Σm(1, 3, 4, 6, 8, 9, 11, 13, 15) + Σd(0, 2, 14)

 

Solution-

 

  • Since the given boolean expression has 4 variables, so we draw a 4 x 4 K Map.
  • We fill the cells of K Map in accordance with the given boolean function.
  • Then, we form the groups in accordance with the above rules.

 

Then, we have-

 

 

Now,

F(A, B, C, D)

= (AB + AB’)(C’D + CD) + (A’B’ + AB’)(C’D + CD) + (A’B’ + AB’)(C’D’ + C’D) + (A’B’ + A’B)(C’D’ + CD’)

= AD + B’D + B’C’ + A’D’

 

Thus, minimized boolean expression is-

F(A, B, C, D) = AD + B’D + B’C’ + A’D’

 

Problem-04:

 

Minimize the following boolean function-

F(A, B, C) = Σm(0, 1, 6, 7) + Σd(3, 5)

 

Solution-

 

  • Since the given boolean expression has 3 variables, so we draw a 2 x 4 K Map.
  • We fill the cells of K Map in accordance with the given boolean function.
  • Then, we form the groups in accordance with the above rules.

 

Then, we have-

 

 

Now,

F(A, B, C)

= A'(B’C’ + B’C) + A(BC + BC’)

= A’B’ + AB

 

Thus, minimized boolean expression is-

F(A, B, C) = AB + A’B’

 

NOTE-

 

  • It may be noted that there is no need of considering the quad group.
  • This is because even if we consider that group, we will have to consider the other two duets.
  • So, there is no use of considering that quad group.

 

Problem-05:

 

Minimize the following boolean function-

F(A, B, C) = Σm(1, 2, 5, 7) + Σd(0, 4, 6)

 

Solution-

 

  • Since the given boolean expression has 3 variables, so we draw a 2 x 4 K Map.
  • We fill the cells of K Map in accordance with the given boolean function.
  • Then, we form the groups in accordance with the above rules.

 

Then, we have-

 

 

Now,

F(A, B, C)

= (A + A’)(B’C’ + B’C) + A(B’C’ + B’C + BC + BC’) + (A + A’)(B’C’ + BC’)

= B’ + A + C’

 

Thus, minimized boolean expression is-

F(A, B, C) = A + B’ + C’

 

Problem-06:

 

Minimize the following boolean function-

F(A, B, C) = Σm(0, 1, 6, 7) + Σd(3, 4, 5)

 

Solution-

 

  • Since the given boolean expression has 3 variables, so we draw a 2 x 4 K Map.
  • We fill the cells of K Map in accordance with the given boolean function.
  • Then, we form the groups in accordance with the above rules.

 

Then, we have-

 

 

Now,

F(A, B, C)

= (A + A’)(B’C’ + B’C) + A(B’C’ + B’C + BC + BC’)

= B’ + A

 

Thus, minimized boolean expression is-

F(A, B, C) = A + B’

 

Problem-07:

 

Minimize the following boolean function-

F(A, B, C, D) = Σm(0, 2, 8, 10, 14) + Σd(5, 15)

 

Solution-

 

  • Since the given boolean expression has 4 variables, so we draw a 4 x 4 K Map.
  • We fill the cells of K Map in accordance with the given boolean function.
  • Then, we form the groups in accordance with the above rules.

 

Then, we have-

 

 

Now,

F(A, B, C, D)

= (AB + AB’)CD’ + (A’B’ + AB’)(C’D’ + CD’)

= ACD’ + B’D’

 

Thus, minimized boolean expression is-

F(A, B, C, D) = ACD’ + B’D’

 

Problem-08:

 

Minimize the following boolean function-

F(A, B, C, D) = Σm(3, 4, 5, 7, 9, 13, 14, 15)

 

Solution-

 

  • Since the given boolean expression has 4 variables, so we draw a 4 x 4 K Map.
  • We fill the cells of K Map in accordance with the given boolean function.
  • Then, we form the groups in accordance with the above rules.

 

Then, we have-

 

 

Now,

F(A, B, C, D)

= A’B(C’D’ + C’D) + (A’B’ + A’B)(CD) + (AB + AB’)(C’D) + AB(CD + CD’)

= A’BC’ + A’CD + AC’D + ABC

 

Thus, minimized boolean expression is-

F(A, B, C, D) = A’BC’ + A’CD + AC’D + ABC

 

It is important to note that we are not considering the quad group because we have to consider the duets anyhow.

 

Problem-09:

 

Consider the following boolean function-

F(W, X, Y, Z) = Σm(1, 3, 4, 6, 9, 11, 12, 14)

 

This function is independent ________ number of variables. Fill in the blank.

 

Solution-

 

  • Since the given boolean expression has 4 variables, so we draw a 4 x 4 K Map.
  • We fill the cells of K Map in accordance with the given boolean function.
  • Then, we form the groups in accordance with the above rules.

 

Then, we have-

 

 

Now,

F(W, X, Y, Z)

= (W’X + WX)(Y’Z’ + YZ’) + (W’X’ + WX’)(Y’Z + YZ)

= XZ’ + X’Z

= X ⊕ Z

 

Thus, minimized boolean expression is-

F(W, X, Y, Z) = X ⊕ Z

 

Clearly, the given boolean function depends on only two variables X and Z.

Hence, it is independent of other two variables W and Y.

 

Next Article- Neutral Functions

 

Get more notes and other study material of Digital Design.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Candidate Key | Finding Candidate Keys | Examples

Keys in DBMS-

 

Before you go through this article, make sure that you have gone through the previous article on Keys in DBMS.

 

We have discussed-

  • A key is a set of attributes that can identify each tuple uniquely in the given relation.
  • There are various types of keys in DBMS-

 

 

In this article, we will discuss how to find candidate keys of a given relation.

 

Candidate Key-

 

A candidate key may be defined as-

 

A set of minimal attribute(s) that can identify each tuple uniquely in the given relation is called as a candidate key.

OR

A minimal super key is called as a candidate key.

 

For any given relation,

  • It is possible to have multiple candidate keys.
  • There exists no general formula to find the total number of candidate keys of a given relation.

 

Example-

 

Consider the following Student schema-

Student ( roll , name , sex , age , address , class , section )

 

Given below are the examples of candidate keys-

  • ( class , section , roll )
  • ( name , address )

 

These are candidate keys because each set consists of minimal attributes required to identify each student uniquely in the Student table.

 

Finding Candidate Keys-

 

We can determine the candidate keys of a given relation using the following steps-

 

Step-01:

 

  • Determine all essential attributes of the given relation.
  • Essential attributes are those attributes which are not present on RHS of any functional dependency.
  • Essential attributes are always a part of every candidate key.
  • This is because they can not be determined by other attributes.

 

Example

 

Let R(A, B, C, D, E, F) be a relation scheme with the following functional dependencies-

A → B

C → D

D → E

 

Here, the attributes which are not present on RHS of any functional dependency are A, C and F.

So, essential attributes are- A, C and F.

 

Step-02:

 

  • The remaining attributes of the relation are non-essential attributes.
  • This is because they can be determined by using essential attributes.

 

Now, following two cases are possible-

 

Case-01:

 

If all essential attributes together can determine all remaining non-essential attributes, then-

  • The combination of essential attributes is the candidate key.
  • It is the only possible candidate key.

 

Case-02:

 

If all essential attributes together can not determine all remaining non-essential attributes, then-

  • The set of essential attributes and some non-essential attributes will be the candidate key(s).
  • In this case, multiple candidate keys are possible.
  • To find the candidate keys, we check different combinations of essential and non-essential attributes.

 

We will further understand how to find candidate keys with the help of following problems.

The following practice problems are based on Case-01.

 

PRACTICE PROBLEMS BASED ON FINDING CANDIDATE KEYS-

 

Problem-01:

 

Let R = (A, B, C, D, E, F) be a relation scheme with the following dependencies-

C → F

E → A

EC → D

A → B

Which of the following is a key for R?

  1. CD
  2. EC
  3. AE
  4. AC

 

Also, determine the total number of candidate keys and super keys.

 

Solution-

 

We will find candidate keys of the given relation in the following steps-

 

Step-01:

 

  • Determine all essential attributes of the given relation.
  • Essential attributes of the relation are- C and E.
  • So, attributes C and E will definitely be a part of every candidate key.

 

Step-02:

 

Now,

  • We will check if the essential attributes together can determine all remaining non-essential attributes.
  • To check, we find the closure of CE.

 

So, we have-

{ CE }+

= { C , E }

= { C , E , F }                       ( Using C → F )

= { A , C , E , F }                  ( Using E → A )

= { A , C , D , E , F }            ( Using EC → D )

= { A , B , C , D , E , F }       ( Using A → B )

 

We conclude that CE can determine all the attributes of the given relation.

So, CE is the only possible candidate key of the relation.

 

Thus, Option (B) is correct.

 

Total Number of Candidate Keys-

 

Only one candidate key CE is possible.

 

Total Number of Super Keys-

 

There are total 6 attributes in the given relation of which-

  • There are 2 essential attributes- C and E.
  • Remaining 4 attributes are non-essential attributes.
  • Essential attributes will be definitely present in every key.
  • Non-essential attributes may or may not be taken in every super key.

 

 

So, number of super keys possible = 2 x 2 x 2 x 2 = 16.

Thus, total number of super keys possible = 16.

 

Problem-02:

 

Let R = (A, B, C, D, E) be a relation scheme with the following dependencies-

AB → C

C → D

B → E

Determine the total number of candidate keys and super keys.

 

Solution-

 

We will find candidate keys of the given relation in the following steps-

 

Step-01:

 

  • Determine all essential attributes of the given relation.
  • Essential attributes of the relation are- A and B.
  • So, attributes A and B will definitely be a part of every candidate key.

 

Step-02:

 

Now,

  • We will check if the essential attributes together can determine all remaining non-essential attributes.
  • To check, we find the closure of AB.

 

So, we have-

{ AB }+

= { A , B }

= { A , B , C }                     ( Using AB → C )

= { A , B , C , D }               ( Using C → D )

= { A , B , C , D , E }          ( Using B → E )

 

We conclude that AB can determine all the attributes of the given relation.

Thus, AB is the only possible candidate key of the relation.

 

Total Number of Candidate Keys-

 

Only one candidate key AB is possible.

 

Total Number of Super Keys-

 

There are total 5 attributes in the given relation of which-

  • There are 2 essential attributes- A and B.
  • Remaining 3 attributes are non-essential attributes.
  • Essential attributes will be definitely present in every key.
  • Non-essential attributes may or may not be taken in every super key.

 

 

So, number of super keys possible = 2 x 2 x 2 = 8.

Thus, total number of super keys possible = 8.

 

Problem-03:

 

Consider the relation scheme R(E, F, G, H, I, J, K, L, M, N) and the set of functional dependencies-

{ E, F } → { G }

{ F } → { I , J }

{ E, H } → { K, L }

{ K } → { M }

{ L } → { N }

 

What is the key for R?

  1. { E, F }
  2. { E, F, H }
  3. { E, F, H, K, L }
  4. { E }

 

Also, determine the total number of candidate keys and super keys.

 

Solution-

 

We will find candidate keys of the given relation in the following steps-

 

Step-01:

 

  • Determine all essential attributes of the given relation.
  • Essential attributes of the relation are- E, F and H.
  • So, attributes E, F and H will definitely be a part of every candidate key.

 

Step-02:

 

Now,

  • We will check if the essential attributes together can determine all remaining non-essential attributes.
  • To check, we find the closure of EFH.

 

So, we have-

{ EFH }+

= { E , F , H }

= { E , F , G , H }                                ( Using EF → G )

= { E , F , G , H , I , J }                       ( Using F → IJ )

= { E , F , G , H , I , J , K , L }             ( Using EH → KL )

= { E , F , G , H , I , J , K , L , M }       ( Using K → M )

= { E , F , G , H , I , J , K , L , M , N } ( Using L → N )

 

We conclude that EFH can determine all the attributes of the given relation.

So, EFH is the only possible candidate key of the relation.

 

Thus, Option (B) is correct.

 

Total Number of Candidate Keys-

 

Only one candidate key EFH is possible.

 

Total Number of Super Keys-

 

There are total 10 attributes in the given relation of which-

  • There are 3 essential attributes- E, F and H.
  • Remaining 7 attributes are non-essential attributes.
  • Essential attributes will be definitely present in every key.
  • Non-essential attributes may or may not be taken in every super key.

 

 

So, number of super keys possible = 2 x 2 x 2 x 2 x 2 x 2 x 2 = 128.

Thus, total number of super keys possible = 128.

 

Problem-04:

 

Consider the relation scheme R(A, B, C, D, E, H) and the set of functional dependencies-

A → B

BC → D

E → C

D → A

 

What are the candidate keys of R?

  1. AE, BE
  2. AE, BE, DE
  3. AEH, BEH, BCH
  4. AEH, BEH, DEH

 

Solution-

 

We will find candidate keys of the given relation in the following steps-

 

Step-01:

 

  • Determine all essential attributes of the given relation.
  • Essential attributes of the relation are- E and H.
  • So, attributes E and H will definitely be a part of every candidate key.

 

The only possible option is (D).

Thus, Option (D) is correct.

 

Next Article- Functional Dependency in DBMS

 

Get more notes and other study material of Database Management System (DBMS).

Watch video lectures by visiting our YouTube channel LearnVidFun.

Cause Effect Graph Technique | Examples

Cause Effect Graph-

 

  • Cause Effect Graph is a popular black box testing technique.
  • It illustrates the relationship between a given outcome and all the factors that influence the outcome graphically.

 

 

Here,

  • A “Cause” stands for a distinct input condition that fetches about an internal change in the system.
  • An “Effect” represents an output condition, a system state that results from a combination of causes.

 

Applications-

 

  • For analyzing the existing problem so that corrective actions can be taken at the earliest.
  • For relating the interactions of the system with the factors affecting a particular process.
  • For identifying the possible root causes, reasons for a particular effect, problem or outcome.

 

Advantages-

 

  • It helps to determine the root causes of a problem or quality.
  • It indicates possible causes of variation in a process.
  • It identifies those areas where data should be collected for further study.
  • It utilizes the team knowledge of the process by encouraging team participation.

 

Steps For Drawing Cause Effect Diagram-

 

The following steps are followed-

  • Identify and describe the input conditions (causes) and actions (effect).
  • Build up a cause-effect graph.
  • Convert cause-effect graph into a decision table.
  • Convert decision table rules to test cases where each column of the decision table represents a test case.

 

PRACTICE PROBLEMS BASED ON CAUSE-EFFECT GRAPH TECHNIQUE-

 

Problem-01:

 

Design test cases for the following problem-

If the character of the first column is ‘A’ or ‘B’ and the second column is a number, then the file is considered updated. If the first character is erroneous, then message x should be printed. If the second column is not a number, then message y should be printed.

 

Solution-

 

Step-01:

 

Identify and describe the input conditions (causes) and actions (effect).

 

The causes represented by letter “C” are as follows-

  • C1 : The character in column 1 is ‘A’
  • C2 : The character in column 1 is ‘B’
  • C3 : The character in column 2 is a number

 

The effects represented by letter “e” are as follows-

  • e1 : File update is made
  • e2 : Message x is printed
  • e3 : Message y is printed

 

Step-02:

 

Build up a cause-effect graph-

 

 

Step-03:

 

Convert cause-effect graph into a decision table-

 

Test dataCausesEffect
A1A2A3M1M2M3
1000011
2001010
3010001
4011100
5100001
6101100

 

Problem-02:

 

Why Cause Effect Graphing Technique is Better Than Any Other Black Box Testing Technique?

 

Solution-

 

  • Boundary value analysis and equivalence partitioning do not explore combinations of input circumstances.
  • These only consider the single input conditions.
  • However, combinations of inputs may result in interesting situations.
  • These situations should be tested.
  • By considering all the valid combinations of equivalence classes, there will be large number of test cases.
  • Many of these test cases will not be useful for revealing any new errors.

 

On the other hand,

  • Cause Effect Graph is a technique that helps in selecting a high-yield set of test cases in a systematic way.
  • It has a beneficial effect in pointing out incompleteness and ambiguities in the specifications.

 

To gain better understanding about Cause Effect Graph Technique,

Watch this Video Lecture

 

Get more notes and other study material of Software Engineering.

Watch video lectures by visiting our YouTube channel LearnVidFun.