Madhav Institute of Technology and science

Gwalior,MP
Department of IT

Proficiency presentation:
design and analysis of
algorithms

SUBMITTED TO: from

Prof. Bulbul agarwal Aayushman Agarwal
0901IT211001
 UNIT 1 :Introduction to Computational Model
1. Recurrence and Asymptotic Notations,
Resources for an algorithm are usually expressed as a function regarding input. Often
this function is messy and complicated to work. To study Function growth efficiently, we
reduce the function down to the important part.
1. They give simple characteristics of an algorithm's efficiency.
2. They allow the comparisons of the performances of various algorithms.
A recurrence is an equation or inequality that describes a function in terms of its values
on smaller inputs. To solve a Recurrence Relation means to obtain a function defined on
the natural numbers that satisfy the recurrence.There are four methods for solving
Recurrence: Substitution Method , Iteration Method , Recursion Tree Method , Master
Method.
2. Sorting & Searching Algorithms: Bubble Sort ,Selection Sort ,Insertion Sort and many
more sorting as well as binary and linear search were aanalysed on basis of worst case
asymptotic notation and recurerence
3. Basic Tree and Graph Concepts : B-Trees and Traversal Techniques (BFS and DFS)
 UNIT 2 :Divide and Conquer Method
Divide and Conquer is an algorithmic pattern. In algorithmic methods, the design is to take a dispute on a huge input,
break the input into minor pieces, decide the problem on each of the small pieces, and then merge the piecewise
solutions into a global solution. This mechanism of solving the problem is called the Divide & Conquer Strategy.
1. Finding the Maximum and Minimum : we will divide the problem into sub-problems
and find the max and min of each group, now max. Of each group will compare with
the only max of another group and min with min.
2.Binary Search, Merge Sort, Quick Sorts : In Binary Search technique, we search an
element in a sorted array by recursively dividing the interval in half.
Merge sort is yet another sorting algorithm that falls under the category of Divide and
Conquer technique. It is one of the best sorting techniques that successfully build a
recursive algorithm.
in quick sort Rearrange the elements and split arrays into two sub-arrays and an element
in between search that each element in left sub array is less than or equal to the average
element and each element in the right sub- array is larger than the middle element.
3. Strassen’s Matrix : : Strassen's matrix multiplication algorithm follows divide and
conquer technique. In this algorithm the input matrices are divided into n/2 x n/2 sub
matrices and then the recurrence relation is applied.
 UNIT 3 :Greedy Method
1. Characteristics: The greedy method is one of the strategies like Divide and conquer
used to solve the problems. This method is used for solving optimization problems. An
optimization problem is a problem that demands either maximum or minimum results.
To construct the solution in an optimal way, this algorithm creates two sets where
one set contains all the chosen items, and another set contains the rejected items.
A Greedy algorithm makes good local choices in the hope that the solution should be
either feasible or optimal.
components that can be used in the greedy algorithm are: Candidate set,Selection
function,Feasibility function,Objective function,Solution function.
2. Examples of Greedy Methods :
It is used in finding the shortest path(Dijkstra’s single source shortest path algorithm).
It is used to find the minimum spanning tree using the prim's algorithm or the
Kruskal's algorithm.
It is used in a job sequencing with a deadline.
This algorithm is also used to solve the fractional knapsack problem.
 UNIT 4:Dynamic Programming
1. Principle of Optimality : We divide a problem into smaller nested subproblems, and
then combine the solutions to reach an overall solution. This concept is known as the
principle of optimality
Optimality criteria are the conditions a function must satisfy at its minimum point.
2. Examples of Dynamic Programming Methods : 0/1 Knapsack, Traveling salesman
problem,Floyd’s All Pairs Shortest Path
3. Matrix chain multiplication : Matrix chain multiplication (or the matrix chain ordering
problem) is an optimization problem concerning the most efficient way to multiply a
given sequence of matrices. The problem is not actually to perform the multiplications,
but merely to decide the sequence of the matrix multiplications involved.
 UNIT 5 :Backtracking,Branch & Bound AND NP-Completeness
1. Backtracking : In backtracking, the state space tree is searched until the solution is
obtained. Backtracking is more efficient.
2. Branch & Bound: In Branch-and-Bound as the optimum solution may be present any
where in the state space tree, so the tree need to be searched completely.
3. NP-Completeness : NP is a set of decision problems that can be solved by a Non-
deterministic Turing Machine in Polynomial-time. P is a subset of NP (any problem that
can be solved by a deterministic machine in polynomial time can also be solved by a non-
deterministic machine in polynomial time).
NP-complete problems are the upgraded harder NP set. A decision problem L is NP-
complete if:
1) L is in NP (Any given solution for NP-complete problems can be verified quickly, but
there is no efficient known solution).
2) Every problem in NP is reducible to L in polynomial time (Reduction is defined below).
THANKYOU