Assignment 1.
Time Complexity
1. Identify the time complexity: Given the following code snippet, determine its time complexity:
for i in range(n):
for j in range(n):
print(i, j)
Explain the process you used to arrive at your answer.
2. Explain time complexity analysis: Given the function below, analyze and explain each term contributing to the
overall time complexity:
def example_function(n):
for i in range(n):
print(i)
for j in range(n * n):
print(j)
Identify and explain the dominant term in the time complexity.
3. Discuss space complexity of recursion: Consider a recursive function that calculates the factorial of n. Explain
the space complexity of the function in terms of the stack space used during recursive calls. Show the space
used for n = 5.
4. Apply Big-O notation: Analyze the following function and express its time complexity using Big-O notation:
def example_function(n):
i=1
while i < n:
print(i)
i *= 2
Calculate the number of iterations if n = 64.
5. Calculate the space complexity of a data structure: Given an array of n elements, where each element is an
integer, calculate the space complexity of storing this array. Additionally, if the array is converted into a linked
list, calculate the total space complexity considering both node storage and pointer storage. Use specific
numerical values, like n = 1000 and each integer taking 4 bytes.
6. Analyze the efficiency of different sorting algorithms: Compare the time complexities of Bubble Sort, Merge
Sort, and Quick Sort for an array of size n = 1000. Calculate the expected number of comparisons for each sort
in the best, average, and worst cases.
7. Examine the time complexity of a recursive function: Given the recursive function below, determine its time
complexity and analyze how many calls are made if n = 5:
def recursive_function(n):
if n <= 1:
return 1
return recursive_function(n - 1) + recursive_function(n - 1)
Provide an explanation of the exponential growth pattern.
8. Evaluate iterative vs recursive solutions: Consider the Fibonacci sequence. Calculate the time complexity for
both an iterative and a recursive solution to compute the nth Fibonacci number. For n = 30, estimate the number
of operations each solution performs and discuss which approach is more efficient.
9. Assess space complexity in different data structures: Given an array-based implementation and a linked-list-
based implementation of a stack, evaluate the space complexity for each when holding n = 100 elements.
Assume each integer is 4 bytes, and in the linked list, each pointer is also 4 bytes. Discuss the trade-offs in
memory usage between the two implementations.
10. Design an algorithm and analyze its complexity: Design an algorithm to search for a specific element in a
sorted 2D matrix where each row and column is sorted in ascending order. Write pseudocode, implement the
algorithm for a 5x5 matrix, and analyze its time and space complexity.
Assignment 2. Recursive functions
1. Define the recurrence relation: For the recursive function below, write the recurrence relation that
represents its time complexity.
def example_function(n):
if n <= 1:
return 1
else:
return example_function(n - 1) + example_function(n - 1)
Explain your reasoning for each term in the recurrence relation.
2. Explain the recurrence relation for binary search: Given a binary search algorithm on an array of size n,
derive and explain the recurrence relation for its time complexity. Show each step in your derivation.
3. Interpret the Master Theorem in relation to recurrence relations: Consider the recurrence relation T(n) =
2T(n/2) + n. Using the Master Theorem, explain the process of determining the time complexity and provide the
final Big-O result.
4. Solve a recurrence relation using iteration: Given the recurrence relation T(n) = 3T(n/2) + n, use the
iteration method to expand and simplify the recurrence. Calculate the time complexity in Big-O notation for n =
16.
5. Apply the Master Theorem: Use the Master Theorem to solve the recurrence relation T(n) = 4T(n/2) +
n^2. Determine the time complexity and verify your solution by calculating T(n) for n = 16.
6. Analyze time complexity with recursion tree: For the recurrence relation T(n) = T(n/2) + n, draw a
recursion tree to represent the calls made. Analyze the total work done at each level and derive the overall time
complexity using the tree.
7. Compare recursive and iterative complexities: Given the recurrence relation for Merge Sort, T(n) =
2T(n/2) + n, and an iterative sorting algorithm with O(n log n) complexity, analyze both approaches for an input
size of n = 1024. Discuss the efficiency of each method in terms of time complexity.
8. Evaluate the effect of a constant in a recurrence relation: Given T(n) = 3T(n/2) + 100, evaluate how the
constant term 100 affects the asymptotic time complexity. Calculate T(n) for n = 32 and discuss whether the
constant impacts the overall growth rate.
9. Assess space complexity in recursive algorithms: For the recursive algorithm with recurrence T(n) = T(n
- 1) + O(1), analyze both the time and space complexity. If n = 10, calculate the space required for the recursion
stack and evaluate how it scales with increasing n.
10. Design a recurrence relation for a divide-and-conquer algorithm: Consider a problem that divides the
input n into 3 subproblems of size n/3, with each division step taking O(n) time. Write a recurrence relation for
this algorithm, solve it using the Master Theorem, and verify the time complexity by expanding the recurrence
for n = 27.
Assignment 3. Divide and Conquer
1. Compute the result of a Binary Search: Given a sorted array [2, 5, 8, 12, 16, 23, 38, 56, 72, 91], perform a
binary search to find the element 23. Show each step in the search process.
2. Trace Merge Sort steps: Given the array [38, 27, 43, 3, 9, 82, 10], demonstrate how the Merge Sort algorithm
would sort this array. Show each division and merging step.
3. Explain Quick Sort partitioning: Given an array [12, 7, 14, 9, 10, 11] and choosing 10 as the pivot, show how
Quick Sort will partition the array around this pivot. Illustrate each swap and final partitioned array.
4. Apply Divide and Conquer to find the minimum and maximum: Use a Divide and Conquer approach to find
the minimum and maximum of the array [18, 52, 43, 17, 24, 19, 8, 56]. Show each step of the division and
combination process.
5. Implement Karatsuba’s algorithm: Multiply two large numbers, 1234 and 5678, using Karatsuba’s Divide and
Conquer multiplication method. Show each recursive step.
6. Analyze the steps of Strassen’s Matrix Multiplication: Given two 2x2 matrices. Multiply two sample matrix
using St rassen’s method and detail each step of the calculation.
7. Examine Closest Pair of Points: Given a set of points [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)], apply
the Divide and Conquer method to find the closest pair of points. Show the steps of splitting, recursion, and
combining.
8. Evaluate Binary Search efficiency: Calculate the number of comparisons made by Binary Search on a sorted
array of size 1024 to find a target element in the worst case. Compare this with the number of comparisons in a
linear search.
9. Assess time complexity of Merge Sort: Given an array of size 1024, compute the exact number of
comparisons Merge Sort will perform. Analyze whether this matches the expected O(n log n) complexity and
discuss any discrepancies.
10. Design an algorithm using Divide and Conquer to solve a modified problem: Given a large array of n integers
where n is a power of 2, create an algorithm to find the sum of all even numbers using Divide and Conquer.
Implement this in pseudocode, then solve it numerically for the array [4, 7, 2, 9, 8, 3, 6, 5]. Show each division
and summing step.
Assignment 4. Greedy Technique
1. Identify the steps in a Greedy approach for Activity Selection: Given a set of activities with their start and end
times [(1, 3), (2, 5), (4, 6), (6, 8), (5, 9), (8, 9)], select the maximum number of non-overlapping activities. Show
each step in your selection process.
2. Explain the Greedy Choice Property in Huffman Coding: Given characters with frequencies [(A, 5), (B, 9), (C,
12), (D, 13), (E, 16), (F, 45)], explain how the greedy method is used in creating the Huffman Tree for optimal
encoding. Illustrate the steps and show the final tree.
3. Trace the Fractional Knapsack problem: Given items with weights [10, 20, 30] and values [60, 100, 120], and
a knapsack capacity of 50, apply the Greedy approach to determine the maximum value that can be obtained.
Show each step in selecting items or fractions of items.
4. Implement Prim’s algorithm for Minimum Spanning Tree: Given the weighted graph with vertices A, B, C, D
and edges with weights as follows:
• (A, B) = 1
• (A, C) = 3
• (B, C) = 3
• (B, D) = 6
• (C, D) = 4
Use Prim’s Greedy algorithm to find the MST, starting from vertex A. Show each step and the selected edges.
5. Solve a Coin Change problem using a Greedy approach: For a currency system with denominations [1, 5,
10, 25, 100], find the minimum number of coins required to make 99 units. Show each coin selection and explain
the Greedy approach in this context.
6. Analyze the optimal solution for Job Sequencing: Given jobs with deadlines and profits [(Job1, 2, 100), (Job2,
1, 19), (Job3, 2, 27), (Job4, 1, 25), (Job5, 3, 15)], find the sequence of jobs that maximizes profit within their
deadlines using a Greedy approach. Show each selection step and explain how Greedy ensures maximum profit.
7. Examine the correctness of Dijkstra’s algorithm: For the weighted graph below, apply Dijkstra’s algorithm
starting from vertex A to find the shortest paths to all other vertices:
• (A, B) = 4
• (A, C) = 2
• (B, C) = 5
• (B, D) = 10
• (C, E) = 3
• (D, E) = 4
Show each step and analyze why Greedy works correctly in this case.
8. Evaluate Greedy’s solution for the Minimum Number of Platforms problem: Given train arrival and departure
times [(10:00, 10:30), (10:15, 10:45), (10:20, 11:00), (10:40, 11:10)], find the minimum number of platforms
required using a Greedy approach. Discuss if this Greedy approach yields an optimal solution and any limitations
it may have.
9. Assess the efficiency of Kruskal’s algorithm for Minimum Spanning Tree: Given a graph with vertices A, B, C,
D, E and weighted edges:
• (A, B) = 1
• (A, C) = 7
• (B, C) = 5
• (B, D) = 4
• (C, E) = 3
• (D, E) = 2
Use Kruskal’s algorithm to find the MST. Analyze the time complexity and discuss why Greedy leads to an
optimal solution.
10. Design an algorithm using a Greedy approach for a custom scheduling problem: Given a set of jobs with
durations and profits [(Job1, 2, 40), (Job2, 1, 30), (Job3, 2, 60), (Job4, 3, 20)], and a maximum allowed time of
4, create a Greedy algorithm to select jobs that maximize profit within the time limit. Implement this algorithm
and solve it for the given jobs, showing each step of your process and justifying your choices.
Assignment 5. Dynamic programming
1. Define the steps in the Fibonacci Sequence using Dynamic Programming: Using Dynamic Programming,
compute the 10th Fibonacci number. Show each step of the memoization or tabulation process.
2. Explain the Dynamic Programming approach to the Knapsack Problem: Given items with weights [2, 3, 4, 5]
and values [3, 4, 5, 6] and a knapsack capacity of 5, explain how Dynamic Programming solves this problem.
Show each subproblem solved and fill in a DP table for clarity.
3. Trace the steps in the Longest Common Subsequence (LCS): For the sequences X = "ABCBDAB" and Y =
"BDCAB", demonstrate the steps to find the LCS using Dynamic Programming. Show the matrix as it is filled and
explain the decision process at each cell.
4. Implement the Coin Change problem: Given coins of denominations [1, 2, 5] and a target amount of 11, use
Dynamic Programming to find the minimum number of coins needed. Show each step of building the DP array
and explain your result.
5. Apply Dynamic Programming to solve the Edit Distance problem: Given the words "sunday" and "saturday",
use Dynamic Programming to calculate the minimum edit distance. Show each cell in the DP table and describe
how the final answer is obtained.
6. Analyze the DP approach to the Rod Cutting problem: Given a rod of length 8 and prices for each length [1,
5, 8, 9, 10, 17, 17, 20], use Dynamic Programming to determine the maximum obtainable profit. Show each
subproblem solved and analyze the time complexity of your solution.
7. Examine the 0/1 Knapsack problem’s efficiency: Given items with weights [1, 2, 3, 8] and values [10, 15, 40,
50] and a knapsack capacity of 5, solve the problem using Dynamic Programming. Compare this approach’s
efficiency to a brute-force solution in terms of time complexity.
8. Evaluate the results of the Matrix Chain Multiplication: For matrices with dimensions [10, 20, 30, 40, 30], use
Dynamic Programming to find the minimum number of scalar multiplications required to multiply these matrices.
Show each step of building the DP table and discuss the benefits of the DP approach over a recursive solution.
9. Assess the optimality of Dynamic Programming in the Longest Increasing Subsequence: Given an array [10,
22, 9, 33, 21, 50, 41, 60, 80], use Dynamic Programming to find the length of the longest increasing
subsequence. Evaluate the performance and accuracy of the solution compared to a greedy approach.
10. Design a Dynamic Programming algorithm for a custom scheduling problem: Given a list of projects with
start times, end times, and profits [(1, 3, 50), (2, 5, 20), (4, 6, 70), (6, 7, 30), (5, 8, 80)], create a Dynamic
Programming algorithm to select projects that maximize profit without overlapping. Implement this algorithm for
the given projects, showing each step and explaining the DP table construction.
Assignment 6. Backtracking and Branch-and-Bound techniques
1. Explain the backtracking approach to the N-Queens problem: Using backtracking, place 4 queens on a 4x4
chessboard so that no two queens threaten each other. Show each step of the placement and backtracking
process.
2. Illustrate solving a subset-sum problem with backtracking: Given a set of numbers {3, 34, 4, 12, 5, 2} and a
target sum of 9, use backtracking to determine if there is a subset that sums to 9. Show each recursive call and
explain each decision to include or exclude an element.
3. Explain the Branch-and-Bound approach for solving the Knapsack problem: Given items with weights [2, 3,
4] and values [3, 4, 5], and a knapsack capacity of 5, describe how Branch-and-Bound finds the maximum value.
Show each node’s bounding value and decision path in the search tree.
4. Use backtracking to solve the Hamiltonian Cycle problem: Given a graph with vertices {A, B, C, D} and edges
{(A, B), (B, C), (C, D), (D, A), (A, C)}, determine if there is a Hamiltonian cycle. Show each recursive call and
path explored.
5. Apply Branch-and-Bound to solve the Traveling Salesman Problem (TSP): Given cities and their pairwise
distances represented as:

Use Branch-and-Bound to find the minimum cost tour starting from city 0. Show each bounding step and node
evaluation.
6. Analyze the efficiency of solving Sudoku with backtracking: For a partially filled Sudoku grid, use backtracking
to solve the puzzle. Show each recursive attempt and backtrack step. Analyze the time complexity and discuss
why backtracking is effective for Sudoku.
7. Compare backtracking with Branch-and-Bound for solving the Knapsack problem: Given items with weights
[10, 20, 30] and values [60, 100, 120] and a knapsack capacity of 50, solve the problem using both backtracking
and Branch-and-Bound. Compare the number of nodes explored and explain the differences in their efficiency.
8. Evaluate the effectiveness of Branch-and-Bound for job scheduling: Given jobs with deadlines and profits
[(Job1, 2, 50), (Job2, 1, 20), (Job3, 2, 40), (Job4, 1, 30)], use Branch-and-Bound to maximize profit. Show each
bounding step and explain why this approach may be better or worse than a Greedy approach for job scheduling.
9. Assess the performance of backtracking in the subset-sum problem: Given a set {1, 2, 3, 7, 8, 10} and a
target sum of 11, use backtracking to find all subsets that sum to 11. Evaluate the number of recursive calls
needed and discuss the feasibility of using backtracking for large sets.
10. Design a backtracking solution for a custom constraint satisfaction problem: Create a solution for the Magic
Square problem for a 3x3 grid, where the sum of each row, column, and diagonal is the same. Using
backtracking, fill the grid with numbers 1 to 9 to form a magic square. Show each attempt, backtracking step,
and the final solution. Explain your approach and the challenges faced with backtracking for this constraint
problem.
Assignment 7. P, NP, NP-Complete, and NP-Hard problems
1. Define the classes P, NP, NP-Complete, and NP-Hard: Write definitions for each class, providing at least one
example for each. Explain the differences between these classes in terms of time complexity and problem-
solving approaches.
2. Explain the concept of polynomial time: Describe what it means for an algorithm to run in polynomial time.
Given the functions O(n^2), O(n!), and O(2^n), identify which functions represent polynomial, exponential, and
factorial time, respectively, and classify them in terms of P and NP.
3. Discuss the significance of the P vs. NP problem: Explain why determining if P = NP is one of the most
important unsolved questions in computer science. Discuss potential real-world implications if P were proven to
equal NP.
4. Classify problems as P, NP, or NP-Hard: Given the problems below, determine if each belongs to P, NP, or
NP-Hard:
• Sorting a list of numbers
• Solving the Sudoku puzzle
• Finding the shortest path in a weighted graph
• Traveling Salesman Problem (TSP)
• Knapsack Problem
Provide justifications for each classification.
5. Demonstrate reductions between problems: Show how the Subset-Sum problem can be reduced to the
Knapsack problem, explaining the steps of the reduction. Discuss what this reduction implies about the
complexity of these problems.
6. Analyze why the SAT problem is NP-Complete: Describe the satisfiability (SAT) problem and explain the
process by which SAT was proven to be NP-Complete. Analyze why many other problems can be reduced to
SAT.
7. Compare P, NP, and NP-Complete problems: Given the problems below, identify which ones are in P, which
are in NP, and which are NP-Complete:
• Graph coloring
• Hamiltonian Cycle
• Matrix multiplication
• Integer factorization
Justify your classifications and explain the characteristics that distinguish each category.
8. Evaluate the feasibility of solving NP-Complete problems: Given an NP-Complete problem like the Traveling
Salesman Problem, discuss why brute-force approaches are impractical for large instances. Explain heuristic
and approximation algorithms and evaluate their usefulness for solving NP-Complete problems in practice.
9. Assess the impact of NP-Hard problems on industry: Select an NP-Hard problem such as the Vehicle Routing
Problem or Job Scheduling, and discuss its importance in a specific industry (e.g., logistics, manufacturing).
Evaluate the effectiveness of current methods (heuristics, approximations) used in industry to address this
problem.
10. Design an algorithmic approach for an NP-Hard problem: Choose an NP-Hard problem, such as the 3-SAT
or Knapsack problem, and create an approach using heuristics, approximation algorithms, or dynamic
programming (if applicable). Describe each step of your approach, implement it for a small test case, and discuss
its limitations in terms of time complexity and accuracy.