DAA LAB EXPERIMENTS
Aria is working on a text analysis tool that processes user feedback messages from a mobile
application. She noticed that users sometimes use palindromic words or phrases to express
emotion, emphasis, or creativity - especially when they type fast or informally
To better understand this behavior, Aria's task is to identify the longest palindromic
substring in each of the feedback messages collected. If there are multiple palindromic
substrings of the same maximum length, she prefers the one that appears first in the
message (i.e., the one with the smallest starting index).
Your job is to help Aria by writing a program that takes multiple feedback messages as input
and finds the longest palindromic substring in each using Manacher’s Algorithm.
Example
Input:
abacd
abbcd
Output:
aba
bb
// You are using GCC
#include<iostream>
using namespace std;
string center(string str, int left, int right) {
while (left >= 0 && right < [Link]() && str[left] == str[right]) {
left--;
right++;
return [Link](left + 1, right - left - 1);
}
string longestPalindrome(string str) {
string temp = "";
int len = [Link]();
for (int i = 0; i < len; i++) {
string oddstr = center(str, i, i);
string evenstr = center(str, i, i + 1);
if ([Link]() > [Link]())
temp = oddstr;
if ([Link]() > [Link]())
temp = evenstr;
return temp;
int main() {
int T;
cin >> T;
while (T--) {
string str;
cin >> str;
cout << longestPalindrome(str) << endl;
return 0;
2. You are building the backend of a financial platform that records users daily transactions
over a period of N days. Each transaction can be a positive value (deposit) or negative value
(withdrawal). Your system must support:
• Efficient querying of the total transaction amount between two days.
• Updating a transaction amount on a specific day due to corrections or adjustments.
Given the high volume of data and operations, you must implement these operations using a
Segment Tree to ensure logarithmic time complexity.
Input format :
The first line contains two integers, N and Q, representing the number of days and number
of operations.
The second line contains N space-separated integers representing the transaction amount
for each day.
The next Q lines contain operations in one of the following formats:
• S L R represents Query sum from index L to R
• U i val Updates index i with new value val
All indices are 0-based.
// You are using GCC
#include<iostream>
#include<vector>
using namespace std;
class SegmentTree{
vector<int> tree;
int n;
public:
SegmentTree(vector<int> &arr){
n = [Link]();
[Link](4*n);
build(arr,0,n-1,1);
void build(vector<int>& arr,int start,int end,int node){
if(start == end){
tree[node] = arr[start];
return;
int mid = (start+end)/2;
build(arr,start,mid,2*node);
build(arr,mid+1,end,2*node+1);
tree[node] = tree[2*node]+tree[2*node+1];
int query(int l,int r,int start,int end,int node){
if(r < start || l > end)return 0;
if(l <= start && end <= r)return tree[node];
int mid = (start + end)/2;
int leftSum = query(l,r,start,mid,2*node);
int rightSum = query(l,r,mid+1,end,2*node+1);
return leftSum+rightSum;
int query(int l,int r){
return query(l,r,0,n-1,1);
void update(int index,int val,int start,int end,int node){
if(start == end){
tree[node] = val;
return ;
int mid = (start+end)/2;
if(index <= mid)update(index,val,start,mid,2*node);
else update(index,val,mid+1,end,2*node+1);
tree[node] = tree[2*node]+tree[2*node+1];
}
void update(int index,int val){
update(index,val,0,n-1,1);
};
int main(){
int N,Q;
cin>>N>>Q;
vector<int>arr(N);
for(int i = 0;i<N;i++)cin>>arr[i];
SegmentTree seg(arr);
while(Q--){
char type;
cin>>type;
if(type == 'S'){
int L,R;
cin >> L >> R;
cout<<[Link](L,R)<<endl;
}else if(type == 'U'){
int i,val;
cin >> i >>val;
[Link](i,val);
return 0;
3.
Ram is planning activities for a person during the day. He has a list of activities, and each
activity has a start time and an end time. The person can only do one activity at a time, and
they need to maximize the number of activities they can participate in. His goal is to select
the maximum number of non-overlapping activities. Help Ram to complete the task.
Input format :
The first line of input is an integer n, representing the number of activities.
The second line of input consists of n space-separated integers representing the start times
of the activities.
The third line of input consists of n space-separated integers representing the finish times of
the activities.
Output format :
The output displays the indices of the selected activities separated by a space, representing
the maximum number of activities that can be performed.
// You are using GCC
#include <bits/stdc++.h>
using namespace std;
struct Activity {
int start, finish, index;
};
bool comp(Activity a, Activity b) {
if ([Link] == [Link])
return [Link] < [Link];
return [Link] < [Link];
int main() {
int n;
cin >> n;
vector<int> start(n), finish(n);
for (int i = 0; i < n; i++) cin >> start[i];
for (int i = 0; i < n; i++) cin >> finish[i];
vector<Activity> activities(n);
for (int i = 0; i < n; i++) {
activities[i] = {start[i], finish[i], i};
sort([Link](), [Link](), comp);
vector<int> result;
int lastFinish = -1;
for (auto &act : activities) {
if ([Link] >= lastFinish) {
result.push_back([Link]);
lastFinish = [Link];
for (int i = 0; i < [Link](); i++) {
cout << result[i];
if (i != [Link]() - 1) cout << " ";
}
cout << endl;
return 0;
Given an undirected graph and a number m, determine if the graph can be colored with at
most m colors such that no two adjacent vertices of the graph are colored with the same
color.
Note: Here, the coloring of a graph means the assignment of colors to all vertices.
Example
Input:
0111
1010
1101
1010
Output:
Solution Exists:
1232
Explanation:
A minimum of 3 colors is required for the above graph.
Input format :
The input consists of four lines each containing four space-separated integers (1 if
connected, 0 if not), representing the adjacency matrix of a graph where each element
represents the connection between vertices.
The last line consists of an integer m, representing the number of colors available.
// You are using GCC
#include <bits/stdc++.h>
using namespace std;
const int V = 4; // number of vertices (fixed as 4)
// Check if assigning color c to vertex v is safe
bool isSafe(int v, vector<vector<int>>& graph, vector<int>& color, int c) {
for (int i = 0; i < V; i++) {
if (graph[v][i] && color[i] == c)
return false;
return true;
bool graphColoringUtil(vector<vector<int>>& graph, int m, vector<int>& color, int v) {
if (v == V)
return true;
for (int c = 1; c <= m; c++) {
if (isSafe(v, graph, color, c)) {
color[v] = c;
if (graphColoringUtil(graph, m, color, v + 1))
return true;
color[v] = 0;
}
return false;
int main() {
vector<vector<int>> graph(V, vector<int>(V));
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
cin >> graph[i][j];
int m;
cin >> m;
vector<int> color(V, 0);
if (graphColoringUtil(graph, m, color, 0)) {
cout << "Solution Exists:" << endl;
for (int i = 0; i < V; i++) {
cout << color[i] << " ";
cout << endl;
} else {
cout << "Solution does not exist" << endl;
}
return 0;
Lydia is a jewelry designer who is about to showcase her collection at a prestigious
exhibition. She has a limited display space and needs to choose a subset of her jewelry items
to display that will maximize her total value while staying within the space constraints. Each
piece of jewelry has a certain weight and value associated with it. Your task is to help Lydia
choose the best combination of jewelry pieces to maximize her total display value without
exceeding the available space in her showcase.
To solve this problem, you will implement the Branch and Bound algorithm to determine
the maximum value that Lydia can display.
Input format :
The first line of input consists of two integers, G and H, where:
• G represents the number of jewelry items.
• H represents the total available weight capacity of the display showcase.
The second line consists of G integers representing the weight of each jewelry item.
The third line consists of G integers representing the value of each jewelry item.
#include <bits/stdc++.h>
using namespace std;
struct Item {
int weight, value;
double ratio;
};
struct Node {
int level, weight, value;
double bound;
};
bool cmp(Item a, Item b) {
return [Link] > [Link];
double bound(Node u, int n, int W, vector<Item>& items) {
if ([Link] >= W) return 0;
double profit_bound = [Link];
int j = [Link] + 1;
int totweight = [Link];
while ((j < n) && (totweight + items[j].weight <= W)) {
totweight += items[j].weight;
profit_bound += items[j].value;
j++;
if (j < n) {
profit_bound += (W - totweight) * items[j].ratio;
return profit_bound;
double knapsack(int W, vector<Item>& items, int n) {
sort([Link](), [Link](), cmp);
queue<Node> Q;
Node u, v;
[Link] = -1;
[Link] = 0;
[Link] = 0;
[Link](u);
double maxProfit = 0;
while (![Link]()) {
u = [Link]();
[Link]();
if ([Link] == n - 1) continue;
[Link] = [Link] + 1;
// Case 1: take the item
[Link] = [Link] + items[[Link]].weight;
[Link] = [Link] + items[[Link]].value;
if ([Link] <= W && [Link] > maxProfit)
maxProfit = [Link];
[Link] = bound(v, n, W, items);
if ([Link] > maxProfit)
[Link](v);
// Case 2: skip the item
[Link] = [Link];
[Link] = [Link];
[Link] = bound(v, n, W, items);
if ([Link] > maxProfit)
[Link](v);
return maxProfit;
int main() {
int G, H;
cin >> G >> H;
vector<int> weights(G), values(G);
for (int i = 0; i < G; i++) cin >> weights[i];
for (int i = 0; i < G; i++) cin >> values[i];
vector<Item> items(G);
for (int i = 0; i < G; i++) {
items[i].weight = weights[i];
items[i].value = values[i];
items[i].ratio = (double)values[i] / weights[i];
double result = knapsack(H, items, G);
cout << fixed << setprecision(2) << result << endl;
return 0;
}
You are required to implement a program that calculates the area of different shapes based
on given dimensions.
The program should provide support for calculating the area of rectangles, triangles, and
circles.
The shapes are identified by the following characters: 'r' for rectangle, 't' for triangle, and 'c'
for circle.
Write a function called calculateArea that takes the following parameters:
1. length (integer): The length of the shape.
2. breadth (integer): The breadth of the shape.
3. shape (character, optional): The shape identifier. The default value is 'r' for the
rectangle.
Function Specification
void calculateArea(int length, int breadth, char shape = 'r')
// You are using GCC
#include <iostream>
#include <iomanip>
using namespace std;
void calculateArea(int length, int breadth, char shape = 'r') {
switch (shape) {
case 'r': // Rectangle
cout << "Area of rectangle: " << length * breadth << endl;
break;
case 't': // Triangle
cout << "Area of triangle: " <<0.5* length * breadth << endl;
break;
case 'c': { // Circle, use length as radius, ignore breadth
double area = 3.14 * length * length;
cout << fixed << setprecision(2);
cout << "Area of circle: " << area << endl;
break;
default:
cout << "Invalid shape!" << endl;
break;
int main() {
int length, breadth;
char shape;
cin >> length;
cin >> breadth;
cin >> shape;
calculateArea(length, breadth, shape);
return 0;
Problem Statement:
You are given a 2D grid of size R x C where each cell contains a non-negative integer
representing the cost to step into that cell. Your task is to find the minimum cost to reach
the bottom-right cell (R-1, C-1) from the top-left cell (0, 0).
You are allowed to move in the following three directions:
Right: Move from (i, j) to (i, j + 1)
Down: Move from (i, j) to (i + 1, j)
Diagonal: Move from (i, j) to (i + 1, j + 1)
Your goal is to compute the minimum total cost to reach the destination cell using any
combination of these three movements.
Input format :
The first line contains two integers R and C — the number of rows and columns in the grid.
The next R lines each contain C integers — the grid values.
// You are using GCC
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
[Link](nullptr);
int R,C;
cin >> R>> C;
vector<vector<int>> grid(R,vector<int>(C));
for(int i = 0;i < R;i++){
for(int j = 0;j < C;j++){
cin >> grid[i][j];
vector<vector<long long>> dp(R,vector<long long>(C,0));
dp[0][0] = grid[0][0];
for(int j =1;j<C;j++)
dp[0][j] = dp[0][j-1]+grid[0][j];
for(int i =1;i<R;i++)
dp[i][0] = dp[i-1][0] + grid[i][0];
for(int i =1 ;i<R;i++){
for(int j = 1;j<C;j++){
dp[i][j] = grid[i][j] +min({dp[i-1][j],dp[i][j-1],dp[i-1][j-1]});
cout<<dp[R-1][C-1]<<"\n";
return 0;