DAA 1 Merged

DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
Experiment 1
Student Name: UID:
Branch: CSE Section/Group:
Semester: 5th Date of Performance:
Subject Name: DAA LAB Subject Code: 22CSH-311
1. Aim: Analyze if the stack is empty or full, and if elements are present,
return the top element in the stack using templates. Also, perform push and
pop operations on the stack.
2. Objective:
The objective of this experiment seems to be to implement a stack data
structure using templates in C++ that supports basic operations such as
push, pop, top, and checking if the stack is empty or full
Perform and verify stack operations such as pushing, popping, checking if
the stack is empty, and accessing the top element.
3. Implementation/Code:
#include <iostream>
#include <climits>
using namespace std;
template <typename T>
class Stack {
T* arr;
int top;
int capacity;
DEPARTMENT OF
public:
Stack(int c) {
capacity = c;
arr = new T[c];
top = -1;
}
void push(T data) {

if (isFull()) {
cout << "Overflow" << endl;
return;
}
top++;
arr[top] = data;
}
T pop() {
if (isEmpty()) {
cout << "Underflow" << endl;
return T();
}
T popped = arr[top];
top--;
return popped;
DEPARTMENT OF
}
T gettop() {
if (isEmpty()) {
cout << "Stack is empty" << endl;
return T();
}
return arr[top];
}
bool isEmpty() {
return top == -1;
}
bool isFull() {
return top == capacity - 1;
}
};
int main() {
Stack<int> st(5);
st.push(8);
st.push(7);
DEPARTMENT OF
st.push(10);
cout << "Top element: " << st.gettop() << endl;
st.push(2);
cout << "Top element after push: " << st.gettop() << endl;
st.pop();
cout << "Top element after pop: " << st.gettop() << endl
return 0;
}
4. Output
5. Time Complexity
1. Push Operation: O(1)
2. Pop Operation: O(1)
3. If empty Operation: O(1)
4. If full: O(1)
DEPARTMENT OF
6. Learning Outcome
• Understanding how to implement a generic stack using templates enhances
your ability to write flexible and reusable code that can work with different
data types.
• Learning the fundamental operations (push, pop, getTop, isEmpty, isFull) and
their implementation in a stack data structure helps reinforce understanding
of basic data structures and algorithms.
• Practicing dynamic memory allocation and deallocation (new[] and delete[])
within the context of a stack class improves proficiency in memory
management practices in C++.
DEPARTMENT OF
Experiment 2
Student Name: UID:
1. Aim: Code implement power function in O(logn) time complexity.

2. Objective:
The objective here is to implement a power function in C++ that computes
x^n in O(logn) time complexity using an efficient approach called
"exponentiation by squaring".
#include <iostream>
long long power(long long x, long long n) {

if (n == 0)
return 1;
else if (n % 2 == 0) {
long long half_pow = power(x, n / 2);
return half_pow * half_pow;
} else {
long long half_pow = power(x, n / 2);
return half_pow * half_pow * x;
}
DEPARTMENT OF
int main() {
long long x = 2;
long long n = 10;
long long result = power(x, n);
cout << x << "^" << n << " = " << result << endl;
return 0;
}
4. Output
5. Time Complexity
O(log n)
6. Learning Outcome
• You learn a powerful technique for computing powers efficiently.
Exponentiation by squaring reduces the number of multiplicative operations
drastically compared to a naive approach that directly multiplies the base x by
itself n times.
• You understand the importance of time complexity in algorithm design
• You develop skills in algorithmic thinking and optimization
DEPARTMENT OF
Experiment 3
Student Name: Zatch UID:

Branch: BE-CSE Section/Group:
Subject Name: DAA Lab Subject Code: 22CHS-311
1. Aim: Code to find frequency of elements in a given array in O(n) time

complexity.
2. Objective: Traverse the input array and increment the frequency of the element
if the current element and the previous element are the same, otherwise reset the
frequency and print the element and its frequency.
3. Algorithm:
Step 1: Initialize: Set freq to 1, idx to 1, and element to arr[0].
Step 2: Traverse Array: While idx < n, check if arr[idx] is equal to arr[idx - 1].
Step 3: Update Frequency: If equal, increment freq; if not, print element and
freq, then update element to arr[idx] and reset freq to 1.
Step 4: Increment Index: Always increment idx.
Step 5: Print Last: After exiting the loop, print the last element and its freq.
#include <iostream>
void findFrequencies(int arr[], int n) {

int freq = 1;
int idx = 1;
int element = arr[0];
while (idx < n) {

if (arr[idx - 1] == arr[idx]) {
freq++;
} else {
cout << element << " > " << freq << endl;
element = arr[idx];
freq = 1;
}
DEPARTMENT OF
idx++;
}
// Print the frequency of the last element
cout << element << " > " << freq << endl;
}
int main() {
cout << "Frequencies in a sorted Array ::-" << endl;
int arr[] = {5, 5, 10, 10, 10, 20, 30, 30, 40, 40, 40, 50};
int n = sizeof(arr) / sizeof(arr[0]);
findFrequencies(arr, n);
return 0;
}
5. Output:
6. Time Complexity: O(n)
7. Space Complexity: O(1)
8. Learning Outcomes:
a. Understand how to calculate element frequencies in a sorted array.
b. Learn to implement and debug basic array traversal and comparison
techniques.
c. Develop skills in handling and printing results for di
different
fferent array scenarios.
DEPARTMENT OF
Experiment 3

1. Aim: Apply the concept of Linked list and write code to Insert and Delete an element
at the beginning and at end in Doubly and Circular Linked List.
2. Objective: The objective of this experiment is to implement and demonstrate the basic
operations—insertion and deletion—at both the beginning and end of Doubly Linked
Lists and Circular Linked Lists, showcasing how these structures can be efficiently
managed and manipulated.
3. Algorithm:
Algorithm for Doubly Linked List (DLL)
Insertion at the Beginning:
1. Create a New Node: Create a new node with the given data.
2. Check if List is Empty:
o If the list is empty, set both head and tail to point to the new node.
o Otherwise, proceed to the next step.
3. Link New Node:
o Set the new node’s next to point to the current head.
o Set the current head's prev to point to the new node.
4. Update Head: Set the new node as the head.
Insertion at the End:
o If the list is empty, set both head and tail to point to the new node.
3. Link New Node:
o Set the current tail's next to point to the new node.
o Set the new node’s prev to point to the current tail.
4. Update Tail: Set the new node as the tail.
Deletion from the Beginning:
1. Check if List is Empty: If the list is empty, do nothing.

DEPARTMENT OF
2. Check if Single Node:
o If the list has only one node, delete the node and set both head and tail to
nullptr.
3. Delete Node:
o Store the current head in a temporary pointer.
o Move head to the next node.
o Set the new head's prev to nullptr.
o Delete the temporary node.
Deletion from the End:

o If the list has only one node, delete the node and set both head and tail to
nullptr.
3. Delete Node:
o Store the current tail in a temporary pointer.
o Move tail to the previous node.
o Set the new tail's next to nullptr.
Algorithm for Circular Linked List (CLL)

Insertion at the Beginning:
o If the list is empty, set the head to the new node and point next to itself.
3. Find Last Node:
o Traverse the list to find the last node (node whose next points to head).
4. Link New Node:
o Set the new node’s next to the current head.
o Set the last node’s next to point to the new node.
5. Update Head: Set the new node as the head.
Insertion at the End:
o If the list is empty, set the head to the new node and point next to itself.
3. Find Last Node:
4. Link New Node:
o Set the last node’s next to the new node.
o Set the new node’s next to point to head.
DEPARTMENT OF
Deletion from the Beginning:

o If the list has only one node, delete the node and set head to nullptr.
3. Find Last Node:
4. Delete Node:
o Store the current head in a temporary pointer.
o Move head to the next node.
o Set the last node’s next to point to the new head.
Deletion from the End:

o If the list has only one node, delete the node and set head to nullptr.
3. Find Second Last Node:
o Traverse the list to find the second last node (node whose next points to the
last node).
4. Delete Node:
o Store the last node in a temporary pointer.
o Set the second last node’s next to point to head.
Doubly Linked List:
#include <iostream>
struct Node {
int data;
Node* prev;
Node* next;
Node(int val) : data(val), prev(nullptr), next(nullptr) {}

};
class DoublyLinkedList {
public:
Node* head;
Node* tail;
DEPARTMENT OF
DoublyLinkedList() : head(nullptr), tail(nullptr) {}
// Insert at the beginning

void insertAtBeginning(int val) {
Node* newNode = new Node(val);
if (!head) {
head = tail = newNode;
} else {
newNode->next = head;
head->prev = newNode;
head = newNode;
}
cout << "Inserted " << val << " at the beginning." << endl;
}
// Insert at the end

void insertAtEnd(int val) {
if (!tail) {
head = tail = newNode;
} else {
tail->next = newNode;
newNode->prev = tail;
tail = newNode;
}
cout << "Inserted " << val << " at the end." << endl;
}
// Delete from the beginning

void deleteFromBeginning() {
if (!head) return;
Node* temp = head;
if (head == tail) {
head = tail = nullptr;
} else {
head = head->next;
head->prev = nullptr;
}
cout << "Deleted " << temp->data << " from the beginning." << endl;
delete temp;
}
// Delete from the end

void deleteFromEnd() {
if (!tail) return;
DEPARTMENT OF
Node* temp = tail;
if (head == tail) {
head = tail = nullptr;
} else {
tail = tail->prev;
tail->next = nullptr;
}
cout << "Deleted " << temp->data << " from the end." << endl;
delete temp;
}
void printList() {
cout << "Current List: ";
Node* current = head;
while (current) {
cout << current->data << " ";
current = current->next;
}
cout << endl;
}
};
int main() {
DoublyLinkedList dll;
dll.insertAtBeginning(3);
dll.insertAtEnd(4);
dll.insertAtBeginning(2);
dll.insertAtEnd(5);
dll.printList(); // Output: 2 3 4 5
dll.deleteFromBeginning();
dll.printList(); // Output: 3 4 5
dll.deleteFromEnd();
dll.printList(); // Output: 3 4
return 0;
}
DEPARTMENT OF
Circular Linked List:
#include <iostream>
struct Node {
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}

};
class CircularLinkedList {
public:
Node* head;
CircularLinkedList() : head(nullptr) {}
// Insert at the beginning

void insertAtBeginning(int val) {
if (!head) {
head = newNode;
head->next = head;
} else {
Node* temp = head;
while (temp->next != head) {
temp = temp->next;
}
temp->next = newNode;
head = newNode;
}
cout << "Inserted " << val << " at the beginning." << endl;
}
// Insert at the end

void insertAtEnd(int val) {
if (!head) {
head = newNode;
head->next = head;
} else {
Node* temp = head;
DEPARTMENT OF
temp = temp->next;
}
temp->next = newNode;
}
cout << "Inserted " << val << " at the end." << endl;
}
// Delete from the beginning

void deleteFromBeginning() {
if (!head) return;
if (head->next == head) {
cout << "Deleted " << head->data << " from the beginning." << endl;
delete head;
head = nullptr;
} else {
Node* temp = head;
temp = temp->next;
}
Node* delNode = head;
temp->next = head->next;
head = head->next;
cout << "Deleted " << delNode->data << " from the beginning." << endl;
delete delNode;
}
}
// Delete from the end

void deleteFromEnd() {
if (!head) return;
if (head->next == head) {
cout << "Deleted " << head->data << " from the end." << endl;
delete head;
head = nullptr;
} else {
Node* temp = head;
while (temp->next->next != head) {
temp = temp->next;
}
Node* delNode = temp->next;
temp->next = head;
cout << "Deleted " << delNode->data << " from the end." << endl;
delete delNode;
}
DEPARTMENT OF
}
void printList() {
if (!head) {
cout << "The list is empty." << endl;
return;
}
cout << "Current List: ";
Node* current = head;
do {
cout << current->data << " ";
current = current->next;
} while (current != head);
cout << endl;
}
};
int main() {
CircularLinkedList cll;
cll.insertAtBeginning(3);
cll.insertAtEnd(4);
cll.insertAtBeginning(2);
cll.insertAtEnd(5);
cll.printList(); // Output: 2 3 4 5
cll.deleteFromBeginning();
cll.printList(); // Output: 3 4 5
cll.deleteFromEnd();
cll.printList(); // Output: 3 4
return 0;
}
DEPARTMENT OF
5. Output:
(Doubly Linked List)
(Circular Linked List)
6. Time Complexity: O(1) For insertion and deletion

O(n) For display
7. Space Complexity: O(n)
a. Understand to manage nodes with insertion and deletion at both ends.
b. Understand time and space complexities.
c. Understand to apply linked list to solve real world problems.
DEPARTMENT OF
Experiment 5
1. Aim:
Sort a given set of elements using the Quick sort method and determine the
time required to sort the elements. Repeat the experiment for different
values of n, the number of elements in the list to be sorted. The elements
can be read from a file or can be generated using the random number
generator.
2. Objective:
To sort a list of elements using the Quick sort algorithm and measure the
time complexity for different list sizes.
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>

void quickSort(std::vector<int>& arr, int low, int high) {
if (low < high) {
int pivot = arr[high];
int i = low - 1;
DEPARTMENT OF
for (int j = low; j < high; j++) {

if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
int pi = i + 1;
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
double measureTime(int n) {
vector<int> arr(n);
for (int& num : arr) {
num = rand() % 10000; // Random numbers
}
clock_t start = clock();

quickSort(arr, 0, n - 1);
clock_t end = clock();
return double(end - start) / CLOCKS_PER_SEC;

}
DEPARTMENT OF
int main() {
srand(time(0)); // Seed for random number generation
int sizes[] = {100, 500, 1000, 5000, 10000}; // Different sizes to test
for (int n : sizes) {
double timeTaken = measureTime(n);
std::cout << "Time taken to sort " << n << " elements: " << timeTaken
<< " seconds" << std::endl;
}
return 0;
}
4. Output
5. Time Complexity
Average Case: O(nlogn)
Worst Case: O(n^2)
DEPARTMENT OF
6. Learning Outcome
• Learn the principles and steps involved in the Quick sort algorithm,
including the partitioning process and recursive sorting. Understand how
the algorithm sorts an array by dividing it into smaller sub-arrays.
• Gain insight into the time and space complexity of Quick sort. Learn to
differentiate between the average-case, worst-case, and best-case scenarios
and understand the factors influencing Quick sort's performance.
• Compare Quick sort's efficiency with other sorting algorithms like Merge
sort, Heap sort, and Bubble sort. Understand the trade-offs between Quick
sort’s average-case performance and its worst-case behavior.
• Develop skills in implementing Quick sort in a programming language
(e.g., C++). Learn about pivot selection strategies and how they affect the
algorithm’s performance. Gain experience in optimizing and debugging
sorting algorithms.
• Learn how to measure and analyze the performance of Quick sort.
Understand how to use timing functions to evaluate sorting efficiency and
how different input sizes impact the sorting time. Develop the ability to
interpret performance results and apply this knowledge to real-world
scenarios.
DEPARTMENT OF
Experiment-6
1. Aim:
Develop a program and analyze complexity to implement subset-sum
problem using Dynamic Programming.
2. Objective:
The objective of this program is to determine whether a subset of a given
set of integers sums to a specified value. This problem is a classic example
of dynamic programming where we use a table to store intermediate results
and build the solution incrementally.
#include <iostream>
#include <vector>
void printSubsets(vector<int>& arr, vector<vector<bool>>& dp, int i, int

j, vector<int>& subset) {
if (j == 0) {
cout << "{ ";
for (int num : subset) {
cout << num << " ";
}
DEPARTMENT OF
cout << "}" << endl;

return;
}
if (i == 0) return;
if (dp[i-1][j]) {
printSubsets(arr, dp, i-1, j, subset);
}
if (j >= arr[i-1] && dp[i-1][j - arr[i-1]]) {

subset.push_back(arr[i-1]);
printSubsets(arr, dp, i-1, j - arr[i-1], subset);
subset.pop_back();
}
}
bool subsetSum(vector<int>& arr, int sum) {

int n = arr.size();
vector<vector<bool>> dp(n + 1, vector<bool>(sum + 1, false));
for (int i = 0; i <= n; ++i) {

dp[i][0] = true;
}
for (int i = 1; i <= n; ++i) {

DEPARTMENT OF
for (int j = 1; j <= sum; ++j) {

if (arr[i - 1] <= j) {
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - arr[i - 1]];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
if (!dp[n][sum]) {
return false;
}
vector<int> subset;
cout << "Subsets with the given sum are:" << endl;
printSubsets(arr, dp, n, sum, subset);
return true;
}
int main() {
vector<int> arr = {3, 34, 4, 12, 5, 2};
int sum = 9;
if (!subsetSum(arr, sum)) {
cout << "No subset with the given sum" << endl;
}
return 0;
}
DEPARTMENT OF
4. Output
5. Time Complexity :
O(n * sum) + O(2^n)
6. Learning Outcome
• Dynamic Programming concepts and how to apply them to solve problems.
• The Subset Sum Problem and how to determine if a subset with a given sum
exists within a set.
• How to analyze the time and space complexity of a dynamic programming
algorithm.
• Improved understanding of two-dimensional arrays in C++ and how to use
them for dynamic programming tables.
DEPARTMENT OF
Experiment 7

1. Aim: Develop a program and analyze complexity to implement 0-1 Knapsack

using Dynamic Programming
2. Objective: To implement the 0-1 Knapsack problem using dynamic

programming by constructing a solution that maximizes the total value of
selected items while ensuring the total weight does not exceed the given
capacity. Analyze the time and space complexity of the solution.
3. Algorithm:
Step 1:- Create a DP Table:
 Let dp[i][w] be a 2D array where i represents the first i items and w

represents the weight capacity.
 dp[i][w] will store the maximum value that can be obtained with
capacity w using the first i items.
Step 2:- Initialization:
 For i = 0 (no items), dp[0][w] = 0 for all w because no value can

be obtained with no items.
 For w = 0, dp[i][0] = 0 for all i because no value can be obtained
with zero capacity.
Step 3:- Filling the DP Table:
 For each item i from 1 to n:

o For each capacity w from 1 to W:
 If the weight of the current item wt[i-1] is less than or equal to w, we
can either:
1. Include the item: val[i-1] + dp[i-1][w - wt[i-1]]
2. Exclude the item: dp[i-1][w]
 Take the maximum of both choices:
dp[i][w]=max (dp[i−1][w],val[i−1]+dp[i−1][w−wt[i−1]])dp[i][w] =
DEPARTMENT OF
\max(dp[i-1][w], val[i-1] + dp[i-1][w - wt[i-
1]])dp[i][w]=max(dp[i−1][w],val[i−1]+dp[i−1][w−wt[i−1]])
 If the weight of the current item is greater than w, exclude the item:
dp[i][w]=dp[i−1][w]dp[i][w] = dp[i-1][w]dp[i][w]=dp[i−1][w]
Step 4:- Return the Result:
 The maximum value that can be put in the knapsack is found in

dp[n][W].
#include <iostream>
#include <vector>
// Function to return the maximum value that can be put in a knapsack of

capacity W
int knapsack(int W, vector<int>& wt, vector<int>& val, int n) {
vector<vector<int>> dp(n+1, vector<int>(W+1, 0));
// Build table dp[][] in bottom-up manner

for (int i = 1; i <= n; i++) {
for (int w = 1; w <= W; w++) {
if (wt[i-1] <= w) {
dp[i][w] = max(dp[i-1][w], val[i-1] + dp[i-1][w - wt[i-1]]);
} else {
dp[i][w] = dp[i-1][w];
}
}
}
// The maximum value in the knapsack with capacity W

return dp[n][W];
}
int main() {
// Input values
vector<int> val = {60, 100, 120};
vector<int> wt = {10, 20, 30};
int W = 50;
int n = val.size();
// Descriptive Output
DEPARTMENT OF
cout << "---------------------------\n";
cout << " 0-1 KNAPSACK PROBLEM \n";
cout << "---------------------------\n\n";
cout << "Item Details:\n";

cout << "--------------------------------\n";
cout << "Item | Weight | Value\n";
cout << "--------------------------------\n";
for (int i = 0; i < n; i++) {
cout << " " << i+1 << " | " << wt[i] << " | " << val[i] << "\n";
}
cout << "\nMaximum Capacity of Knapsack: " << W << "\n";

cout << "--------------------------------\n\n";
int result = knapsack(W, wt, val, n);
cout << "--------------------------------\n";

cout << "Maximum Value that can be placed in the knapsack = " << result
<< "\n";
cout << "--------------------------------\n";
return 0;
}
5. Output:
DEPARTMENT OF
6. Time Complexity: O(n * W), where n is the number of items and W is the
capacity of the knapsack. This is because we fill the DP table of size n × W.
Space Complexity: O(n * W) for the DP table.
 Dynamic Programming Concept: Learned how to optimize the 0-1
Knapsack problem using dynamic programming to reduce time complexity.
 Table-based Approach: Understood the use of a 2D table to store
intermediate results and build the solution bottom-up.
 Code Presentation: Gained insights into making program output more
readable and professional through structured formatting.
DEPARTMENT OF
Experiment 8

1. Aim: Develop a program and analyze complexity to find shortest paths in a

graph with positive edge weights using Dijkstra’s algorithm.
2. Objective: To implement and analyze the efficiency of Dijkstra’s algorithm for

finding the shortest paths in a graph with positive edge weights. The goal is to
evaluate the algorithm's time complexity based on the data structure used for the
priority queue (e.g., binary heap or Fibonacci heap).
3. Algorithm:
Step1:- Initialize:
 Create a distance array dist[] and set all values to infinity (∞) except for
the source node, which is set to 0.
 Use a priority queue (min-heap) to store nodes with their current known
shortest distance.
Step 2:- Push Source:
 Insert the source node into the priority queue with a distance of 0.
Step 3:- While Queue is Not Empty:
 Extract the node u with the minimum distance from the priority queue.
 For each neighboring node v of u, calculate the tentative distance to v
through u.
 If this distance is smaller than the current distance in dist[v], update
dist[v] and insert v into the priority queue with the new distance.
Step 4:- Repeat:
 Continue this process until the priority queue is empty.
Step 5:- Result:

DEPARTMENT OF
 At the end, dist[] contains the shortest distance from the source node to all
other nodes.
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
typedef pair<int, int> PII; // Pair to store (distance, vertex)
// Dijkstra's algorithm to find the shortest paths from a source node

vector<int> dijkstra(int source, const vector<vector<PII>>& graph, int V) {
priority_queue<PII, vector<PII>, greater<PII>> pq; // Min-heap priority
queue
vector<int> dist(V, INT_MAX); // Initialize distances to infinity
dist[source] = 0; // Distance to the source is 0

pq.push({0, source}); // Push the source into the priority queue
while (!pq.empty()) {
int u = pq.top().second; // Get the vertex with the smallest distance
pq.pop();
// Traverse all adjacent vertices of u

for (const auto& neighbor : graph[u]) {
int v = neighbor.second;
int weight = neighbor.first;
// Relaxation step
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.push({dist[v], v}); // Push updated distance to the priority queue
}
}
}
return dist; // Return the shortest distance to all vertices

}
DEPARTMENT OF
int main() {
int V = 5; // Number of vertices
vector<vector<PII>> graph(V);
// Adding edges (weight, vertex)

graph[0].push_back({10, 1});
int source = 0; // Set the source node
// Run Dijkstra's algorithm

vector<int> distances = dijkstra(source, graph, V);
// Output the shortest distances from the source node

cout << "Shortest distances from node " << source << ":\n";
for (int i = 0; i < V; ++i) {
cout << "Node " << i << " : " << distances[i] << "\n";
}
return 0;
}
5. Output:
DEPARTMENT OF
6. Time Complexity:
Using Binary Heap: O((V + E) log V), where V is the number of vertices and E
is the number of edges.
Using Fibonacci Heap: O(E + V log V).
Space Complexity:
The overall space complexity of Dijkstra’s algorithm is O(V + E), where V is
the number of vertices and E is the number of edges.
1. Understanding of Dijkstra's Algorithm: You will learn how to implement
and apply Dijkstra’s algorithm to find the shortest paths in graphs with
positive edge weights, utilizing a priority queue for efficiency.
2. Time and Space Complexity Analysis: You will gain insights into
analyzing the time complexity (O((V + E) log V) using a binary heap) and
space complexity (O(V + E)) of the algorithm.
3. Graph Representation: You will understand how to represent graphs
efficiently using adjacency lists and handle shortest path problems with real-
world applications.
DEPARTMENT OF
Experiment 9

1. Aim: Develop a program and analyze complexity to find all occurrences of a

pattern P in a given strings.
2. Objective: To develop a program to find all occurrences of a pattern P in a

string S, and analyze the time complexity based on different algorithms (e.g.,
brute force, KMP, or Boyer-Moore). Compare performance for varying pattern
lengths and input sizes.
3. Algorithm:
Step 1: Build LPS Array (Longest Prefix Suffix)
 Initialize an array lps[] of size m (length of P).

 Set lps[0] = 0 and iterate through P to fill the rest of the lps[] values, where
lps[i] represents the longest proper prefix which is also a suffix for the
substring P[0…i].
 Time complexity: O(m).
Step 2: Start Matching P in S
 Set two pointers, i = 0 for S and j = 0 for P.

 Traverse through the string S. If P[j] == S[i], increment both i and j.
 If there is a mismatch, use lps[] to update j (i.e., set j = lps[j-1]), without
resetting i.
Step 3: Record Occurrence
 If j reaches the length of P (i.e., j == m), a full pattern match is found. Record
the index i - j as the occurrence.
 Then, reset j = lps[j-1] to continue searching.
Step 4: End the Search
 Continue until i traverses the entire string S.

DEPARTMENT OF
#include <iostream>
#include <vector>
// Function to build the LPS (Longest Prefix Suffix) array

vector<int> buildLPS(const string& P) {
int m = P.length();
vector<int> lps(m, 0);
int len = 0; // length of previous longest prefix suffix
int i = 1;
while (i < m) {
if (P[i] == P[len]) {
len++;
lps[i] = len;
i++;
} else {
if (len != 0) {
len = lps[len - 1]; // use previous lps
} else {
lps[i] = 0;
i++;
}
}
}
return lps;
}
// KMP search function to find all occurrences of P in S

void KMPsearch(const string& S, const string& P) {
int n = S.length();
int m = P.length();
vector<int> lps = buildLPS(P);
int i = 0; // index for S

int j = 0; // index for P
bool found = false; // flag to check if any pattern is found
cout << "Searching for pattern: \"" << P << "\" in string: \"" << S << "\"\n";
cout << "--------------------------------------------\n";
DEPARTMENT OF
while (i < n) {
if (P[j] == S[i]) {
i++;
j++;
}
if (j == m) {
found = true;
cout << ">> Pattern found at index: " << (i - j) << " <<\n";
j = lps[j - 1]; // get the index from LPS array
} else if (i < n && P[j] != S[i]) {
if (j != 0) {
j = lps[j - 1]; // use the LPS array
} else {
i++;
}
}
}
if (!found) {
cout << ">> No occurrences of the pattern found. <<\n";
}
cout << "--------------------------------------------\n";

}
int main() {
string S = "ababcababcababc";
string P = "ababc";
KMPsearch(S, P);
return 0;
}
DEPARTMENT OF
5. Output:
6. Time Complexity: The overall time complexity is: O(n + m)

Space Complexity: The overall space complexity is: O(m).
1. Efficient String Matching:
You will understand how the KMP algorithm efficiently finds all occurrences
of a pattern P in a string S, avoiding redundant comparisons.
2. LPS Array Utility:
You will learn how to construct and utilize the Longest Prefix Suffix (LPS)
array to skip unnecessary comparisons, optimizing the search process.
3. Time and Space Trade-offs:
You will gain insight into analyzing algorithms for both time and space
complexity, understanding why KMP achieves linear time complexity O(n +
m) with only O(m) space overhead.

DAA 1 Merged

Uploaded by

Copyright:

Available Formats

DAA 1 Merged

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

DAA 1 Merged

Uploaded by

Copyright:

Available Formats

DEPARTMENT OF

COMPUTER SCIENCE & ENGINEERING

void push(T data) {

1. Aim: Code implement power function in O(logn) time complexity.

long long power(long long x, long long n) {

Student Name: Zatch UID:

1. Aim: Code to find frequency of elements in a given array in O(n) time

void findFrequencies(int arr[], int n) {

while (idx < n) {

6. Time Complexity: O(n)

7. Space Complexity: O(1)

Student Name: Zatch UID:

Insertion at the End:

Deletion from the Beginning:

1. Check if List is Empty: If the list is empty, do nothing.

Deletion from the End:

1. Check if List is Empty: If the list is empty, do nothing.

Algorithm for Circular Linked List (CLL)

Insertion at the End:

1. Check if List is Empty: If the list is empty, do nothing.

Deletion from the End:

1. Check if List is Empty: If the list is empty, do nothing.

Node(int val) : data(val), prev(nullptr), next(nullptr) {}

// Insert at the beginning

// Insert at the end

// Delete from the beginning

// Delete from the end

Node(int val) : data(val), next(nullptr) {}

// Insert at the beginning

// Insert at the end

// Delete from the beginning

// Delete from the end

(Circular Linked List)

6. Time Complexity: O(1) For insertion and deletion

using namespace std;

for (int j = low; j < high; j++) {

clock_t start = clock();

return double(end - start) / CLOCKS_PER_SEC;

using namespace std;

void printSubsets(vector<int>& arr, vector<vector<bool>>& dp, int i, int

cout << "}" << endl;

if (j >= arr[i-1] && dp[i-1][j - arr[i-1]]) {

bool subsetSum(vector<int>& arr, int sum) {

for (int i = 0; i <= n; ++i) {

for (int i = 1; i <= n; ++i) {

for (int j = 1; j <= sum; ++j) {

Student Name: Zatch UID:

1. Aim: Develop a program and analyze complexity to implement 0-1 Knapsack

2. Objective: To implement the 0-1 Knapsack problem using dynamic

Step 1:- Create a DP Table:

 Let dp[i][w] be a 2D array where i represents the first i items and w

Step 2:- Initialization:

 For i = 0 (no items), dp[0][w] = 0 for all w because no value can

Step 3:- Filling the DP Table:

 For each item i from 1 to n:

Step 4:- Return the Result:

 The maximum value that can be put in the knapsack is found in

// Function to return the maximum value that can be put in a knapsack of

// Build table dp[][] in bottom-up manner

// The maximum value in the knapsack with capacity W