Write a short note on Asymptotic Notations.

Asymptotic Notations are languages that allow us to analyze an algorithm's running time by identifying its behavior as the input size for the algorithm increases. It is used to describe the asymptotic behaviour of complexities of algorithms.

Demo Teacher

added 2 years ago

Given weight vector {15,25,35,45,55} and the profit vector {10,20,30,40,50} and a knapsack of capacity 100, find atleast three feasible solutions including optimal one for the knapsack problem of 5 items.

Demo Teacher

added 2 years ago

Why Recursion tree method is best than the Substitution method for solving a recurrence relation?  Find the asymptotic upper bound of the following recurrence relation with the help of recursion tree method.

T(n)=T(n/4)+T(n/2)+Θ(n²)

Recursion tree method is best than the Substitution method for solving a recurrence relation because in recursion tree method, we draw a recurrence tree and calculate the time taken by every level of tree.

Demo Teacher

added 2 years ago

What do you mean by dynamic programming? Write the algorithm of chain matrix multiplication. 

It is a problem solving technique like divide and conquer where problems are divided into subproblems. Dynamic programming is used when the subproblems are not independent.

Demo Teacher

added 2 years ago

Write quick sort algorithm. Analyze the best case and worst case time complexities of your algorithm. Perform the PARTITION operation once(one time) on the following array as per the requirement of the quicksort algorithm, assuming the last element of the array to be the pivot element. Clearly mention the steps. Arr=[2,8,7,1,3,5,6,4].

The array A[p….r] is divided into two subarrays A[p…….(q-1)] and A[(q+1)…….r] where q is the partitioning element.

Demo Teacher

added 2 years ago

Find the recurrence relation of binary search and derive the time complexity of binary search.

Binary search is a technique to find a particular element in a sorted list of elements. Suppose L is the sorted list and d is the element to be searched, lb is the lower bound of the list and ub is the upper bound of the list.

Demo Teacher

added 2 years ago

Write a C program to multiplication of two matrix.

#include<stdio.h> #include<conio.h> main() { int a[10][10],b[10][10],c[10][10],m,n,p,q,i,j,k;

Demo Teacher

added 2 years ago

Write a C program to find factorial(using recursion) of any no.

#include<stdio.h> #include<conio.h> int fact(int); main() { int n,result;

Demo Teacher

added 2 years ago

Write a C program to print pattern below:

*

* *

* * *

* * * *

#include<stdio.h> #include<conio.h> main() { int n,i,j;

Demo Teacher

added 2 years ago

Write a C program to convert decimal no. to binary.

#include<stdio.h> #include<conio.h> main() { int bin[50],i=0,n,j;

Demo Teacher

added 2 years ago