Department of Computer Science and Engineering (CSE)

Course: M.Tech CSE

Year/Semester: 1st/ 1st
Subject Name: Advanced Algorithm (MTCS 102)

Submitted To: Ms. Sheenam Naaz

DATE OF DATE OF
UNIT CO ASSIGNMENT REMARKS
ISSUE SUBMISSION

Submitted By:
 Assignment 1
UNIT 1

Q1. Define an algorithm and explain why algorithms are essential

in problem solving.

Ans 1. An algorithm is a set of commands that must be followed for a computer to perform
calculations or other problem-solving operations. According to its formal definition, an
algorithm is a finite set of instructions carried out in a specific order to perform a particular
task. It is not the entire program or code; it is simple logic to a problem represented as an
informal description in the form of a flowchart or pseudocode.

Algorithms play a crucial role in computing by providing a set of instructions for a computer
to perform a specific task. They are used to solve problems and carry out tasks in computer
systems, such as sorting data, searching for information, image processing, and much more.
An algorithm defines the steps necessary to produce the desired outcome, and the computer
follows the instructions to complete the task efficiently and accurately. The development of
efficient algorithms is a central area of computer science and has significant impacts in various
fields, from cryptography and finance to machine learning and robotics.

In computing, algorithms are essential for solving complex problems and tasks, improving
efficiency and performance, and enabling new technologies and applications.

Algorithms play a critical role in networking and communication systems, enabling efficient
and reliable data transfer and communication.

Q2. Differentiate between deterministic and non- deterministic algorithm provide

an example for each.

Ans 2. Deterministic Algorithm

a. A deterministic algorithm is one whose behavior is completely determined by its inputs and
the sequence of its instructions.
b. For a particular input, the computer will give always the same output.

c. Can solve the problem in polynomial time.

d. Can determine the next step of execution.

e. Operation are uniquely defined.

f. Like linear search and binary search

g. Deterministic algorithms usually have a well- defined worst-case time coplexcity

h. Deterministic algorithms are entirely predictable and always produce the same output for
the same input.

i. Deterministic algorithms usually provide precise solutions to problems.

j. Deterministic algorithms are commonly used in applications where precision is critical,

such as in cryptography, numerical analysis, and computer graphics.

Examples of deterministic algorithms include sorting algorithms like bubble sort, insertion
sort, and selection sort, as well as many numerical algorithms.

Non-deterministic Algorithm
a. A non-deterministic algorithm is one in which the outcome cannot be predicted with
certainty, even if the inputs are known.

b. For a particular input the computer will give different outputs on different execution.

c. Can't solve the problem in polynomial time.

d. Cannot determine the next step of execution due to more than one path the algorithm can
take.

e. Operation are not uniquely defined.

f. like 0/1 knapsack problem.

g. Time complexity of non- deterministic algorithms is often described in terms of expected

running time.

h. Non-deterministic algorithms may produce different outputs for the same input due to
random events or other factors.

i. non-deterministic algorithms often provide approximate solutions to the problems.

 j. Non-deterministic algorithms are often used in applications where finding an exact
solution is difficult or impractical, such as in artificial intelligence, machine learning,
and optimization problems.

Examples of non-deterministic algorithms include probabilistic algorithms like Monte

Carlo methods, genetic algorithms, and simulated annealing.

Q3. what is the significance of efficiency in algorithms, how do we measure

efficiency of an algorithm.

Ans 3. In computer science, algorithmic efficiency is a property of an algorithm which relates

to the amount of computational resources used by the algorithm. An algorithm must be
analyzed to determine its resource usage, and the efficiency of an algorithm can be measured
based on the usage of different resources. Algorithmic efficiency can be thought of as
analogous to engineering productivity for a repeating or continuous process.

For maximum efficiency it is desirable to minimize resource usage. However, different

resources such as time and space complexity cannot be compared directly, so which of two
algorithms is considered to be more efficient often depends on which measure of efficiency is
considered most important.

An algorithm needs to be processed very quickly, so it must perform as flawlessly as possible.

This is why every new algorithm goes through testing to calculate its efficiency, using
theoretical analysis and benchmarking to compare it against other algorithms.

Time and space complexity are the two main measures for calculating algorithm efficiency,
determining how many resources are needed on a machine to process it. Where time measures
how long it takes to process the algorithm, space measures how much memory is used.

Unfortunately, numerous challenges, such as the programming language used, the processor,
the instruction set, etc., can arise during the implementation process, causing headaches for
programmers.

Despite this, time and space complexity have proven to be very effective ways of measuring
algorithm efficiency.

Q4. Explain the concept of a brute force algorithm. Provide an example where a
brute force algorithm may be applied.
Ans 4. A brute force algorithm is a straightforward and uncomplicated approach to solving a
problem or performing a task. It relies on sheer computational power to systematically check
all possible solutions or elements in a search space, without taking advantage of any particular
characteristics of the problem that might lead to more efficient solutions. In essence, it's a
"brute" method because it systematically explores every possibility, making it relatively simple
to implement but often inefficient for complex problems.

Key characteristics of a brute force algorithm include:

1. Exhaustive Search: The algorithm systematically examines every possible option in the
solution space, typically through a nested loop or recursive structure.

2. No Optimization: It doesn't incorporate any optimization techniques or heuristics to reduce

the search space or make the process more efficient.

3. Simplicity: Brute force algorithms are usually simple to understand and implement, making
them a good choice for solving relatively small or straightforward problems.

4. High Time Complexity: Because they check all possibilities, the time complexity of brute
force algorithms can be high, especially for large problem instances.

Example of a Brute Force Algorithm:

Consider the problem of finding the two numbers in an unsorted list that sum up to a specific
target value. This is often referred to as the "Two Sum" problem. A brute force algorithm for
this problem would involve checking every possible pair of numbers in the list to see if their
sum matches the target value.

Here's how the brute force algorithm might work in Python:

def two_sum_bruteforce(nums, target):

for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
return None

In this example, the algorithm uses two nested loops to compare each pair of numbers in the
list. If a pair with the desired sum is found, the algorithm returns their indices. However, this
algorithm has a time complexity of O(n2) because it checks all possible pairs. For large lists, it
can be highly inefficient.

Brute force algorithms are suitable for small problem instances or scenarios where more
optimized algorithms may be overly complex to implement or unnecessary. In many cases,
especially in large-scale or computationally intensive problems, more efficient algorithms like
divide and conquer, dynamic programming, or greedy algorithms are preferred due to their
ability to solve problems with lower time complexity.
Q5. Discuss the importance of data structures in algorithm design. Provide
examples of data structures and explain how they impact algorithm.

Ans 5. Data structures are fundamental components in computer science and algorithm design.
They play a crucial role in organizing and manipulating data efficiently, which, in turn,
significantly impacts the design and performance of algorithms. The choice of an appropriate
data structure can make the difference between an efficient algorithm and an inefficient one.
Here are some key reasons why data structures are important in algorithm design:

a. Efficient Data Storage: Data structures provide a way to store and organize data in
memory efficiently. The choice of data structure can impact the space requirements of
an algorithm, and using the right structure can minimize memory usage.

b. Fast Data Retrieval: Different data structures offer various methods for searching,
accessing, and retrieving data. The choice of data structure can greatly affect the speed
of these operations. For example, arrays offer constant-time access, while linked lists
might require linear-time traversal.

c. Effective Data Manipulation: Data structures provide methods for adding, deleting, and
modifying data. The efficiency of these operations depends on the underlying data
structure. For instance, a well-designed hash table allows for fast insertion and retrieval,
while a simple list might require linear time for similar operations.

d. Problem-Specific Adaptability: Certain data structures are better suited to specific types
of problems. Choosing the right data structure can make the algorithm more natural,
easier to implement, and more efficient. For example, trees are often used for
hierarchical data, and graphs are ideal for modeling relationships between entities.

e. Optimizing Time Complexity: The use of the appropriate data structure can help reduce
the time complexity of an algorithm. For example, a binary search tree can provide
logarithmic-time search operations, while a linear search in an unsorted list is much
slower.

Here are some examples of data structures and how they impact algorithms:

a. Arrays: Arrays are simple and provide constant-time access to elements by index.
Algorithms that require random access, like searching, sorting, and dynamic
programming, often benefit from using arrays.

b. Linked Lists: Linked lists are efficient for insertions and deletions, especially when
elements are frequently added or removed from the middle of a list. Algorithms that
require dynamic resizing, such as stack or queue implementations, often use linked lists.
 c. Hash Tables: Hash tables are excellent for fast data retrieval and are used in various
algorithms, such as hash-based searching, caching, and frequency counting.

d. Trees: Tree data structures, such as binary search trees, AVL trees, and Red-Black trees,
are commonly used in algorithms that involve hierarchical data, searching, and
balancing.

e. Graphs: Graphs are versatile data structures that are used in algorithms for problems
involving relationships, such as graph traversal algorithms (e.g., depth-first search and
breadth-first search), shortest path algorithms (e.g., Dijkstra's algorithm), and network
flow problems.

f. Priority Queues: Priority queues are often used in algorithms that require efficient
handling of elements with different priorities, like Dijkstra's algorithm for finding the
shortest path in a graph or Huffman coding for data compression.

In summary, the choice of data structure is a critical decision in algorithm design. It impacts
the algorithm's efficiency, readability, and suitability for specific problem domains. Properly
selecting and using data structures is key to designing algorithms that perform optimally in
terms of time and space complexity.

Q6. Compare and contrast best case, worst case and average case time
complexity. Provide an algo example of each.

Ans 6: Best Case Time Complexity:

Best case time complexity represents the minimum amount of time an algorithm would take
for a given input. It assumes that the input is in the best possible state for the algorithm.
Example: Binary Search
The best case for binary search occurs when the target element is found in the middle of the
sorted array. In this case, the algorithm's time complexity is O(1) as it directly finds the target.

public int binarySearch(int[] arr, int target) {

int left = 0;
int right = arr.length - 1;

while (left <= right) {

int mid = left + (right - left) / 2;

if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
 } else {
right = mid - 1;
}
}
return -1; // Target not found
}

Worst Case Time Complexity:

Worst case time complexity represents the maximum amount of time an algorithm would take
for a given input. It assumes that the input is in the worst possible state for the algorithm.
Example: Selection Sort
The worst case for selection sort occurs when the input is in reverse order. This results in the
maximum number of comparisons and swaps, leading to a time complexity of O(n^2).

public void selectionSort(int[] arr) {

int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}

Average Case Time Complexity:

Average case time complexity represents the expected or average amount of time an algorithm
would take for a given input, considering all possible inputs and their probabilities.
Example: Quick Sort
Quick sort has an average case time complexity of O(n * log(n)) achieved through randomized
partitioning, which divides the input into roughly equal-sized subproblems and is expected to
perform well for random inputs.

public void quickSort(int[] arr, int low, int high) {

if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
 private int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}

Best case, worst case, and average case time complexities provide different insights into an
algorithm's performance under various conditions. They help us understand how an algorithm
behaves in practice and are important for selecting the right algorithm for a specific problem.

Q7. How does the concept of growth functions relate to the analysis of
algorithms? Why is it important to understand the growth rate of algorithm.

Ans 7: The concept of growth functions, often referred to as the "Big O notation" or asymptotic
analysis, is crucial to the analysis of algorithms because it provides a way to describe and
compare the efficiency of algorithms independently of specific machine configurations,
constant factors, and lower-order terms. Here's how it relates to the analysis of algorithms and
why it is important:

• Standardized Comparison: Growth functions allow us to standardize the comparison of

different algorithms and evaluate their efficiency by focusing on how the algorithm's
runtime grows as the input size increases. This is particularly important in algorithm
analysis because it provides a consistent and objective way to compare algorithms'
performance.

• Independence from Hardware and Language: Algorithms are designed to solve general
computational problems, and they can be implemented on various hardware and
programming languages. By analyzing their growth rates, we abstract away the details
of specific hardware or software environments, allowing us to make algorithmic
comparisons that hold across different systems.
 • Efficiency Prediction: Growth functions help in predicting how an algorithm will
perform as the input size becomes very large. It allows us to estimate how much time
and resources will be needed for large-scale computations, which is vital for practical
applications in fields like data analysis, scientific simulations, and software
development.

• Optimization Prioritization: By understanding the growth rate of algorithms, we can

prioritize the optimization of the most time-consuming parts of a program. If one part
of the algorithm has a higher growth rate than the rest, optimizing that part will have a
more significant impact on overall performance.

• Algorithm Selection: In practical applications, we often need to choose the right

algorithm for a specific problem. Understanding the growth rate helps us select the most
efficient algorithm for the problem, ensuring that the computational resources are used
efficiently.

• Algorithmic Trade-offs: Analyzing the growth rate of algorithms can reveal trade-offs
between different aspects of an algorithm, such as memory usage and runtime. For
example, some algorithms may use less memory but have a higher time complexity,
while others may use more memory but run faster. Understanding these trade-offs is
essential for making informed decisions.

• Scaling Up: As data and computational needs continue to grow, algorithms must scale
efficiently to handle larger inputs. Understanding the growth rate helps ensure that an
algorithm can meet these scalability requirements.

The analysis of the growth rate of algorithms is crucial for making informed decisions about
algorithm selection, optimization, and resource allocation in various computational
applications. It provides a common language and framework for discussing algorithm
efficiency, which is essential for both theoretical analysis and practical software development.

Q8. State the Masters Theorem and explain its significance in algorithm analysis.
Provide an example of an algorithm where the Masters theorem can be applied.

Ans 8: The Master Theorem is a mathematical tool used to analyze the time complexity of
divide-and-conquer algorithms. It provides a way to determine the time complexity of such
algorithms in a recursive form and is particularly useful for solving recurrence relations. The
Master Theorem is significant in algorithm analysis because it offers a straightforward way to
classify and analyze the efficiency of many well-known algorithms, especially those that
exhibit a specific recursive structure. By using the Master Theorem, we can quickly assess the
time complexity without having to manually derive recurrence relations, simplifying the
process of algorithm analysis and design.
The Master Theorem can be stated as follows:
Suppose we have a divide-and-conquer algorithm with the following recurrence relation:
T(n) = a * T(n/b) + f(n)
Where:
- T(n) is the time complexity of the algorithm for an input of size n.
- a is the number of subproblems created in each recursion.
- n/b is the size of each subproblem.
- f(n) is the time spent on combining the solutions to the subproblems and dividing the original
problem into subproblems.

The Master Theorem provides a solution for T(n) in terms of three cases, which depend on the
relationship between a, b, and f(n):
1. If f(n) = O(n^c) for some constant c < log_b(a), then T(n) = O(n^log_b(a)).
2. If f(n) = O(n^log_b(a)), then T(n) = O(n^log_b(a) * log(n)).
3. If f(n) = Ω(n^c) for some constant c > log_b(a), and if a * f(n/b) ≤ k * f(n) for some constant
k < 1 and sufficiently large n, then T(n) = O(f(n)).
Now, let's provide an example of an algorithm where the Master Theorem can be applied:
Example: Merge Sort
Merge Sort is a classic divide-and-conquer sorting algorithm. It divides an unsorted array into
two equal halves, recursively sorts each half, and then merges the two sorted halves to produce
a sorted array. The recurrence relation for Merge Sort is as follows:
T(n) = 2 * T(n/2) + O(n)
In this case, a = 2, b = 2, and f(n) = O(n). We can apply the Master Theorem to determine the
time complexity of Merge Sort.
Here, we can see that f(n) = O(n) is in Case 2, where f(n) is of the same order as n^log_b(a).
Therefore, according to the Master Theorem, the time complexity of Merge Sort is T(n) =
O(n*log(n)). This is a valuable result as it allows us to confidently state the time complexity of
Merge Sort without having to manually solve the recurrence relation.

The significance of the Master Theorem is that it simplifies the analysis of algorithms with
recursive structures and provides a clear way to classify them into well-defined time
complexity categories. This, in turn, aids in the design and comparison of algorithms, making
it a valuable tool in algorithm analysis.

Q9. Discuss the limitations of the Master’s theorem and situations where it cannot
be applied in algorithm analysis.

Ans 9: The Master's Theorem is a valuable tool for analyzing the time complexity of divide-
and-conquer algorithms, but it has limitations and cannot be applied to all types of recurrence
relations and algorithmic scenarios. Here are some limitations and situations where the Master's
Theorem cannot be applied in algorithm analysis:
 • Non-Divide-and-Conquer Algorithms: The Master's Theorem is specifically designed
for divide-and-conquer algorithms, where a problem is divided into subproblems of the
same type. It cannot be applied to algorithms with different recursive structures, such
as algorithms that use dynamic programming or memoization.

• Variable Subproblem Sizes: The Master's Theorem assumes that subproblems are
divided into equal-sized subproblems. If an algorithm divides the problem into
subproblems with varying sizes, the theorem may not be applicable. This is a common
limitation for algorithms that use a "divide and conquer" strategy with unbalanced
subproblems.

• Non-Constant Number of Subproblems: The Master's Theorem assumes a constant

number of subproblems created in each recursion step. Algorithms that create a variable
number of subproblems in different recursive calls, such as some graph algorithms or
algorithms with irregular partitioning, do not fit the Master's Theorem framework.

• Complex Combining Step: The Master's Theorem assumes a straightforward

combining step where the solutions of subproblems are combined. If the combining
step involves complex data structures or operations that cannot be easily expressed in
terms of the input size, the theorem may not be directly applicable.

• Non-Polynomial Time Complexity: The Master's Theorem is primarily designed for

recurrence relations with polynomial terms (e.g., n^2, n*log(n)). It cannot be applied to
algorithms with non-polynomial time complexity, such as algorithms with exponential
or factorial growth rates.

• Non-Multiplicative Constants: The Master's Theorem doesn't take into account non-
multiplicative constants in the recurrence relation. Some algorithms may have time
complexity functions that involve constants or other factors not accounted for by the
theorem.

• Situations Outside the Theorem's Cases: The Master's Theorem provides solutions for
recurrence relations that fit into specific cases (Case 1, Case 2, and Case 3). If an
algorithm's recurrence relation does not precisely match one of these cases, the theorem
cannot be directly applied.

• Recursive Algorithms with External Factors: Some algorithms have time complexities
influenced by external factors or real-world considerations, making it challenging to
model them using a simple recurrence relation. In such cases, the Master's Theorem
may not provide a complete analysis.

Q10: Solve the recurrence relation of T(n)=4T(n/2)+n2 using the Master’s

theorem. Clearly show each step of the solution.
Ans 10: To solve the recurrence relation T(n) = 4T(n/2) + n2 using the Master's Theorem, we
need to compare it with the standard form of the theorem:
T(n) = a * T(n/b) + f(n)
In this case:
- a = 4 (the number of subproblems)
- b = 2 (the factor by which the problem size is reduced in each subproblem)
- f(n) = n2 (the time spent on combining the solutions to the subproblems and dividing the
original problem into subproblems)
Now, we need to compare the function f(n) = n2 to n(log_b(a)). In this case, n(log_2(4)) simplifies to
n2, which means that f(n) falls into the same category as n(log_2(4)), so it satisfies Case 2 of the
Master's Theorem.

Case 2: Master's Theorem states that if f(n) is O(nc) for c equal to log_b(a), then the time
complexity of the recurrence relation T(n) is:
T(n) = O(nc * log(n))
In this case, c equals log_2(4), which is 2. Therefore, we can conclude that:
T(n) = O(n2 * log(n))
So, the solution to the recurrence relation T(n) = 4T(n/2) + n2 is T(n) = O(n2 * log(n)).