Algorithms Lab Subcode: B22EF0305

Project Report:

School of Computing Science and Engineering

Academic Year:2023-
Course Code: B22EF0303 Algorithms Lab Project Report 2024
Semester& Batch:4th
&A2
Project Details:
Project Title: DYNAMIC PROGRAMMING

Place of Project: REVA UNIVERSITY, BENGALURU

Student Details:

Name: C.Harshavardhanreddy Sign:

Mobile No: 9014467153

Email-ID: 22020134504@reva.edu.in

SRN: R22EF043

Guide and Lab Faculty Members

Details
GuideName: Prof.Thirumagal E Sign:
(The FacultyMember Date:
Assigned)
Grade by Guide:
Name of Lab Co- Faculty 1 Dr.Prabhuraj Sign:
Date:
Name of Lab Co- Faculty 2 Prof.Asha K Sign:
Date:
GradebyLabFacultyMembers
(combined)
SEE Examiners
Name of Sign:
Examiner 1: Date:
Name of Sign:
Examiner2: Date:

School of Computer Science and Engineering Page 1

 Algorithms Lab Subcode: B22EF0305

Contents
1.Abstract Pg no 4
2.Introduction Pg no 5

3.Problem Statement. Pg no 6

4.Project overview. Pg no 7

4. 1.Objectives Pg no 7

4.2.Goals Pg no 8

5. Implementation. Pg no 9-14

5. 1.Problem analysis and description. Pg no 8

5.2.Modules identified. Pg no 9

5.3.Code with comments. Pg no 10-14

6.Output and results Pg no 15-16

7.Conclusions Pg no 18

8. References Pg no 19

1. Abstract:
This paper presents an in-depth study of three classic dynamic programming problems: the 0/1

School of Computer Science and Engineering Page 2

 Algorithms Lab Subcode: B22EF0305

Knapsack Problem, the Longest Common Subsequence (LCS) Problem, and the Matrix Chain
Multiplication Problem. Dynamic programming is a powerful algorithmic technique used to solve
problems by breaking them down into simpler subproblems and storing the solutions to these
subproblems to avoid redundant computations. The 0/1 Knapsack Problem involves selecting items with
given weights and values to maximize the total value without exceeding a weight limit. The Longest
Common Subsequence Problem seeks to find the longest sequence that can be derived from two given
sequences without reordering the elements. The Matrix Chain Multiplication Problem focuses on
determining the most efficient way to multiply a chain of matrices by fully parenthesizing the product to
minimize the number of scalar multiplications. Through rigorous analysis and implementation, this
paper elucidates the methodology and significance of dynamic programming in optimizing these
problems. The results underscore the efficiency and effectiveness of dynamic programming techniques
in solving complex optimization problems, highlighting their importance in various computational
applications. Conclusively, the study demonstrates that dynamic programming not only enhances
problem-solving strategies but also significantly improves computational performance in relevant fields.

Keywords:-

1. Dynamic Programming
2. 0/1 Knapsack Problem
3. Longest Common Subsequence (LCS)
4. Matrix Chain Multiplication
5. Optimization
6. Subproblems
7. Algorithmic Technique
8. Computational Performance
9. Efficiency
10. Effectiveness

School of Computer Science and Engineering Page 3

 Algorithms Lab Subcode: B22EF0305

2. Introduction:
Dynamic programming is a fundamental algorithmic paradigm that has revolutionized the way complex
optimization problems are approached in computer science. This project delves into three quintessential
problems that exemplify the power and versatility of dynamic programming: the 0/1 Knapsack Problem,
the Longest Common Subsequence (LCS) Problem, and the Matrix Chain Multiplication Problem. Each
of these problems presents unique challenges and requires meticulous strategies to achieve optimal
solutions efficiently.

The 0/1 Knapsack Problem is a classic example in combinatorial optimization, where the goal is to select
a subset of items with given weights and values to maximize the total value without exceeding a
specified weight limit. This problem is pervasive in resource allocation scenarios and has significant
practical applications in fields such as finance, logistics, and resource management.

The Longest Common Subsequence (LCS) Problem focuses on identifying the longest subsequence
common to two sequences without altering the order of elements. This problem is integral to various
domains, including bioinformatics, text comparison, and version control systems, where understanding
similarities and differences between sequences is crucial.

The Matrix Chain Multiplication Problem aims to determine the most efficient way to multiply a
sequence of matrices. The objective is to fully parenthesize the product such that the number of scalar
multiplications is minimized. This problem is critical in optimizing computations in scientific computing
and computer graphics, where large matrix operations are routine.

By investigating these problems, this project aims to elucidate the principles and methodologies of
dynamic programming, showcasing its ability to break down complex problems into manageable
subproblems and solve them efficiently. The motivation behind this study is to highlight the significance
of dynamic programming in both theoretical and practical contexts, demonstrating its impact on
enhancing computational performance and problem-solving strategies across various applications. This
introduction sets the stage for a comprehensive exploration of dynamic programming techniques,
providing readers with a clear understanding of the project's scope and importance.

School of Computer Science and Engineering Page 4

 Algorithms Lab Subcode: B22EF0305

3.Problem statement:

This project addresses the inefficiency and computational challenges of solving complex
optimization problems such as the 0/1 Knapsack Problem, the Longest Common Subsequence (LCS)
Problem, and the Matrix Chain Multiplication Problem. Traditional methods for solving these
problems often result in excessive computational time and resource consumption, highlighting the
need for more efficient algorithmic solutions.
3. Project overview:
3.1. Objectives:
1.To Understand and Explain Dynamic Programming Concepts:
• Provide a detailed explanation of dynamic programming principles and how they apply
to optimization problems.
• Illustrate the step-by-step process of breaking down complex problems into simpler
subproblems.
2.To Implement Solutions for the 0/1 Knapsack Problem:
• Develop a dynamic programming algorithm to solve the 0/1 Knapsack Problem.
• Validate the algorithm with test cases to demonstrate its efficiency and correctness.
3.To Develop an Algorithm for the Longest Common Subsequence (LCS) Problem:
• Create a dynamic programming solution for finding the LCS of two sequences.
• Test the solution with various sequence pairs to ensure accuracy and performance.
4.To Optimize Matrix Chain Multiplication:
• Formulate a dynamic programming approach to minimize the number of scalar
multiplications in matrix chain multiplication.
• Conduct experiments to compare the performance of the dynamic programming
solution against traditional methods.
5.To Analyze and Compare Results:
• Perform a comparative analysis of the dynamic programming solutions for each
problem.
• Discuss the computational benefits and potential limitations of using dynamic
programming for these problems.
3.2. Goals:
The primary goal of this project is to explore and demonstrate the effectiveness of
dynamic programming in solving complex optimization problems, specifically the 0/1
Knapsack Problem, the Longest Common Subsequence (LCS) Problem, and the
Matrix Chain Multiplication Problem. By providing a comprehensive analysis and
implementation of dynamic programming techniques, this project aims to highlight
their significance in enhancing computational efficiency and problem-solving
capabilities in various applications.

School of Computer Science and Engineering Page 5

 Algorithms Lab Subcode: B22EF0305

4. Project Implementation
This document outlines the implementation details of the project, focusing on three dynamic
programming problems: the Longest Common Subsequence (LCS), the 0/1 Knapsack Problem,
and Matrix Chain Multiplication. The provided C code follows proper coding conventions,
includes appropriate comments, and maintains a logical flow to ensure ease of understanding
and maintenance.
4.1. Problem analysis and description.

1.Longest Common Subsequence (LCS):

• The lcs_length function calculates the length of the LCS between two sequences X and
Y using dynamic programming.
• A 2D array L is used to store the lengths of LCS for substrings of X and Y.
• The function prints the time complexity, O(m * n), where m and n are the lengths of the
sequences.

2.0/1 Knapsack Problem:

• The knapsack function solves the 0/1 Knapsack Problem using dynamic programming.
• A 2D array K is used to store the maximum value that can be obtained for a given
weight and items.
• The function prints the time complexity, O(n * W), where n is the number of items and
W is the capacity of the knapsack.

3.Matrix Chain Multiplication:

• The matrixChainOrder function finds the minimum number of scalar multiplications

needed for matrix chain multiplication using dynamic programming.
• A 2D array m is used to store the minimum number of multiplications.
• The function prints the time complexity, O(n^3), where n is the number of matrices.

4.Main Function:  The main function presents a menu for the user to choose which

problem to solve.

• Based on the user's choice, it prompts for necessary inputs, calls the appropriate
function, and measures the execution time using clock_gettime.

5.Time Measurement:

• The getElapsedTime function calculates the elapsed time between the start and end
times.

School of Computer Science and Engineering Page 6

 Algorithms Lab Subcode: B22EF0305

4.2. Modules identified:

Here are the identified modules in the given code:

1. Longest Common Subsequence (LCS) Module:

• Function: int lcs_length(char *X, char *Y, int m, int n)

• Description: Computes the length of the longest common subsequence between two
input sequences X and Y.

2. 0/1 Knapsack Problem Module:

• Function: int knapsack(int W, int wt[], int val[], int n)

• Description: Solves the 0/1 knapsack problem for a given capacity W, item weights
wt, item values val, and the number of items n.

3. Matrix Chain Multiplication Module:

• Function: int matrix Chain Order(int p[], int n)

• Description: Calculates the minimum number of scalar multiplications needed to
multiply a chain of matrices with dimensions specified in the array p.

4. Elapsed Time Calculation Module:

• Function: double getElapsedTime(struct timespec start, struct timespec end)

• Description: Calculates the elapsed time between two timestamps represented by
struct timespec.

School of Computer Science and Engineering Page 7

 Algorithms Lab Subcode: B22EF0305

5.Code with comments:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <time.h>

// Function to compute the length of the Longest Common Subsequence (LCS)

int lcs_length(char *X, char *Y, int m, int n) {
// Create a 2D array to store lengths of LCS
int L[m + 1][n + 1];
int i, j;
// Build the LCS table in bottom-up fashion
for (i = 0; i <= m; i++) {
for (j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
L[i][j] = 0;
} else if (X[i - 1] == Y[j - 1]) {
L[i][j] = L[i - 1][j - 1] + 1;
} else {
L[i][j] = (L[i - 1][j] > L[i][j - 1]) ? L[i - 1][j] : L[i][j - 1];
}
}
}
// Print the time complexity for LCS
printf("Time Complexity for LCS: O(m * n)\n");
return L[m][n];
}

// Function to solve the 0/1 Knapsack problem

School of Computer Science and Engineering Page 8

 Algorithms Lab Subcode: B22EF0305

int knapsack(int W, int wt[], int val[], int n) {

// Create a 2D array to store the maximum value that can be obtained
int i, w;
int K[n + 1][W + 1];
// Build the table in bottom-up fashion
for (i = 0; i <= n; i++) {
for (w = 0; w <= W; w++) {
if (i == 0 || w == 0) {
K[i][w] = 0;
} else if (wt[i - 1] <= w) {
K[i][w] = (val[i - 1] + K[i - 1][w - wt[i - 1]] > K[i - 1][w]) ?
(val[i - 1] + K[i - 1][w - wt[i - 1]]) : K[i - 1][w];
} else {
K[i][w] = K[i - 1][w];
}
}
}
// Print the time complexity for Knapsack
printf("Time Complexity for Knapsack: O(n * W)\n");
return K[n][W];
}

// Function to find the minimum number of scalar multiplications needed

// to multiply a chain of matrices int
matrixChainOrder(int p[], int n) {
// Create a 2D array to store the minimum number of multiplications
int m[n][n];
int i, j, k, L, q;
// Initialize the diagonal elements to 0
for (i = 1; i < n; i++)
m[i][i] = 0;
// L is the chain length

School of Computer Science and Engineering Page 9

 Algorithms Lab Subcode: B22EF0305

for (L = 2; L < n; L++) {

for (i = 1; i < n - L + 1; i++) {
j = i + L - 1;
m[i][j] = INT_MAX;
for (k = i; k <= j - 1; k++) {
q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
if (q < m[i][j])
m[i][j] = q;
}
}
}
// Print the time complexity for Matrix Chain Multiplication
printf("Time Complexity for Matrix Chain Multiplication: O(n^3)\n");
return m[1][n - 1];
}
// Function to calculate the elapsed time between two timestamps
double getElapsedTime(struct timespec start, struct timespec end) {
return ((double) (end.tv_sec - start.tv_sec)) + ((double) (end.tv_nsec - start.tv_nsec)) / 1.0e9; }
// Main function
int main(){
int choice;
// Display the menu and get user choice
printf("Choose the problem to solve:\n");
printf("1.Longest Common Subsequence\n");
printf("2. 0/1 Knapsack problem\n");
printf("3. Matrix Chain Multiplication\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch(choice) {
case 1: {
// Handle LCS problem
char X[100], Y[100];

School of Computer Science and Engineering Page 10

 Algorithms Lab Subcode: B22EF0305

printf("Enter the first sequence: ");

scanf("%s", X);
printf("Enter the second sequence:");
scanf("%s", Y);
int m = strlen(X);
int n = strlen(Y);

// Measure time taken by LCS function

struct timespec start, end;
clock_gettime(CLOCK_MONOTONIC, &start);
int result = lcs_length(X, Y, m, n);
clock_gettime(CLOCK_MONOTONIC, &end);
double time_spent = getElapsedTime(start, end);
// Output the result
printf("Length of Longest Common Subsequence: %d\n", result);
printf("Time taken: %.6f seconds\n", time_spent);
break;
}
case 2: {
// Handle Knapsack problem

int n, W;

printf("Enter the number of items:");

scanf("%d", &n);

int val[n], wt[n];

printf("Enter the values and weights of %d items:\n", n);
int i;
for (i = 0; i < n; i++) {
printf("Item %d value: ", i + 1);
scanf("%d", &val[i]);
printf("Item %d weight: ", i + 1);
scanf("%d", &wt[i]);

School of Computer Science and Engineering Page 11

 Algorithms Lab Subcode: B22EF0305

}
printf("Enter the capacity of the knapsack: ");
scanf("%d", &W);
// Measure time taken by Knapsack function
struct timespec start, end;
clock_gettime(CLOCK_MONOTONIC, &start);
int result = knapsack(W, wt, val, n);
clock_gettime(CLOCK_MONOTONIC, &end);
double time_spent = getElapsedTime(start, end);
// Output the result
printf("Maximum value that can be obtained is %d\n", result);
printf("Time taken: %.6f seconds\n", time_spent);
break;
}
case 3: {
// Handle Matrix Chain Multiplication problem
int n;
printf("Enter the number of matrices: ");

scanf("%d", &n);

int p[n + 1];

printf("Enter the dimensions of %d matrices:\n", n);
int i;
for (i = 0; i <= n; i++) {
printf("Dimension of matrix %d:",i+ 1);
scanf("%d", &p[i]);
}
// Measure time taken by Matrix Chain Multiplication function
struct timespec start, end;
clock_gettime(CLOCK_MONOTONIC, &start);
int result = matrixChainOrder(p, n + 1);
clock_gettime(CLOCK_MONOTONIC,&end);
double time_spent = getElapsedTime(start, end);

School of Computer Science and Engineering Page 12

 Algorithms Lab Subcode: B22EF0305

// Output the result

printf("Minimum number of scalar multiplications needed: %d\n", result);
printf("Time taken: %.6f seconds\n", time_spent);
break;
}
default:
printf("Invalid choice!\n");
}

return 0;
}

School of Computer Science and Engineering Page 13

 Algorithms Lab Subcode: B22EF0305

6.Output and results

• OUTPUTS:

School of Computer Science and Engineering Page 14

 Algorithms Lab Subcode: B22EF0305

• RESULTS:

Results refer to the broader and often longer-term changes or benefits that occur as a direct or
indirect consequence of the outputs. For the provided code, the results include:

1. Enhanced Understanding of Dynamic Programming:

 Users gain a deeper understanding of how dynamic programming can be

used to solve complex problems like LCS, Knapsack, and Matrix Chain
Multiplication.  Result: Improved problem-solving skills and algorithmic
thinking.

2. Efficiency in Problem Solving:

• The code demonstrates efficient solutions to common computational problems,

which can be applied in various fields such as bioinformatics, logistics, and
computer science.
• Result: More efficient and effective problem-solving approaches in real-world
applications.

3. Educational Tool:

• The code can be used as an educational tool for teaching dynamic programming
and algorithm analysis in computer science courses.
• Result: Better educational outcomes for students learning about algorithms.

School of Computer Science and Engineering Page 15

 Algorithms Lab Subcode: B22EF0305

4. Benchmarking and Performance Analysis:

• By measuring execution time, users can benchmark the performance of different

algorithms and optimize them further.
• Result: Enhanced performance of software applications that implement these
algorithms.

5. Foundation for Further Research:

• The code provides a foundation for further research and development in algorithm
optimization and advanced problem-solving techniques.
• Result: Advancement in the field of computer science research.

In summary, while the outputs of the code are the immediate, quantifiable results such as the length of
LCS, maximum knapsack value, and minimum matrix multiplications, the results are the broader,
longterm benefits like improved understanding, enhanced problem-solving skills, educational
advancements, performance benchmarking, and a foundation for further research.

School of Computer Science and Engineering Page 16

 Algorithms Lab Subcode: B22EF0305

7.Conclusions:

The provided code is a comprehensive implementation of three classical dynamic programming

problems: Longest Common Subsequence (LCS), 0/1 Knapsack, and Matrix Chain Multiplication.
The code includes functionality to measure and report the execution time of each algorithm, providing
a practical perspective on their computational efficiency.

From a purely time complexity perspective, the longest common subsequence (LCS) problem
typically has the best performance with O(mn).The 0/1 knapsack problem can also be efficient, but its
performance heavily depends on the capacity W. Matrix chain multiplication, with O(n3), generally
has the worst time complexity among the three for large inputs.

Here are the key takeaways.

1. Effective Implementation of Algorithms:

• The code effectively implements three dynamic programming algorithms, each designed to
solve a specific type of problem.
• The LCS algorithm calculates the longest subsequence common to two sequences.
• The 0/1 Knapsack algorithm determines the maximum value that can be obtained from a
set of items without exceeding a weight limit.
2. User Interaction:

• The code is user-friendly, allowing users to input sequences, item values and weights, and
matrix dimensions interactively.
• The choice-based menu structure guides the user to select the desired problem to solve.

3. Performance Measurement:

• By measuring and displaying the execution time for each algorithm, the code provides
insight into their computational performance.
• Time complexity statements are printed, helping users understand the theoretical efficiency
of each algorithm.

4. Educational Value:

• The code serves as an excellent educational tool for learning and teaching dynamic
programming concepts.
• Comments and structured implementation make it easier for learners to follow and
understand the logic behind each algorithm.

5. Real-World Applicability:

School of Computer Science and Engineering Page 17

 Algorithms Lab Subcode: B22EF0305

• The algorithms implemented are fundamental to various applications in computer science

and related fields, such as bioinformatics, operations research, and computer graphics.
8.References:

"Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and

Clifford Stein

"Algorithms" by Robert Sedgewick and Kevin Wayne

"Algorithm Design" by Jon Kleinberg and Éva Tardos

"The Art of Computer Programming, Volume 1: Fundamental Algorithms" by Donald E. Knuth

"Knapsack Problems: Algorithms and Computer Implementations" by Silvano Martello and Paolo Toth

"Dynamic Programming Algorithm Optimization for Sequence Alignment" by Saul B. Needleman and
Christian D. Wunsch

"A Fast Algorithm for Matrix Chain Multiplication" by Huynh Tu Dang and Toshihide Ibaraki

"Dynamic Programming and Optimal Control" by Dimitri P. Bertsekas

"Algorithms Unlocked" by Thomas H. Cormen

"The Algorithm Design Manual" by Steven S. Skiena

"Advanced Algorithms and Data Structures" by Marcello La Rocca

School of Computer Science and Engineering Page 18