1.What is an Algorithm?
An Algorithm is a set of well-defined instructions designed to perform a specific
set of tasks. Algorithms are used in Computer science to perform calculations,
automatic reasoning, data processing, computations, and problem-solving.
Designing an algorithm is important before writing the program code as the
algorithm explains the logic even before the code is developed.
Why Study Design and Analysis of Algorithm?
Design and Analysis of Algorithm help to design the algorithms for solving
different types of problems in Computer Science. It also helps to design and
analyze the logic on how the program will work before developing the actual
code for a program.
I. To understand the basic idea of the problem.
II. To find an approach to solve the problem.
III. To improve the efficiency of existing techniques.
IV. To understand the basic principles of designing the algorithms.
V. To compare the performance of the algorithm with respect to other
techniques.
VI. It is the best method of description without describing the
implementation detail.
VII. The Algorithm gives a clear description of requirements and goal of
the problem to the designer.
VIII. A good design can produce a good solution.
IX. To understand the flow of the problem.
2.Define asymptotic notation
Asymptotic notations are the mathematical notations used to describe the
running time of an algorithm when the input tends towards a particular
value or a limiting value.
For example: In bubble sort, when the input array is already sorted, the
time taken by the algorithm is linear i.e. the best case.
There are mainly three asymptotic notations:
o Big-O notation
o Omega notation
o Theta notation
Big-O Notation (O-notation)
Big-O notation represents the upper bound of the running time of an
algorithm. Thus, it gives the worst-case complexity of an algorithm.
o
Omega Notation (Ω-notation)
Omega notation represents the lower bound of the running time of an
algorithm. Thus, it provides the best case complexity of an algorithm.
Theta Notation (Θ-notation)
Theta notation encloses the function from above and below. Since it
represents the upper and the lower bound of the running time of an
algorithm, it is used for analyzing the average-case complexity of an
algorithm.
3. Explain the algorithm design and analysis process with neat
diagram
Design and Analysis of Algorithm help to design the algorithms for solving
different types of problems in Computer Science. It also helps to design and
analyze the logic on how the program will work before developing the actual
code for a program.
4. Explain strassen’s matrix multiplication
the divide-and-conquer approach can reduce the number of one-digit
multiplications in multiplying two integers, we should not be surprised
that a similar feat can be accomplished for multiplying matrices. Such an
algorithm was published by V. Strassen in 1969 [Str69]. The principal
insight of the algorithm lies in the discovery that we can find the
product C of two 2 × 2 matrices A and B with just seven multiplications
as opposed to the eight required by the brute-force algorithm
This is accomplished by using the following formulas
This is accomplished by using the following formulas:
Thus, to multiply two 2 × 2 matrices, Strassen’s algorithm makes seven
multipli-cations and 18 additions/subtractions, whereas the brute-force
algorithm requires eight multiplications and four additions. These numbers
should not lead us to multiplying 2 × 2 matrices by Strassen’s algorithm. Its
importance stems from its asymptotic superiority as matrix order n goes to
infinity.
Let A and B be two n × n matrices where n is a power of 2. (If n is not a power
of 2, matrices can be padded with rows and columns of zeros.) We can
divide A, B, and their product C into four n/2 × n/2 submatrices each as
follows:
the correct product. For example, C00 can be computed either as A00 ∗ B00 +
It is not difficult to verify that one can treat these submatrices as numbers to get
A01 ∗ B10 or as M1 + M4 − M5 + M7 where M1, M4, M5, and M7 are found
by Strassen’s formulas, with the numbers replaced by the corresponding
submatrices. If the seven products of n/2 × n/2 matrices are computed
recursively by the same method, we have Strassen’s algorithm for matrix
multiplication.
5. Define Time And Space complixity
Time complixity :- Time complexity is defined in terms of how many times it
takes to run a given algorithm, based on the length of the input. Time
complexity is not a measurement of how much time it takes to execute a
particular algorithm because such factors as programming language,
operating system, and processing power are also considered.
Space complixity :- When an algorithm is run on a computer, it necessitates a
certain amount of memory space. The amount of memory used by a program
to execute it is represented by its space complexity. Because a program
requires memory to store input data and temporal values while running, the
space complexity is auxiliary and input space.
Significant in Terms of Time Complexity
The input size has a strong relationship with time complexity. As the size
of the input increases, so does the runtime, or the amount of time it takes
the algorithm to run.
Here is an example.
Assume you have a set of numbers S= (10, 50, 20, 15, 30)
There are numerous algorithms for sorting the given numbers. However,
not all of them are effective. To determine which is the most effective, you
must perform computational analysis on each algorithm.
