lOMoARcPSD|43337963
2 Marks Answers - Algorithms
Algorithm for CSE II YR and IV Sem (Anna University)
Scan to open on Studocu
Studocu is not sponsored or endorsed by any college or university
Downloaded by Omprakash D (itmeom@gmail.com)
lOMoARcPSD|43337963
1. What do you mean by algorithm? Give the diagram representation of notion of algorithm.
2. List the types of asymptotic notations in analysing complexity of algorithms.
Big Oh-upper bound of algorithm’s running time
Big Omega- lower bound of algorithm’s running time
Big Theta- upper and the lower bound of the running time of an algorithm.
Downloaded by Omprakash D (itmeom@gmail.com)
lOMoARcPSD|43337963
3. Outline divide and conquer algorithm design paradigm.
4. State the principle of optimality.
In an optimal sequence of decisions or choices, each subsequence must also be optimal. To use
dynamic programming the problem must observe the principle of optimality that whatever the initial state
is, remaining decisions must be optimal regard the state following from the first decision.
5. Define multistage graph.
A directed graph 'G' whose vertices V are partitioned into k stages, where k ≥ 2,
where one of the vertex is called source and the other is called sink such type of
graph is known as a multistage graph. Every edge has weight assigned to it. Let the
cost of the edge (i, j) be denoted by COST (i, j). The cost of the path from source to sink
is the total of the weights of all the edges lying on that path. The problem is to find the
shortest path from source to sink.
Downloaded by Omprakash D (itmeom@gmail.com)
lOMoARcPSD|43337963
6. State the general principle of Greedy algorithm.
In greedy technique, the solution is constructed through a sequence of steps, each
expanding partially constructed solution obtained so far, until a complete solution to a
problem is reduced. At each step the choice of feasible solutions is made. From the set of
feasible solutions the optimal solution is selected as the solution to the problem.
7. State Hamiltonian circuit problem.
8. State 15 puzzle problem.
Downloaded by Omprakash D (itmeom@gmail.com)
lOMoARcPSD|43337963
The 15 puzzle problem consist of 15 numbered (0-15) tiles on a square box with
16 tiles(one tile is blank or empty). The objective of this problem is to change the
arrangement of initial node to goal node by using series of legal moves.
9. Differentiate tractable and intractable problems
Tractable problem Intractable problem
1.A problem that is solvable by a polynomial- 1.A problem that cannot be solved by a
time algorithm. The upper bound is polynomial. polynomial-time algorithm. The lower bound
is exponential.
2.Example: Example:
Sorting a list Tower of Hanoi
Multiplication of integers Traveling salesman problem (TSP):
10. Write an algorithm to find the kth smallest number.
Choose a Pivot: Select a pivot element from the array.
Partition the Array: Rearrange the elements in the array so that elements less
than the pivot are on the left, elements greater than the pivot are on the right.
Recursively Apply: Depending on the position of the pivot, either recursively
apply the algorithm to the left or right partition, or return the pivot if it is in the
correct position.
C implementation:
int partition(int a[], int low, int high) {
int pivot = a[low];
int i = low + 1;
int j= high;
while (i<= j) {
while (i<= j && a[i] <= pivot) {
i++;
}
while (i <= j && a[j] > pivot) {
j--;
}
Downloaded by Omprakash D (itmeom@gmail.com)
lOMoARcPSD|43337963
if (i <j) {
swap(&a [i], &arr[j]);
}
}
swap(&a [i], &a[j]);
return j;
}
// Quickselect function to find the k-th smallest element
int quickselect(int a [], int low, int high, int k) {
if (low == high) {
return a[low];
}
int pivotIndex = partition(a, low, high);
if (k == pivotIndex) {
return a[k];
}
else if (k < pivotIndex) {
return quickselect(a, low, pivotIndex - 1, k);
}
else {
return quickselect(a, pivotIndex + 1, high, k);
}
}
Downloaded by Omprakash D (itmeom@gmail.com)
