UNIT 1

SHORT ANSWER QUESTIONS

1.​ Define Algorithm.

Ans: An algorithm is a set of commands that must be followed for a computer to perform
calculations or other problem-solving operations.
An algorithm is a procedure used for solving a problem or performing a computation. Algorithms
act as an exact list of instructions that conduct specified actions step by step in either hardware-
or software-based routines.
2.​ Explain amortized complexity.
Ans: Amortized complexity is the average time taken per operation over a sequence of
operations. It's useful when some operations in a sequence are slow, and others are faster.
Amortized complexity is a way of analyzing the performance of algorithms or data structures
that have occasional high-cost operations. It takes into account not only the worst-case scenario
but also the average cost over a series of operations.
3.​ Explain time complexity
Ans: Time complexity is a way to measure how long an algorithm takes to run, based on the size
of the input data. It's a type of computational complexity, and is often used to compare and
evaluate algorithms.
The time complexity of an algorithm quantifies the amount of time taken by an algorithm to run
as a function of the length of the input. Note that the time to run is a function of the length of
the input and not the actual execution time of the machine on which the algorithm is running
on.
4.​ Explain space complexity
Ans: Space complexity is the amount of memory an algorithm needs to solve a problem, based
on the size of the input data. It's an important factor when designing algorithms or choosing
data structures.
The space complexity of an algorithm or a data structure is the amount of memory space
required to solve an instance of the computational problem as a function of characteristics of
the input. It is the memory required by an algorithm until it executes completely.
5.​ Define Asymptotic Notations
Ans: Asymptotic notation is a mathematical shorthand used to describe how an algorithm's
running time or space complexity changes as the input size increases. It's used to analyze the
efficiency and performance of an algorithm, and to compare multiple algorithms to choose the
best one.
6.​ Define divide and conquer algorithm
Ans: A divide and conquer algorithm is a strategy of solving a large problem by
●​ breaking the problem into smaller sub-problems
●​ solving the sub-problems, and
●​ combining them to get the desired output.

To use the divide and conquer algorithm, recursion is used.

7.​ Define probabilistic analysis
Ans: In analysis of algorithms, probabilistic analysis of algorithms is an approach to estimate the
computational complexity of an algorithm or a computational problem. It starts from an
assumption about a probabilistic distribution of the set of all possible inputs. This assumption is
then used to design an efficient algorithm or to derive the complexity of a known algorithm. This
approach is not the same as that of probabilistic algorithms, but the two may be combined.
8.​ Define Randomized Algorithms.
Ans: A randomized algorithm is a technique that uses a source of randomness as part of its logic.
It is typically used to reduce either the running time, or time complexity; or the memory used, or
space complexity, in a standard algorithm. The algorithm works by generating a random
number, rr, within a specified range of numbers, and making decisions based on rr's value.
A randomized algorithm could help in a situation of doubt by flipping a coin or a drawing a card
from a deck in order to make a decision. Similarly, this kind of algorithm could help speed up
a brute force process by randomly sampling the input in order to obtain a solution that may not
be totally optimal, but will be good enough for the specified purposes.
9.​ Define pseudocode and flowchart
Ans: Pseudocode is a method of describing computer algorithms using a combination of natural
language and programming language.
A Pseudocode is defined as a step-by-step description of an algorithm. Pseudocode does not use
any programming language in its representation instead it uses the simple English language text
as it is intended for human understanding rather than machine reading.
10.​How can we measure an algorithm’s running time?
Ans: To calculate the running time, find the maximum number of nested loops that go through a
significant portion of the input. Some algorithms use nested loops where the outer loop goes
through an input n while the inner loop goes through a different input m. The time complexity in
such cases is O(nm).

LONG ANSWER QUESTIONS

1.​ Define an algorithm and its characteristics
Ans: An algorithm is a procedure used for solving a problem or performing a
computation. Algorithms act as an exact list of instructions that conduct specified
actions step by step in either hardware- or software-based routines.
The word Algorithm means ” A set of finite rules or instructions to be followed in
calculations or other problem-solving operations ” ​
Or ​
” A procedure for solving a mathematical problem in a finite number of steps that
frequently involves recursive operations”.
 For some instructions to be an algorithm, it must have the following characteristics:
●​ Clear and Unambiguous: The algorithm should be unambiguous. Each of its steps should
be clear in all aspects and must lead to only one meaning.
●​ Well-Defined Inputs: If an algorithm says to take inputs, it should be well-defined inputs.
It may or may not take input.
●​ Well-Defined Outputs: The algorithm must clearly define what output will be yielded
and it should be well-defined as well. It should produce at least 1 output.
●​ Finite-ness: The algorithm must be finite, i.e. it should terminate after a finite time.
●​ Feasible: The algorithm must be simple, generic, and practical, such that it can be
executed with the available resources. It must not contain some future technology or
anything.
●​ Language Independent: The Algorithm designed must be language-independent, i.e. it
must be just plain instructions that can be implemented in any language, and yet the
output will be the same, as expected.
●​ Input: An algorithm has zero or more inputs. Each that contains a fundamental operator
must accept zero or more inputs.
●​ Output: An algorithm produces at least one output. Every instruction that contains a
fundamental operator must accept zero or more inputs.
●​ Definiteness: All instructions in an algorithm must be unambiguous, precise, and easy to
interpret. By referring to any of the instructions in an algorithm one can clearly
understand what is to be done. Every fundamental operator in instruction must be
defined without any ambiguity.
●​ Finiteness: An algorithm must terminate after a finite number of steps in all test cases.
Every instruction which contains a fundamental operator must be terminated within a
finite amount of time. Infinite loops or recursive functions without base conditions do
not possess finiteness.
●​ Effectiveness: An algorithm must be developed by using very basic, simple, and feasible
operations so that one can trace it out by using just paper and pencil.
2.​ Sort the records with the following index values in the ascending order using quick
sort algorithm. 10, 80, 30, 90, 40, 50, 70
Ans: QuickSort is a sorting algorithm based on the Divide and Conquer that picks an
element as a pivot and partitions the given array around the picked pivot by placing the
pivot in its correct position in the sorted array.
There are mainly three steps in the algorithm.​
1. Choose a pivot​
2. Partition the array around pivot. After partition, it is ensured that all elements are
smaller than all right and we get index of the end point of smaller elements. The left and
right may not be sorted individually.​
3. Recursively call for the two partitioned left and right subarrays.​
4. We stop recursion when there is only one element is left.

Complexity Analysis of Quick Sort :

Time Complexity:
●​ Best Case : Ω (N log (N))​
The best-case scenario for quicksort occur when the pivot chosen at the each step
divides the array into roughly equal halves.​
In this case, the algorithm will make balanced partitions, leading to efficient Sorting.
●​ Average Case: θ ( N log (N))​
Quicksort’s average-case performance is usually very good in practice, making it one of
the fastest sorting Algorithm.
●​ Worst Case: O(N ^ 2)​
The worst-case Scenario for Quicksort occur when the pivot at each step consistently
results in highly unbalanced partitions. When the array is already sorted and the pivot is
always chosen as the smallest or largest element. To mitigate the worst-case Scenario,
various techniques are used such as choosing a good pivot (e.g., median of three) and
using Randomized algorithm (Randomized Quicksort) to shuffle the element before
sorting.
3.​ Define Asymptotic Notations. Explain in detail
Ans: Asymptotic notations are mathematical tools used to describe the efficiency of
an algorithm by analyzing its running time and space complexity. They are used to
compare algorithms and choose the best one.
There are three types of asymptotic notations:
●​ Big O: Used to describe the worst-case running time of an algorithm
●​ Big Theta (Θ): Used to describe when the running time is the same for all cases
●​ Big Omega (Ω): Used to describe the best-case running time of an algorithm
Asymptotic notations are useful for answering questions like whether an algorithm
slows down when the input size increases, or if it maintains its speed.

Big-O Notation (O-notation)

Big-O notation represents the upper bound of the running time of an algorithm.
Therefore, it gives the worst-case complexity of an algorithm.
.It is the most widely used notation for Asymptotic analysis.​
.It specifies the upper bound of a function.​
.The maximum time required by an algorithm or the worst-case time complexity.​
.It returns the highest possible output value(big-O) for a given input.​
.Big-O(Worst Case) It is defined as the condition that allows an algorithm to complete
statement execution in the longest amount of time possible.
If f(n) describes the running time of an algorithm, f(n) is O(g(n)) if there exist a
positive constant C and n0 such that, 0 ≤ f(n) ≤ cg(n) for all n ≥ n0
It returns the highest possible output value (big-O)for a given input.
The execution time serves as an upper bound on the algorithm’s time complexity.
Mathematical Representation of Big-O Notation:
O(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ f(n) ≤ cg(n) for all
n ≥ n0 }

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.
.Theta (Average Case) You add the running times for each possible input combination
and take the average in the average case.
Let g and f be the function from the set of natural numbers to itself. The function f is
said to be Θ(g), if there are constants c1, c2 > 0 and a natural number n0 such that
c1* g(n) ≤ f(n) ≤ c2 * g(n) for all n ≥ n0

Theta notation
Mathematical Representation of Theta notation:
Θ (g(n)) = {f(n): there exist positive constants c1, c2 and n0 such that 0 ≤ c1 * g(n) ≤
f(n) ≤ c2 * g(n) for all n ≥ n0}
 Note: Θ(g) is a set

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.
The execution time serves as a lower bound on the algorithm’s time complexity.
It is defined as the condition that allows an algorithm to complete statement
execution in the shortest amount of time.
Let g and f be the function from the set of natural numbers to itself. The function f is
said to be Ω(g), if there is a constant c > 0 and a natural number n0 such that c*g(n)
≤ f(n) for all n ≥ n0

Mathematical Representation of Omega notation :

Ω(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ cg(n) ≤ f(n) for
all n ≥ n0 }

●​ There are two more notations called little o and little omega. Little o provides a strict
upper bound (equality condition is removed from Big O) and little omega provides strict
lower bound (equality condition removed from big omega)
4.​ Define binary search. explain in detail with example
Ans : Binary search is a search algorithm that finds the location of a target value in a
sorted array. It is also known as half-interval search, logarithmic search, or binary
chop.
Here's how binary search works:
1.​ Compare the target value to the middle element of the array.
2.​ If the values are not equal, eliminate the half of the array that the target value cannot be
in.
3.​ Continue searching in the remaining half by comparing the target value to the middle
element of that half.
 4.​ Repeat until the target value is found or the remaining half is empty.
Binary search is faster than linear search, except for small arrays. However, the array
must be sorted first.

Let the element to search is, K = 56

We have to use the below formula to calculate the mid of the array -
1.​ mid = (beg + end)/2
2.​ So, in the given array -
3.​ beg = 0
4.​ end = 8
5.​ mid = (0 + 8)/2 = 4. So, 4 is the mid of the array.
Now, the element to search is found. So algorithm will return the index of the element matched.
Time Complexity

Case Time Complexity

Best Case O(1)

Average Case O(logn)

Worst Case O(logn)

5. Define merge sort. explain in detail with example

Ans: Merge sort is a sorting algorithm that uses the divide-and-conquer strategy to efficiently
sort a list of elements in ascending order:
●​ Divide: Split the list into two halves
●​ Conquer: Divide the halves further until each sublist contains only one element
●​ Combine: Compare the smaller halves and merge them together to form a sorted list
Let’s look at the working of above example:
Divide:
●​ [38, 27, 43, 10] is divided into [38, 27 ] and [43, 10] .
●​ [38, 27] is divided into [38] and [27] .
 ●​ [43, 10] is divided into [43] and [10] .
Conquer:
●​ [38] is already sorted.
●​ [27] is already sorted.
●​ [43] is already sorted.
●​ [10] is already sorted.
Merge:
●​ Merge [38] and [27] to get [27, 38] .
●​ Merge [43] and [10] to get [10,43] .
●​ Merge [27, 38] and [10,43] to get the final sorted list [10, 27, 38, 43]
Therefore, the sorted list is [10, 27, 38, 43] .
6.​ Explain Strassen's matrix multiplication algorithm
Ans: Strassen's matrix multiplication algorithm is a recursive method that uses a divide
and conquer strategy to multiply matrices faster than the standard algorithm:
1.​ Divide: Split the two matrices to be multiplied, A and B, into four smaller matrices that
are each about half the size of the original.
2.​ Calculate: Use the smaller matrices to calculate seven values, P1 through P7, by
performing simple additions and subtractions.
3.​ Combine: Use the values of P1 through P7 to compute the final result matrix, C.
Strassen's algorithm is faster than the standard algorithm for large matrices, but the
standard algorithm is often better for smaller matrices. It works best for matrices with
dimensions that are powers of 2. If the matrices are not the right size, you can pad them
with zeros to make them work.
Algorithm: Matrix-Multiplication (X, Y, Z)
for i = 1 to p do
for j = 1 to r do
Z[i,j] := 0
for k = 1 to q do
Z[i,j] := Z[i,j] + X[i,k] × Y[k,j]
Complexity
Here, we assume that integer operations take O(1) time. There are three for loops in this
algorithm and one is nested in other. Hence, the algorithm takes O(n3) time to execute.
Divide X, Y and Z into four (n/2)×(n/2) matrices as represented below −
Z=[IKJL]Z=[IJKL] X=[ACBD]X=[ABCD] and Y=[EGFH]Y=[EFGH]
Using Strassen’s Algorithm compute the following −
M1:=(A+C)×(E+F)M1:=(A+C)×(E+F)
M2:=(B+D)×(G+H)M2:=(B+D)×(G+H)
M3:=(A−D)×(E+H)M3:=(A−D)×(E+H)
M4:=A×(F−H)M4:=A×(F−H)
M5:=(C+D)×(E)M5:=(C+D)×(E)
M6:=(A+B)×(H)M6:=(A+B)×(H)
M7:=D×(G−E)M7:=D×(G−E)
Then,
I:=M2+M3−M6−M7I:=M2+M3−M6−M7
J:=M4+M6J:=M4+M6
K:=M5+M7K:=M5+M7
L:=M1−M3−M4−M5