(i) A Palindrome is a string that reads the same forward and backward. Write an algorithm for determining whether a string of n characters is palindrome.
Solution:-
C program to check whether it is a palindrome and also find the length of string
1. #include <stdio.h>
2. #include <string.h>
3.
4. void main()
5. {
6. char string[25], reverse_string[25] = {'\0'};
7. int i, length = 0, flag = 0;
8.
9. printf("Enter a string \n");
gets(string);
/* keep going through each character of the string till its end */
for (i = 0; string[i] != '\0'; i++)
{
length++;
}
printf("The length of the string '%s' = %d\n", string, length);
for (i = length - 1; i >= 0 ; i--)
{
reverse_string[length - i - 1] = string[i];
}
/* Check if the string is a Palindrome */
for (flag = 1, i = 0; i < length ; i++)
{
if (reverse_string[i] != string[i])
flag = 0;
}
if (flag == 1)
printf ("%s is a palindrome \n", string);
else
printf("%s is not a palindrome \n", string);
}
Output:-
Enter a string how are you The length of the string 'how are you' = 12 how are you is not a palindrome ------------------------------------------------------------------- Enter a string madam The length of the string 'madam' = 5 madam is a palindrome
Algorithm:-
step 1 : start
step 2 : Declare variables char_string[25], reverse_string[25]
int i, length = 0, flag = 0;
step 3 : read value string.
step 4 : for (i = 0; string[i] != '\0'; i++)
length++
step 5 : display 'the length of string =', string, length
step 6 : for (i = length - 1; i >= 0 ; i--)
do reverse_string[length - i - 1] = string[i]
/* Check if the string is a Palindrome */
step 7 : for (flag = 1, i = 0; i < length ; i++)
if revers_string[i] ! = string[i]
do flag = 0
if flag == 1
display string is palindrome.
else
display string is not palindrome.
step 8 : stop.
(ii) Find the largest number in an array and count a number of comparison operations as well as running time complexity of each statement and total complexity of the problem.
Solution:-
#include <stdio.h>int main() {int i,n, count = 0;float arr[100];printf("Enter total number of elements(1 to 100): ");scanf("%d",&n);printf("\n");for(i=0;i<n;++i) /* Stores number entered by user. */{printf("Enter Number %d: ",i+1);scanf("%f",&arr[i]);}for(i=1;i<n;++i) /* Loop to store largest number to arr[0] */{if(arr[0]<arr[i]) /* Change < to > if you want to find smallest element*/{count++;}arr[0]=arr[i];}printf("Largest element = %.2f \n",arr[0]);printf(“the number of comparison %d”, count);return 0;getch();}
Output:-
Time Complexity of AlgorithmsTime complexity of an algorithm signifies the total time required by the program to run to completion. The time complexity of algorithms is most commonly expressed using the big O NotationTime Complexity is most commonly estimated by counting the number of elementary functions performed by the algorithm.
Calculating the Complexity
Now lets tap onto the next big topic related to Time complexity, which is How to Calculate Time Complexity. It becomes very confusing some times, but we will try to explain it in the simplest way.
Now lets tap onto the next big topic related to Time complexity, which is How to Calculate Time Complexity. It becomes very confusing some times, but we will try to explain it in the simplest way.
Now the most common metric for calculating time complexity is Big O notation. This removes all constant factors so that the running time can be estimated in relation to N, as N approaches infinity. In general you can think of it like this:
statement;
Above we have a single statement. Its Time Complexity will be Constant. The running time of the statement will not change in relation to N
for(i=0; i < N; i++)
{
statement;
}
The time complexity for the above algorithm will be Linear. The running time of the loop is directly proportional to N. When N doubles, so does the running time.
for(i=0; i < N; i++)
{
for(j=0; j < N;j++)
{
statement;
}
}
This time, the time complexity for the above code will be Quadratic. The running time of the two loops is proportional to the square of N. When N doubles, the running time increases by N * N.
(iii) Write a programme which interchanges the values the variable using only assignment operations. What is the minimum number of assignments operations required?
Solution:-
#include <stdio.h> #include <string.h> /* Function Prototype */ void swap(int*, int *); void main() { int num1, num2; printf("\nEnter two numbers:"); scanf("%d %d", &num1, &num2); printf("\nThe numbers before swapping are Number1= %d Number2 = %d", num1, num2); swap(&num1, &num2); /* Call by Reference to function swap */ printf("\nThe numbers after swapping are Number1= %d Number2 = %d", num1, num2); } /* Code to swap two numbers using Assignment operator */ void swap(int *x, int *y) { *x = *x ^= *y; *y = *y ^= *y; *x = *x ^= *y; }
Output:-
The minimum number of operator assigned is six because as we can see in the void swap function in that we used assignment operator six time to swap the value of num1 and num2.
(iv) Write a programme to do bubblesort to sort an array X={10,5,7,8,3,6,4,14} showing the
list obtained at each step. Also count no. of comparison operations in the programme
Solution:
#include <stdio.h>
int printAarray(int arr[]){
printf("\n Array at this stage = ");
for(int i=0; i<8; i++){
if(i==7){
printf("%d", arr[i]);
}else{
printf("%d, ", arr[i]);
}
}
printf("\n");
}
int main()
{
int X[]={10,5,7,8,3,6,4,14};
int n=8, c, d, swap, comp=0;
for (c = 0 ; c < ( n - 1 ); c++)
{
for (d = 0 ; d < n - c - 1; d++)
{
if (X[d] > X[d+1]) /* For decreasing order use < */
{
comp++;
swap = X[d];
X[d] = X[d+1];
X[d+1] = swap;
printAarray(X);
}
printAarray(X);
}
printAarray(X);
}
printf(" \n\n Sorted list in ascending
order:\n===================================\n");
for ( c = 0 ; c < n ; c++ ){
printf(" %d\n", X[c]);
}
printf("===================================\n Total Comparisons =
%d\n", comp);
return 0;
}
(v) Write a programme to find multiplication of matrices of order 4*4 and find the total
number of comparison, total no. of assignments, total number of multiplications and total
number of addition operations required in the programme.
Solution:
#include <stdio.h>
int main()
{
int a[4][4]={
{1,2,3,4},
{5,6,7,8},
{9,1,2,3},
{3,4,5,6}
} ;
int b[4][4]={
{1,2,3,4},
{5,6,7,8},
{9,1,2,3},
{3,4,5,6}
} ;
int c[4][4];
int sum, total_comparisons=0, total_assignments=0,
total_multiplications=0, total_additions=0;
//Multiplication Logic
for (int i = 0; i <= 3; i++) {
total_comparisons++;
for (int j = 0; j <= 3; j++) {
total_comparisons++;
sum = 0;
total_assignments++;
for (int k = 0; k <= 3; k++) {
sum = sum + a[i][k] * b[k][j];
total_comparisons++;
total_multiplications++;
total_additions++;
total_assignments++;
}
c[i][j] = sum;
total_assignments++;
}
}
printf("\nMultiplication Of Two Matrices :
\n================================\n");
for (i = 0; i <= 3; i++) {
for (int j = 0; j <= 3; j++) {
printf(" %d ", c[i][j]);
}
printf("\n");
}
printf("\nTotal Numbers (for logic only not for printing):
\n===============================================\n");
printf("\nTotal comparison \t:\t %d\n", total_comparisons);
printf("\nTotal assignments \t:\t %d\n",
total_assignments);
printf("\nTotal multiplications \t:\t %d\n",
total_multiplications);
printf("\nTotal addition \t\t:\t %d\n", total_additions);
return 0;
}
