Scribd
Upload
3 views3 pages

Practical Set

The document contains a series of questions related to algorithms and data structures, including matrix multiplication, sorting algorithms, the Travelling Salesman Problem, the 0/1 Knapsack Problem, Huffman Trees, string matching algorithms, and various dynamic programming problems. Each question requires justification, algorithm implementation, or explanation of concepts and their time complexities. The document serves as an examination or assignment covering a wide range of algorithmic topics.

Uploaded by

me.rajchaurasiya327
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views3 pages

Practical Set

The document contains a series of questions related to algorithms and data structures, including matrix multiplication, sorting algorithms, the Travelling Salesman Problem, the 0/1 Knapsack Problem, Huffman Trees, string matching algorithms, and various dynamic programming problems. Each question requires justification, algorithm implementation, or explanation of concepts and their time complexities. The document serves as an examination or assignment covering a wide range of algorithmic topics.

Uploaded by

me.rajchaurasiya327
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Q1.

Justify that Strassen’s Matrix Multiplication is better than Normal Matrix​


Multiplication in terms of Time Complexity. Write the Divide and Conquer​
algorithm/code for Strassen’s Matrix Multiplication.

[Link] the Quick Sort algorithm to sort the following numbers. Show all​
partitioning steps.

10, 5, 20, 2, 17, 3, 15

[Link] the Merge Sort algorithm to sort the following numbers. Show all​
splitting and merging steps.

9, 5, 12, 2, 7, 3, 11, 6

[Link] the Heap Sort algorithm to sort the following numbers. Construct the​
heap and show all intermediate steps.

10, 5, 20, 2, 17, 3, 15

[Link] the Travelling Salesman Problem (TSP). Solve the given TSP using​
the Brute Force approach and determine the minimum cost tour.

[Link] the 0/1 Knapsack Problem. Solve the given Knapsack problem using​
the Brute Force approach.

Items:​
Weight = {1, 3, 4, 5}​
Profit = {10, 40, 50, 70}​
Capacity = 8

[Link] the construction of a Huffman Tree. Construct the Huffman Tree for​
the following frequencies and write the Huffman code for each symbol.

A = 5, B = 9, C = 12, D = 13, E = 16, F = 45


[Link] 1143: Longest Common Subsequence (LCS)

Write the Dynamic Programming recurrence relation and state the time​
complexity.

[Link] the Dynamic Programming algorithm for the 0/1 Knapsack Problem and​
solve the following instance.

Items:​
Weight = {1, 3, 4, 5}​
Profit = {10, 40, 50, 70}​
Capacity = 8

[Link] the Subset Sum Problem for the set:

{3, 5, 2, 7}

Target Sum = 10

[Link] an algorithm/function for String Matching using the Naïve Approach.​


State its time complexity.

[Link] the Rabin-Karp algorithm/function for String Matching and state its​
time complexity.

[Link] the KMP (Knuth-Morris-Pratt) algorithm/function for String Matching.​


Explain the role of the LPS array.

[Link] 746: Min Cost Climbing Stairs

Write the DP recurrence relation and time complexity.


[Link] 62: Unique Paths

Write the DP recurrence relation and time complexity.

[Link] 63: Unique Paths II

Write the DP recurrence relation and explain how obstacles are handled.

[Link] 64: Minimum Path Sum

Write the DP recurrence relation and time complexity.

[Link] 120: Triangle

Write the DP recurrence relation and time complexity.

[Link] 516: Longest Palindromic Subsequence

Explain how it can be solved using LCS.

[Link] Common Substring

Write the DP recurrence relation and state the time complexity.

[Link] 1312: Minimum Insertions to Make a String Palindrome

Write the formula used to solve the problem using LPS.

[Link] 583: Delete Operation for Two Strings

Write the formula using LCS and state the time complexity.

You might also like