MCA Assignments 2025: Sem-I (MCS-211 to MCSL-217)

Podcast

Play an AI-generated podcast conversation about this lesson

Download our mobile app to listen on the go

Get App

Questions and Answers

Design and develop an efficient algorithm to find the list of prime numbers in the range 501 to 2000. What is the complexity of this algorithm?

An efficient algorithm would be the Sieve of Eratosthenes, adapted for a range. The complexity is approximately O(n log log n) where n is the size of the range.

Differentiate between Cubic-time and Factorial-time algorithms. Give example of one algorithm each for these two running times.

Cubic-time algorithm: O(n^3), e.g., matrix multiplication. Factorial-time algorithm: O(n!), e.g., generating all permutations of a set.

Write an algorithm to multiply two square matrices of order n*n. Also explain the time complexity of this algorithm.

Algorithm: Standard matrix multiplication using nested loops. Time complexity: O(n^3).

What are asymptotic bounds for analysis of efficiency of algorithms? Why are asymptotic bounds used? What are their shortcomings? Explain the Big O and Big Ω notation with the help of a diagram. Find the Big O-notation and Ω-notation for the function: $f(n)= 100n^4 +1000n^3 +100000$

Asymptotic bounds are O, Ω, Θ, o, ω. They are used to describe the growth rate of algorithms, ignoring constant factors and lower-order terms. Shortcomings: they don't reflect actual performance for small input sizes. Big O: upper bound, Big Ω: lower bound. Big O notation: O(n^4), Big Omega notation: Ω(n^4) Signup and view all the answers

Write and explain the Left to Right binary exponentiation algorithm. Demonstrate the use of this algorithm to compute the value of 3^29 (Show the steps of computation). Explain the worst-case complexity of this algorithm.

Algorithm: Repeated squaring and multiplication based on binary representation of the exponent. 3^29 = 3^(11101) = 3^1 * 3^4 * 3^8 * 3^16. Compute each power of 2 and multiply. Worst-case complexity: O(log n) Signup and view all the answers

Write and explain the Bubble sort algorithm. Discuss its best and worst-case time complexity.

Algorithm: Repeatedly compare adjacent elements and swap if they are in the wrong order. Best-case complexity: O(n). Worst-case complexity: O(n^2). Signup and view all the answers

What are the uses of recurrence relations? Solve the following recurrence relations using the Master's method a. $T(n) = 4T(\frac{n}{4}) + n^1$ b. $T(n) = 4T(\frac{n}{3}) + n^1$

Uses of recurrence relations: analyzing the time complexity of recursive algorithms. a. T(n) = Θ(n log n). b. T(n) = Θ(n^(log3 4)) Signup and view all the answers

What is an Optimisation Problem? Explain with the help of an example. When would you use a Greedy Approach to solve optimisation problem? Formulate the Task Scheduling Problem as an optimisation problem and write a greedy algorithm to solve this problem. Also, solve the following fractional Knapsack problem using greedy approach. Show all the steps. Suppose there is a knapsack of capacity 20 Kg and the following 6 items are to packed in it. The weight and profit of the items are as under: (P1, P2,..., P6) = (30,16,18,20,10, 7) (W1, W2,..., W6) = (5, 4, 6, 4, 5, 7) Select a subset of the items that maximises the profit while keeping the total weight below or equal to the given capacity.

Optimization problem: finding the best solution from all feasible solutions. Example: Knapsack problem. Greedy approach is suitable when optimal substructure and greedy choice property hold. Fractional Knapsack Solution: Calculate profit/weight ratio for each item. Sort in descending order of this ratio. Add items to knapsack until full. Solution for given data: Take item 1 (5kg, profit 30), item 2 (4kg, profit 16), item 4 (4kg, profit 20), and 7/6 of item 3 (7/6 * 6kg =7kg, 7/6 * 18 = 21). Total weight = 5+4+4+7=20, total profit = 30+16+20+21 = 87. Signup and view all the answers

Assuming that data to be transmitted consists of only characters 'a' to 'g', design the Huffman code for the following frequencies of character data. Show all the steps of building a huffman tree. Also, show how a coded sequence using Huffman code can be decoded. a:5, b:25, c:10, d:15, e:8, f:7, g:30

Huffman code: Build Huffman tree based on frequencies. a:11110, b:01, c:1110, d:10, e:11111, f:110, g:00. Decoding example: follow the tree based on the bit sequence. Signup and view all the answers

Explain the Merge procedure of the Merge Sort algorithm. Demonstrate the use of recursive Merge sort algorithm for sorting the following data of size 8: [19, 18, 16, 12, 11, 10, 9, 8]. Compute the complexity of Merge Sort algorithm.

Merge procedure: Combine two sorted subarrays into one sorted array. Merge Sort: Divide and conquer approach, recursively divides the array into two halves, sorts each half, and then merges the sorted halves. Time complexity: O(n log n). Sorted array for given data: [8, 9, 10, 11, 12, 16, 18, 19] Signup and view all the answers

Explain the divide and conquer approach of multiplying two large integers. Compute the time complexity of this approach. Also, explain the binary search algorithm and find its time complexity.

Divide and conquer for multiplying large integers (e.g., Karatsuba algorithm): Divide integers into smaller parts, recursively multiply parts, and combine results. Time complexity: O(n^(log2 3)). Binary search: Repeatedly divide the search interval in half. Time complexity: O(log n). Signup and view all the answers

Explain the Topological sorting with the help of an example. Also, explain the algorithm of finding strongly connected components in a directed Graph.

Topological sorting: Linear ordering of vertices in a DAG such that for every directed edge from vertex u to vertex v, vertex u comes before vertex v in the ordering. Algorithm: DFS-based approach. Algorithm for strongly connected components: Kosaraju's algorithm or Tarjan's algorithm. Signup and view all the answers

Write the Prim's algorithm to find the minimum cost spanning tree of a graph. Also, find the time complexity of Prim's algorithm. Demonstrate the use of Kruskal's algorithm and Prim's algorithm to find the minimum cost spanning tree for the Graph given in Figure 1. Show all the steps.

Prim's algorithm: Start with a single vertex and repeatedly add the nearest adjacent vertex with the minimum weight until all vertices are included. Time complexity: O(E log V) using binary heap. Kruskal's Algorithm: MST = { (A,B), (D,F), (D,G), (F,E), (D,E), (A,E) }. Prim's Algorithm: MST = { (A,B), (A,E), (D,F), (F,G), (E,F), (D,E) }. Signup and view all the answers

Write the Dijkstra's shortest path algorithm. Also, find the time complexity of this shortest path algorithm. Find the shortest paths from the vertex 'A' using Dijkstra's shortest path algorithm for the graph given in Figure 1. Show all the steps of computation.

Dijkstra's algorithm: Start at the source node and repeatedly select the nearest vertex with the smallest cumulative distance. Time complexity: O(E + V log V) using a priority queue. Shortest paths from A: {A->B: 10, A->C: 14, A->D: 14, A->E: 15, A->F: 21, A->G: 22}. Signup and view all the answers

Explain the algorithm to find the optimal Binary Search Tree. Demonstrate this algorithm to find the Optimal Binary Search Tree for the following probability data (where $p_i$ represents the probability that the search will be for the key node $k_i$, whereas $q_i$ represents that the search is for dummy node $d_i$. Make suitable assumptions, if any)

Algorithm: Dynamic programming approach to minimize the expected search cost. Computed using the given probability data and dummy nodes' probabilities. Requires calculating the cost for all possible subtrees and choosing the optimal one. Signup and view all the answers

Given the following sequence of chain multiplication of the matrices. Find the optimal way of multiplying these matrices:

Matrix A1: 10 × 15

Matrix A2: 15 × 5

Matrix A3: 5 × 20

Matrix A4: 20 × 10

Optimal way: (A1 x (A2 x A3)) x A4. Signup and view all the answers

Explain the Rabin Karp algorithm for string matching with the help of an example. Find the time complexity of this algorithm.

Rabin-Karp algorithm: Uses hashing to find matches. Time complexity: O(n+m) on average, O(nm) in worst case. Signup and view all the answers

Explain the term Decision problem with the help of an example. Define the following problems and identify if they are decision problem or optimisation problem? Give reasons in support of your answer. (i) Travelling Salesman Problem (ii) Graph Colouring Problem (iii) 0-1 Knapsack Problem

Decision problem: problem with a yes/no answer. TSP (optimisation and decision), Graph Colouring (optimisation and decision), 0-1 Knapsack (optimisation and decision). Signup and view all the answers

What are P and NP class of Problems? Explain each class with the help of at least two examples.

P: Problems solvable in polynomial time (e.g., sorting, searching). NP: Problems verifiable in polynomial time (e.g., subset sum, Hamiltonian cycle). Signup and view all the answers

Define the NP-Hard and NP-Complete problem. How are they different from each other. Explain the use of polynomial time reduction with the help of an example.

NP-Hard: At least as hard as the hardest problems in NP. NP-Complete: Both in NP and NP-Hard. Polynomial time reduction: Transforming one problem into another in polynomial time to prove its complexity (e.g., reducing SAT to 3-SAT). Signup and view all the answers

Define the following Problems: (i) SAT Problem (ii) Clique problem (iii) Hamiltonian Cycle Problem (iv) Subset Sum Problem

SAT: Determining whether a Boolean formula is satisfiable. Clique: Finding a complete subgraph of a certain size. Hamiltonian Cycle: Finding a cycle that visits each vertex exactly once. Subset Sum: Finding a subset of numbers that sum to a target value. Signup and view all the answers

Flashcards

Prime Number Algorithm

Finding prime numbers within a range using an algorithm and determining the algorithm's complexity.

Cubic-time vs. Factorial-time

Algorithms with time complexities that are cubic (n^3) and factorial (n!). Cubic is polynomial, Factorial is exponential.

Binary Exponentiation Algorithm

Algorithm to exponentiate a number using the binary representation of the exponent. It reduces computations.

Bubble Sort Algorithm

Simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order.