Directorate of Online Education

INTERNAL ASSIGNMENT

NAME Yogita Pralhad Deore

SESSION NOV-DEC 2023
PROGRAM MASTER OF COMPUTER APPLICATIONS (MCA)
SEMESTER III
ROLL NUMBER 2214501100
COURSE CODE & NAME DCA7104 - Analysis and Design of Algorithm
BATCH 04
 Set-I
Q1. Compare and contrast the stack space utilisation in recursive and non-recursive
algorithms by analysing a factorial function.
Ans. In computer science, the utilization of stack space can significantly differ between recursive and non-
recursive algorithms. Let's analyze the stack space utilization in both types of algorithms using the example
of a factorial function.

Recursive Factorial Algorithm:

Consider a recursive implementation of the factorial function in a programming language like Python:

def factorial_recursive(n):
if n == 0 or n == 1:
return 1
else:
return n * factorial_recursive(n - 1)

Stack Space Utilization:

 Each recursive call to factorial_recursive adds a new stack frame to the call stack.
 The stack frames are not released until the base case is reached, and the recursive calls start
returning.
 The depth of the call stack corresponds to the level of recursion.

Analysis:

 The recursive algorithm uses additional stack space proportional to the depth of recursion.
 The space complexity is O(n), where n is the input to the factorial function.
 Recursive algorithms may be susceptible to stack overflow if the recursion depth becomes too large.

Non-Recursive Factorial Algorithm:

Now, let's consider a non-recursive (iterative) implementation of the factorial function

def factorial_iterative(n):
result = 1
for i in range(1, n + 1):
result *= i
return result

Stack Space Utilization:

 The non-recursive algorithm does not rely on recursive calls and, therefore, does not create
additional stack frames.
 The space complexity is O(1) as the space required is constant regardless of the input size.

Analysis:

 The non-recursive algorithm is generally more memory-efficient compared to the recursive one.
 It is not prone to stack overflow issues associated with deep recursion.

Comparison:

.
Space Complexity:
.
 Recursive: O(n)
 Non-Recursive: O(1)
.
Stack Space Utilization:
.
 Recursive: Utilizes stack space proportional to the recursion depth.
 Non-Recursive: Does not use additional stack space.
.
Risk of Stack Overflow:
.
 Recursive: Risk of stack overflow for large input values due to the recursive call stack.
 Non-Recursive: Lower risk of stack overflow as it doesn't rely on recursion.
.
Readability and Simplicity:
.
 Recursive: Can be more intuitive and concise for certain algorithms but may sacrifice space
efficiency.
 Non-Recursive: May involve more explicit control flow but is often more memory-efficient.

Q.1 As the head of the IT department at the university library, you have been presented
with a challenge. The library's current book search system has been identified as
inefficient—especially during peak hours when student traffic is high, resulting in slow
search response times. Considering that the library's database of book titles is sorted,
propose a search algorithm to expedite search times.
Ans. Given that the library's database of book titles is sorted, an efficient search algorithm to
expedite search times is the Binary Search algorithm. Binary Search is a divide-and-conquer
algorithm that quickly locates a target value within a sorted collection by repeatedly dividing the
search interval in half.

Here's how Binary Search works

Initialization: Start with the entire sorted collection (in this case, the list of book titles).
.
Define Search Range: Identify the middle element of the current search range.

Compare with Target: Compare the middle element with the target value.
.
Adjust Search Range:
If the middle element is equal to the target, the search is successful.
If the target is less than the middle element, repeat the search on the left half of the collection.
If the target is greater than the middle element, repeat the search on the right half of the
collection.
.
Repeat: Repeat steps 2-4 until the target is found or the search range becomes empty.
.
Result: If the target is found, return its position in the collection; otherwise, indicate that the
target is not present.

Benefits of Binary Search:

Efficiency: Binary Search has a time complexity of O(log n), making it significantly faster than
linear search algorithms.

Optimal for Sorted Data: Since the library's database is already sorted, Binary Search is
particularly well-suited.

Integration into Library System:

 Replace the current search mechanism with Binary Search for book titles in the library's
database.
 Ensure that the database remains sorted for the algorithm to work effectively.
 Monitor and evaluate the search performance during peak hours to confirm improvements.
By implementing Binary Search, the library can significantly expedite search times, especially
during peak hours, leading to an improved and more efficient book search system fo
Ans. Performing BFS Traversal:
Start with vertex A: We'll visit A first as it's the starting point.

r students and library staff.

Q.2Traverse the following graph by Breadth First search and construct the
corresponding BFS tree. Start the traversal at vertex ‘a’ and name the
respective edges.
 Exploring A's Neighbors:

 Imagine you have a friend named A, and you want to visit their friends.
 You start with A and visit all friends directly connected to A, like B, C, and D.
 You prioritize visiting friends with shorter connections first, like B and C, before
going to D.

Continue Level by Level:

 Once you visit A's friends, you look at their friends.

 For B, you visit F. For C, you visit E and G. D has no more friends.
 You keep doing this level by level, exploring friends of friends.

Marking Visited Friends:

 As you visit each friend, you mark them as visited so you don't go back to the
same friend later.

Building the BFS Tree:

 Now, think of this process as making a tree. A is the starting point, the root of the
tree.
 Connect A to its visited friends (B, C, and D) because you visited them from A.
 Continue connecting friends to their friends, like B to F, and C to E and G.

Resulting BFS Tree:

/ \

B C

/ /\

F E G

This tree shows the connection between friends. A is the starting point, and you
connect friends level by level, just like you visited them.

Additional Notes:
 If friends have the same distance (connections of equal length), the order you
visit them might change.
 BFS makes sure to finish visiting all friends at a certain level before moving to the
next level.
 It's like exploring a social network, making sure you meet everyone at the same
level before moving on to the next group.

Q.3 Apply bottom-up dynamic programming technique for the

following instance of the knapsack problem with capacity M=5.
Item Weight Value
1 2 $ 12
2 1 $ 10
3 3 $ 20
4 2 $ 15

Ans. 1. What is the problem?

We have a backpack with a weight limit.

We also have a bunch of items with different weights and values.
The goal is to choose a combination of items to put in the backpack, maximizing
the total value, but without exceeding the weight limit.

2. How to solve it?

 Imagine a table where each cell represents a specific scenario of choosing items
and staying within the weight limit.
 We start filling in this table step by step.
 For each item and each possible backpack weight, we decide whether it's better
to include the item or not based on the total value we can get.
 We keep track of the best choices in the table.

3. How to fill the table?

 We go through each item and each possible backpack weight, considering if it's
better to include the item or not.
 We use the information from the previous row in the table to make these
decisions.
 The goal is to find the best value we can get for each combination of items and
weights.

4. How to find the answer?

 After filling the table, we start at the bottom right corner.
 We trace our steps backward, figuring out which items we included to get the
best value.
 We end up with the optimal combination of items that fit in the backpack and
give us the most value.

5. Example:

 If our backpack can carry a maximum weight of 5 units, and we have items with
weights and values, the solution might tell us to pick specific items (like item 1, 3, and 4)
to get the maximum total value, which is 35.

In simple terms, we're solving a problem of choosing items to put in a backpack to get
the most value without making it too heavy.


 Q.4 Solve the following Single Source Shortest path problem assuming a
suitable vertex and obtain its time efficiency.

Ans. 1. Getting Ready:

 Imagine you have a city (graph) with different places (vertices) and roads (edges)
connecting them, and you want to find the shortest path from one place (source) to all
others.
 You start by creating a list of visited places (set S), a list to remember distances
(dist), and a priority queue (Q) to keep track of unvisited places.

2. Step by Step Journey:

 While there are still places to visit in the priority queue (Q):
 Pick the place (vertex) that is currently the closest to the source from the priority
queue.
 Mark it as visited.
 For each unvisited neighbor of that place:
 Calculate the distance from the source to that neighbor through the
currently visited place.
 If this new distance is shorter than the previously known distance to the
neighbor:
 Update the distance to the shorter one.
 If the neighbor is already in the priority queue, update its priority.
 If not, add it to the priority queue.

3. Finding Shortest Paths:

 After visiting all places, you have the shortest paths from the source to every
other place in the list called 'dist.'

4. Time Management:

 The time it takes to do this depends on the number of places (vertices) and roads
(edges) in the city.
 For this algorithm, it's effective when there are fewer roads compared to places.

For the Provided Graph:

 Apply these steps to find the shortest paths from a starting place (vertex a) to all
other places in the graph.
 The complexity of this process depends on how many places and roads are in the
graph.

In simple terms, Dijkstra's algorithm is like finding the best route through a city,
keeping track of distances and updating as you discover shorter paths. It works well
when there aren't too many roads to check.

. Explain the concept of backtracking and discuss its application in

solving the N- Queens puzzle. Outline the steps and provide the
pseudocode for the algorithm.

Ans.Concept of Backtracking: Backtracking is like a trial-and-error method for

problem-solving. It explores different possibilities to find a solution and goes back
("backtracks") if a certain path doesn't lead to the solution. It's like trying different
paths in a maze and backtracking when you hit a dead end.

Application in N-Queens Puzzle: The N-Queens puzzle is about placing N queens on

an N×N chessboard in such a way that no two queens threaten each other.
Backtracking is a great fit because it allows us to explore different queen placements
and go back when we find a conflict, trying other possibilities.

Steps for N-Queens with Backtracking:

.
Start in the leftmost column:
.
 Begin in the first column and move one column at a time.
.
Place a queen in a safe spot:
.
 Try placing a queen in the current column in a row where it won't conflict
with any previously placed queens.
.
Move to the next column:
.
 Move to the next column and repeat steps 2 and 3.
.
Backtrack if needed:
.
  If placing a queen in the current column leads to a conflict, go back to the
previous column and try a different row.
.
Repeat until solution found or all possibilities explored:
.
 Keep going back and trying different placements until a solution is found
or all possibilities are explored.

Pseudocode for N-Queens with Backtracking:

function solveNQueens(board, column):

if all queens are placed:

print(board) // Found a solution

return

for each row in the current column:

if the queen can be placed in this row:

place queen in this row

solveNQueens(board, column + 1) // Move to the next column

remove queen from this row // Backtrack if needed

This pseudocode outlines the basic steps of the N-Queens problem using backtracking.
It places queens one by one in different columns, making sure they don't threaten each
other. If a conflict is encountered, it backtracks to try a different path. This process
continues until a solution is found or all possibilities are explored.