AALIM MUHAMMED SALEGH COLLEGE OF ENGI

Reg. No:
NEERING
INTERNAL ASSESSMENT I, 2023-2024
Subject Code : AD3351
Subject Title : DESIGN AND ANALYSIS OF ALGORITHM
Year /Sem: II/III
(Regulations R- 2021)

Answer ALL Questions Date: 26.09.2024

CO1 Analyze the efficiency of recursive and non-recursive algorithms mathematically

Analyze the efficiency of brute force, divide and conquer, decrease and conquer, Transform and conquer
CO2
algorithmic techniques
BL – Bloom’s Taxonomy Levels.
(L1-Remembering, L2-Understanding, L3- Applying, L4-Analyzing, L5- Evaluating, L6-Creating)
PART – A (5  2=10 Marks)
Define Algorithm.
1. L1 CO1
2. Differentiate time and space complexity. L4 CO1
3. List out the properties of asymptotic notations. L1 CO1
4. Define Brute force. L1 CO2
5. What is exhaustive search? L1 CO2
PART – B [2 X 13 = 26 Marks]
a) Explain in detail about fundamentals of algorithmic problem solving. 13 L2 CO1
6.
OR
b) Explain in detail about asymptotic notations. CO1
13 L2
Using exhaustive search solve traveling salesman problem (6)
A = {{0, 10, 15, 20,} {5,0, 9,10,},{6, 13, 0, 12}, {8, 8, 9, 0}
knapsack problem(7)
L3
a) Item weight value 13 CO2
1 7 $42
7. 2 3 $12
3 4 $40
4 5 $25
OR
L2
b) Explain the binary search with suitable example. 13 CO2

PART – C [1 X 14 = 14 Marks]
a) Explain in detail about Strassen’s Matrix Multiplication. 14 L2 CO1
8. OR
Give the recursive algorithm which finds the number of binary digits in the
CO1
b) binary representation of a positive decimal integer. Find the recurrence 14 L1
relation and complexity.?
Prepared by Subj. Co-Ordinator Faculty Chairman HOD/ S&H Principal

PART-A

1) ALGORITHM: An algorithm is a set of commands that must be followed

for a computer to perform calculations or other problem-solving
operations.

2) Time complexity:
How long an algorithm takes to run, as a function of the amount of input
it receives. Time complexity is expressed in terms of the number of basic
operations performed by the algorithm.

Space complexity:
How much memory an algorithm requires to run, as a function of the
amount of input it receives. Space complexity is expressed in terms of
the size of the input data.

#Both time and space complexity are important for evaluating and
optimizing the efficiency of algorithms. Time complexity is important for
time-sensitive applications, while space complexity is important for
applications running on memory-constrained devices.

3) IIn general, these notations have the following properties:

1. Reflexive: f(n) = O(f(n)), f(n) = Ω(f(n)), f(n) = Θ(f(n))
2. Transitive: if f(n) = O(g(n)) and g(n) = O(h(n)), then f(n) = O(h(n))
3. Symmetric: if f(n) = Θ(g(n)), then g(n) = Θ(f(n))
4. Addition: f(n) + g(n) = O(max(f(n), g(n))), f(n) + g(n) = Θ(max(f(n), g(n)))
5. Multiplication: f(n) * g(n) = O(f(n) * g(n)), f(n) * g(n) = Ω(f(n) * g(n)), f(n)
* g(n) = Θ(f(n) * g(n))

4) Brute Force: It is a straightforward method used in algorithmic

problem-solving that checks every possible solution until the correct
one is found. Brute Force Algorithms function by searching each
element sequentially until the desired result is found or all options are
exhausted.
5) Exhaustive Search: is a brute-force algorithm that systematically
enumerates all possible solutions to a problem and checks each one to
see if it is a valid solution. This algorithm is typically used for problems
that have a small and well-defined search space, where it is feasible to
check all possible solutions.

PART-B

6) A)FUNDAMENTALS OF ALGORITHMIC PROBLEM SOLVING:

i)Understanding the Problem:

Read the problem’s description carefully and ask questions if you have
any doubt s about the problem, do a few small examples by hand, think
about special cases, and ask questions again if needed. It helps to
understand how such an algorithm works and to know its strengths and
weaknesses, especially if you have to choose among several available
algorithms. But often you will not find a readily available algorithm and
will have to design your own. Determining the Capabilities of the
Computational
ii)Device:
Once you completely understand a problem, you need to determine the
capabilities of the computational device. The central assumption of the
RAM model does not hold for some newer computers that can execute
operations concurrently, i.e., in parallel. Algorithms that take advantage
of this capability are called parallel algorithms.
Choosing between Exact and Approximate Problem Solving: The next
principal decision is to choose between solving the problem exactly or
solving it approximately.
iii)Algorithm Design
An algorithm design technique is a general approach to solving
problems algorithmically that is applicable to a variety of problems from
different areas of computing.
Algorithm design techniques make it possible to classify algorithms
according to an underlying design idea:
(i) Pseudo code is a mixture of a natural language and programming
language. Pseudo code is usually more precise than natural language.
(ii) Flowchart is a method of expressing an algorithm by a collection
of connected geometric shapes containing descriptions of the
algorithms steps.
iv)Proving an Algorithm’s Correctness:
Once an algorithm has been specified, you have to prove its
correctness. That is, you have to prove that the algorithm yields a
required result for every legitimate input in a finite amount of time.
In order to show that an algorithm is incorrect, you need just one
instance of its input for which the algorithm fails
v)Analyzing an Algorithm:
While analyzing an algorithm, we should consider the following factors.
Time efficiency: It is indicating how fast the algorithm runs.
Space efficiency: It is indicating how much extra memory it uses.
Simplicity: It means generating sequence of instructions which are easy
to understand.
Generality: We should write general algorithms for similar problems. So
we can reuse the same algorithms. If you are not satisfied with
the algorithm efficiency, simplicity or generality you must redesign the
algorithm.
vi)Coding an algorithm:
The coding of an algorithm is done by suitable programming language.

OR
6b) ASYMPTOTIC NOTATIONS:
1. O Notation (Big Oh)
2. Ω Notation (Big Omega)
3. θ Notation (Big Theta)

1) O Notation (Big Oh)

Definition: A function f(n) is said to be in O(g(n)), denoted
f(n)∈O(g(n)), if f(n) is bounded above by some constant multiple of
g(n) for all large n, i.e., if there exist some positive constant c and
some nonnegative integer n0 such that

f(n) ≤ cg(n) for all n ≥ n0 and c > 0.

O notation analyses the worst case for the given function.

The definition is illustrated in the following figure.

’
Here n is size of an input &f(n) is a function of n.
When the input size increases, then the time is also increases.
Eg.
Let take f(n)=3n+2 and
g(n)=n. We have to prove
f(n) ∈O(g(n)). By the
definition,
f(n)≤c g(n)
3n+2≤ c * n where c>0, n0≥1.
We can substitute any value
for c. The best option is,
When c=4, 3n+2≤ 4 * n.
Most of the cases, 4*n is greater than
3n+2. Where n≥2.
Reason for taking n≥2:
If n=1, 3(1)+2 ≤ 4(1)=> 5≤4=> Becomes False.
If n=2, 3(2)+2 ≤ 4(2)=> 8≤8=> Becomes True.
If n=3, 3(3)+2 ≤ 4(3)=> 11≤12=> Becomes
True. If n=4, 3(4)+2 ≤ 4(4)=> 14≤16=>
Becomes True. And so on.
Therefore 3n+2 ∈ O(n).

2) . Ω Notation (Big Omega):

Definition: A function f(n) is said to be in Ω(g(n)), denoted f(n) ∈
Ω(g(n)), if f(n) is bounded below by some positive constant multiple
of g(n) for all large n, i.e., if there exist some positive constant c and
some nonnegative integer n0 such that
f(n) ≥ cg(n) for all n ≥ n0 and c > 0.
Ω notation analyses the best case for the given function. The
definition is illustrated in the following figure.
Here n is size of an input & f(n) is a function of n.
When the input size increases, then the time is also increases.

3. θ Notation (Big Theta):

Definition: A function f(n) is said to be in θ(g(n)), denoted f(n) ∈
θ(g(n)), if f(n) is bounded both above and below by some positive
constant multiples of g(n) for all large n, i.e., if there exist some
positive constants c1 and c2 and some nonnegative integer n0 such
that c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ n0.
θ notation analyses the average case for the given function.

Here n is size of an input &f(n) is a function of n.

When the input size increases, then the time is also increases. c1 and
c2 are different constants.
f(n) is bounded by both upper and lower i.e) c1g(n) ≤ f(n) ≤ c2g(n).

7A) Travelling Salesman Problem:

Knapsack Problem:

(OR)

7B) BINARY SEARCH PROBLEM:

It is an efficient algorithm for searching in a sorted array. It is an
example for divide and conquer technique.
Working of binary search:
It works by comparing a search key k with the array‘s middle element
A [m].
If they match, the algorithm stops; otherwise the same operation is
repeated
recursively for the first half of the array if K < A (m) and for the
second half if K > A (m).
K
A [0] … A [m – 1] A [m] A [m+1] …. A [n-1]
Search here if K < A (m) Search here if K > A
Example:
Given set of elements

Search key: K=55

3 14 27 31 42 55 70 81 98

The iterations of the algorithm are given as:

A [m] = K, so the algorithm stops
Binary search can also implemented as a nonrecursive algorithm.
Algorithm Binarysearch(A[0..n-1], k)
// Implements nonrecursive binarysearch
// Input: An array A[0..n-1] sorted in ascending order and a search
key k // Output: An index of the array‗s element that is equal to k or
-1 if there is no such element l←0; r←n-1
while l ≤ r do
m←[(l+r)/2]
if k = A[m] return m else
if k < A[m] r←m-1 else
l←m+1
return -1
Analysis:
The efficiency of binary search is to count the number of times the
search key is compared with an element of the array.
For simplicity, three-way comparisons are considered. This assumes
that after one comparison of K with A [M], the algorithm can
determine whether K is smaller, equal to, or larger than A [M]. The
comparisons not only depend on ‗n‗ but also the particular instance
of the problem.
The worst case comparison Cw (n) includes all arrays that do not
contain a search key, after one comparison the algorithm considers
the half size of the array.Cw (n) = Cw (n/2) + 1 for n > 1, Cw (1) = 1 ---
----------------------------------------------------- eqn(1)
k
To solve such recurrence equations, assume that n = 2 to obtain the solution.
Cw ( k) = k +1 = log2n+1
For any positive even number n, n = 2i, where I > 0. now the LHS of
eqn (1) is:
Cw (n) = [ log2n]+1 = [ log22i]+1 = [ log 22 + log2i] + 1 = ( 1 + [log2i])
+1
= [ log2i] +2
The R.H.S. of equation (1) for n = 2 i is
Cw [n/2] + 1 = Cw [2i / 2] + 1
= Cw (i) + 1
= ([log2 i] + 1) + 1
= ([log2 i] + 2
Since both expressions are the same, the assertion is proved.
The worst – case efficiency is in θ (log n) since the algorithm reduces
the size of the array remained as about half the size, the numbers of
iterations needed to reduce the initial size n to the final size 1 has to
be about log2n. Also the logarithmic functions grow so slowly that its
values remain small even for very large values of n.
The average-case efficiency is the number of key comparisons made
which is slightly smaller than the worst case.
More accurately, . e.Cavg (n) ≈ log2n for
successful search iCavg (n) ≈ log2n –1
for unsuccessful search Cavg (n) ≈ log2n + 1

PART-C

8A) Strassen’s Matrix Multiplication:

This is a problem which is used for multiplying two n x n matrixes.
Volker Strassen in 1969 introduced a set of formula with fewer number of
multiplications by increasing the number of additions.
Based on straight forward or Brute-Force algorithm.

Where,
m1 = ( a00 + a11 ) * (b00 + b11)
m2 = ( a10 + a11 )* b00
m3 = a00 * (b01 - b11)
m4 = a11 * (b10 – b00)
m5 = ( a00 + a01 * b11)
m6 = (a10 – a00) * (b00 + b01)
m7 = ( a01 - a11 ) * (b10 + b11)

Thus, to multiply two 2-by-2 matrixes, Strassen‗s algorithm requires seven

multiplications and 18 additions / subtractions, where as the brute-force
algorithm requires eight multiplications and 4 additions. Let A and B be two
n-by-n matrixes when n is a power of two. (If not, pad the rows and columns
with zeroes). We can divide A, B and their product ,
Analysis:
The efficiency of this algorithm, M(n) is the number of multiplications in
multiplying two n by n matrices according to Strassen‗s algorithm.

(OR)

8B) An investigation of a recursive version of the algorithm which finds the

number of binary digits in the binary representation of a positive decimal
integer.
ALGORITHM BinRec(n)
//Input: A positive decimal integer n
//Output: The number of binary digits in n‗s binary representation if n = 1
return 1
else return BinRec( n/2 )+ 1

Algorithm analysis:
The number of additions made in computing BinRec( n/2 ) is A( n/2 ), plus
one more addition is made by the algorithm to increase the returned value
1.This lead to the recurrence
A(n) = A( n/2 ) + 1 for n > 1.
Since the recurrence call end when n is equal to 1 and there are no addition
made then the initial condition is A(1)=0
The standard approach to solving such a recurrence is to solve it only for n = 2k