Algorithm Analysis & Design Lab Report
Class: 2nd Year 1st Semester
1. Longest Common Subsequence (LCS)
The LCS problem is to find the longest sequence which exists in both given sequences. Dynamic
programming is used for efficient computation.
2. 0/1 Knapsack
This is a classic optimization problem where each item has a weight and value. The objective is to
maximize value within a fixed capacity using dynamic programming.
3. Coin Collecting by Robot
This problem involves finding the maximum number of coins a robot can collect while moving only
right or down in a grid. Dynamic programming techniques are applied here.
4. Merge Sort
A divide-and-conquer sorting algorithm. It divides the array into halves, sorts them, and merges
them back.
5. Quick Sort
Another divide-and-conquer sorting method that selects a pivot and partitions the array. It sorts the
partitions recursively.
6. Change Making Problem
This problem finds the minimum number of coins to make a given amount. Dynamic programming
is used to solve it efficiently.
7. Prim's Minimum Spanning Tree (MST)
A greedy algorithm that grows the MST by adding the smallest edge that connects a vertex in the
tree to one outside it.
8. Kruskal's Minimum Spanning Tree (MST)
Another greedy algorithm for finding the MST, it sorts all the edges and adds the smallest edge
that doesn't form a cycle.
9. Dijkstra's Shortest Path Algorithm
This algorithm finds the shortest path from a source node to all other nodes in a graph with
non-negative edge weights.
Submitted by: [Your Name]
Date: [Insert Date]
