VIVEK SHARMA (2309005370095)
INDEX
SRNO TOPIC PAGE
NO
1 To implement the following using array as data 2 to 4
structure and analyse its time complexity
a)Insertion sort
b)Selection sort
c)Bubble sort
d)Quick sort
e)Merge Sort
2 To implement linear and binary search and analyze its 5
time complexity
3 To implement matrix chain multiplication and analyze 6
its time complexity
4 To implement longest common Subsequence and analyze its 7
time complexity
5 To implement optimal binary search tree problem and 8
analyze its time complexity
6 To implement huffman coding and analyze its time 9-10
complexity
7 To implement Dijkstra algorithm and analyze its time 11-13
complexity
8 To implement Bellman Ford algorithm and analyze its 14-15
time complexity
9 To implement DFS and BFS and analyze their time 16-17
complexities
10 To implement following string matching algorithms and 18-21
analyze its time complexity
1 | Design and Analysis of Algorithms
VIVEK SHARMA (2309005370095)
1. To implement the following using array as data
structure and analyse its time complexity
a) INSERTION SORT
public void insertionSort(int[] arr) {
for (int i = 1; i < [Link]; i++) {
int key = arr[i], j = i - 1;
while (j >= 0 && arr[j] > key)
arr[j + 1] = arr[j--];
arr[j + 1] = key;
}
}
TIME COMPLEXITY:
BEST CASE: O(N)
AVERAGE CASE: O(N2)
WORST CASE: O(N2)
SPACE COMPLEXITY: O(1)
b) SELECTION SORT
public void selectionSort(int[] arr) {
for (int i = 0; i < [Link] - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < [Link]; j++)
if (arr[j] < arr[minIdx]) minIdx = j;
int temp = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = temp;
}
}
TIME COMPLEXITY:
BEST CASE: O(N2)
AVERAGE CASE: O(N2)
WORST CASE: O(N2)
SPACE COMPLEXITY: O(1)
2 | Design and Analysis of Algorithms
VIVEK SHARMA (2309005370095)
c) BUBBLE SORT
public void bubbleSort(int[] arr) {
for (int i = 0; i < [Link] - 1; i++)
for (int j = 0; j < [Link] - i - 1; j++)
if (arr[j] > arr[j + 1]) {
int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] =
temp;
}
}
TIME COMPLEXITY:
BEST CASE: O(N)
AVERAGE CASE: O(N2)
WORST CASE: O(N2)
SPACE COMPLEXITY: O(1)
d) QUICK SORT
public void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
private int partition(int[] arr, int low, int high) {
int pivot = arr[high], i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
}
}
int temp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = temp;
return i + 1;
}
TIME COMPLEXITY:
BEST CASE: O(n log n)
AVERAGE CASE: O(n log n)
WORST CASE: O(N2)
SPACE COMPLEXITY: O(N)
3 | Design and Analysis of Algorithms
VIVEK SHARMA (2309005370095)
e) MERGE SORT
public void mergeSort(int[] arr, int l, int r) {
if (l < r) {
int m = (l + r) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
private void merge(int[] arr, int l, int m, int r) {
int n1 = m - l + 1, n2 = r - m;
int[] L = new int[n1], R = new int[n2];
[Link](arr, l, L, 0, n1);
[Link](arr, m + 1, R, 0, n2);
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
TIME COMPLEXITY:
BEST CASE: O(n log n)
AVERAGE CASE: O(n log n)
WORST CASE: O(n log n)
SPACE COMPLEXITY: O(N)
4 | Design and Analysis of Algorithms
VIVEK SHARMA (2309005370095)
2. To implement linear and binary search and analyze
the its time complexity
a)Linear Search
public int linearSearch(int[] arr, int key) {
for (int i = 0; i < [Link]; i++)
if (arr[i] == key) return i;
return -1;
}
TIME COMPLEXITY:
BEST CASE: O(1)
AVERAGE CASE: O(n)
WORST CASE: O(n)
SPACE COMPLEXITY: O(1)
b)Binary Search
public int binarySearch(int[] arr, int key) {
int low = 0, high = [Link] - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == key) return mid;
else if (arr[mid] < key) low = mid + 1;
else high = mid - 1;
}
return -1;
}
TIME COMPLEXITY:
BEST CASE: O(1)
AVERAGE CASE: O(log n)
WORST CASE: O(log n)
SPACE COMPLEXITY: O(1)
5 | Design and Analysis of Algorithms
VIVEK SHARMA (2309005370095)
3. To implement matrix chain multiplication and
analyze the its time complexity
public int matrixChainOrder(int[] dims) {
int n = [Link] - 1;
int[][] dp = new int[n][n];
for (int len = 2; len <= n; len++) {
for (int i = 0; i < n - len + 1; i++) {
int j = i + len - 1;
dp[i][j] = Integer.MAX_VALUE;
for (int k = i; k < j; k++) {
int cost = dp[i][k] + dp[k + 1][j] + dims[i] * dims[k +
1] * dims[j + 1];
if (cost < dp[i][j]) dp[i][j] = cost;
}
}
}
return dp[0][n - 1];
}
BEST CASE: O(N³)
AVERAGE CASE: O(N³)
WORST CASE: O(N³)
SPACE COMPLEXITY: O(N²)
6 | Design and Analysis of Algorithms
VIVEK SHARMA (2309005370095)
4. To implement longest common Subsequence and
analyze the its time complexity
// implemented using DP(Dynamic Programming)
public int lcs(String X, String Y) {
int m = [Link](), n = [Link]();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if ([Link](i - 1) == [Link](j - 1))
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = [Link](dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[m][n];
}
BEST CASE: O(M × N)
AVERAGE CASE: O(M × N)
WORST CASE: O(M × N)
SPACE COMPLEXITY: O(M × N)
7 | Design and Analysis of Algorithms
VIVEK SHARMA (2309005370095)
5. To implement optimal binary search tree problem
and analyze the its time complexity
public int optimalBST(int[] freq) {
int n = [Link];
int[][] cost = new int[n][n];
int[] sum = new int[n + 1];
// implemented using Dynamic programming
for (int i = 0; i < n; i++)
sum[i + 1] = sum[i] + freq[i];
for (int i = 0; i < n; i++)
cost[i][i] = freq[i];
for (int L = 2; L <= n; L++) {
for (int i = 0; i <= n - L; i++) {
int j = i + L - 1;
cost[i][j] = Integer.MAX_VALUE;
int totalFreq = sum[j + 1] - sum[i];
for (int r = i; r <= j; r++) {
int left = (r > i) ? cost[i][r - 1] : 0;
int right = (r < j) ? cost[r + 1][j] : 0;
cost[i][j] = [Link](cost[i][j], left + right +
totalFreq);
}
}
}
return cost[0][n - 1];
}
BEST CASE: O(N²)
AVERAGE CASE: O(N³)
WORST CASE: O(N³)
SPACE COMPLEXITY: O(N²)
8 | Design and Analysis of Algorithms
VIVEK SHARMA (2309005370095)
6. To implement huffman coding and analyze the its
time complexity
import [Link].*;
class Node {
int freq;
String symbol;
Node left, right;
String huff = "";
public Node(int freq, String symbol) {
[Link] = freq;
[Link] = symbol;
[Link] = null;
[Link] = null;
}
public boolean lt(Node nxt) {
return [Link] < [Link];
}
}
public class HuffmanCoding {
public static void printNodes(Node node, String val) {
String newVal = val + [Link];
if ([Link] != null) {
printNodes([Link], newVal);
}
if ([Link] != null) {
printNodes([Link], newVal);
}
if ([Link] == null && [Link] == null) {
[Link]([Link] + " -> " + newVal);
}
}
public static void main(String[] args) {
String[] chars = {'a', 'b', 'c', 'd', 'e', 'f'};
int[] freq = {6, 10, 13, 15, 17, 46};
PriorityQueue<Node> nodes = new
PriorityQueue<>([Link](n -> [Link]));
9 | Design and Analysis of Algorithms
VIVEK SHARMA (2309005370095)
for (int i = 0; i < [Link]; i++) {
[Link](new Node(freq[i], [Link](chars[i])));
}
while ([Link]() > 1) {
Node left = [Link]();
Node right = [Link]();
[Link] = "0";
[Link] = "1";
Node newNode = new Node([Link] + [Link], [Link] +
[Link]);
[Link] = left;
[Link] = right;
[Link](newNode);
}
printNodes([Link](), "");
}
}
a -> 1100
b -> 1101
c -> 100
d -> 101
e -> 111
f -> 0
BEST CASE: O(N²)
AVERAGE CASE: O(N³)
WORST CASE: O(N³)
SPACE COMPLEXITY: O(N²)
10 | Design and Analysis of Algorithms
VIVEK SHARMA (2309005370095)
7. To implement Dijkstra algorithm and analyze the
its time complex
import [Link].*;
class Dijkstra {
// Define the Graph class
static class Graph {
int vertices;
LinkedList<Edge>[] adjList;
public Graph(int vertices) {
[Link] = vertices;
adjList = new LinkedList[vertices];
for (int i = 0; i < vertices; i++) {
adjList[i] = new LinkedList<>();
}
}
public void addEdge(int u, int v, int weight) {
adjList[u].add(new Edge(v, weight));
adjList[v].add(new Edge(u, weight)); // for undirected graph
}
}
static class Edge {
int dest, weight;
public Edge(int dest, int weight) {
[Link] = dest;
[Link] = weight;
}
}
// Dijkstra algorithm to find shortest path from source to all other
vertices
public static void dijkstra(Graph graph, int source) {
int[] dist = new int[[Link]];
[Link](dist, Integer.MAX_VALUE);
dist[source] = 0;
PriorityQueue<int[]> pq = new
PriorityQueue<>([Link](a -> a[1]));
[Link](new int[]{source, 0});
11 | Design and Analysis of Algorithms
VIVEK SHARMA (2309005370095)
while (![Link]()) {
int[] current = [Link]();
int u = current[0];
int currentDist = current[1];
if (currentDist > dist[u]) {
continue;
}
for (Edge edge : [Link][u]) {
int v = [Link];
int weight = [Link];
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
[Link](new int[]{v, dist[v]});
}
}
}
// Print the shortest distance from source to all other vertices
for (int i = 0; i < [Link]; i++) {
[Link]("Distance from " + source + " to " + i +
": " + dist[i]);
}
}
public static void main(String[] args) {
Graph graph = new Graph(9);
[Link](0, 1, 4);
[Link](0, 7, 8);
[Link](1, 2, 8);
[Link](1, 7, 11);
[Link](2, 3, 7);
[Link](2, 5, 4);
[Link](2, 8, 2);
[Link](3, 4, 9);
[Link](3, 5, 14);
[Link](4, 5, 10);
[Link](5, 6, 2);
[Link](6, 7, 1);
[Link](6, 8, 6);
[Link](7, 8, 7);
dijkstra(graph, 0);
}
}
12 | Design and Analysis of Algorithms
VIVEK SHARMA (2309005370095)
BEST CASE: O((V + E) * log V)
AVERAGE CASE: O((V + E) * log V)
WORST CASE: O((V + E) * log V)
SPACE COMPLEXITY: O(V + E)
13 | Design and Analysis of Algorithms
VIVEK SHARMA (2309005370095)
8. To implement Bellman Ford algorithm and analyze
its time complexity
import [Link].*;
class BellmanFord {
static class Edge {
int source, dest, weight;
public Edge(int source, int dest, int weight) {
[Link] = source;
[Link] = dest;
[Link] = weight;
}
}
public static void bellmanFord(List<Edge> edges, int V, int source) {
// Step 1: Initialize distances
int[] dist = new int[V];
[Link](dist, Integer.MAX_VALUE);
dist[source] = 0;
// Step 2: Relax edges repeatedly
for (int i = 1; i < V; i++) {
for (Edge edge : edges) {
if (dist[[Link]] != Integer.MAX_VALUE &&
dist[[Link]] + [Link] < dist[[Link]]) {
dist[[Link]] = dist[[Link]] + [Link];
}
}
}
// Step 3: Check for negative weight cycles
for (Edge edge : edges) {
if (dist[[Link]] != Integer.MAX_VALUE &&
dist[[Link]] + [Link] < dist[[Link]]) {
[Link]("Graph contains negative weight
cycle");
return;
}
}
// Print the shortest distances
[Link]("Vertex Distance from Source (" + source +
"):");
for (int i = 0; i < V; i++) {
[Link](i + " -> " + (dist[i] == Integer.MAX_VALUE
? "INF" : dist[i]));
14 | Design and Analysis of Algorithms
VIVEK SHARMA (2309005370095)
}
}
public static void main(String[] args) {
List<Edge> edges = new ArrayList<>();
[Link](new Edge(0, 1, -1));
[Link](new Edge(0, 2, 4));
[Link](new Edge(1, 2, 3));
[Link](new Edge(1, 3, 2));
[Link](new Edge(1, 4, 2));
[Link](new Edge(3, 2, 5));
[Link](new Edge(3, 1, 1));
[Link](new Edge(4, 3, -3));
int V = 5; // Number of vertices
int source = 0;
// Run Bellman-Ford Algorithm
bellmanFord(edges, V, source);
}
}
BEST CASE: O(V * E)
AVERAGE CASE: O(V * E)
WORST CASE: O(V * E)
SPACE COMPLEXITY: O(V + E)
15 | Design and Analysis of Algorithms
VIVEK SHARMA (2309005370095)
9. To implement DFS and BFS and analyze their time
complexities
a.Graph representation
import [Link].*;
class Graph {
private int V; // Number of vertices
private LinkedList<Integer>[] adj; // Adjacency list
Graph(int V) {
this.V = V;
adj = new LinkedList[V];
for (int i = 0; i < V; i++)
adj[i] = new LinkedList<>();
}
void addEdge(int u, int v) {
adj[u].add(v);
adj[v].add(u); // Remove this for directed graph
}
b.BFS
void bfs(int start) {
boolean[] visited = new boolean[V];
Queue<Integer> queue = new LinkedList<>();
visited[start] = true;
[Link](start);
[Link]("BFS Traversal: ");
while (![Link]()) {
int u = [Link]();
[Link](u + " ");
for (int v : adj[u]) {
if (!visited[v]) {
visited[v] = true;
[Link](v);
}
}
}
[Link]();
}
16 | Design and Analysis of Algorithms
VIVEK SHARMA (2309005370095)
c.DFS
void dfs(int start) {
boolean[] visited = new boolean[V];
[Link]("DFS Traversal: ");
dfsUtil(start, visited);
[Link]();
}
private void dfsUtil(int u, boolean[] visited) {
visited[u] = true;
[Link](u + " ");
for (int v : adj[u]) {
if (!visited[v])
dfsUtil(v, visited);
}
}
}
//Main method
public class Main {
public static void main(String[] args) {
Graph g = new Graph(6);
[Link](0, 1);
[Link](0, 2);
[Link](1, 3);
[Link](1, 4);
[Link](2, 5);
[Link](0); // Start BFS from node 0
[Link](0); // Start DFS from node 0
}
}
BFS:
BEST CASE: O(V + E)
AVERAGE CASE: O(V + E)
WORST CASE: O(V + E)
SPACE COMPLEXITY: O(V) (queue + visited array)
DFS:
BEST CASE: O(V + E)
AVERAGE CASE: O(V + E)
WORST CASE: O(V + E)
SPACE COMPLEXITY: O(V) (stack depth + visited array)
17 | Design and Analysis of Algorithms
VIVEK SHARMA (2309005370095)
10. To implement following string matching algorithms
and analyze its time complexity
a.Naive
class NaiveSearch {
static void search(String text, String pattern) {
int n = [Link]();
int m = [Link]();
for (int i = 0; i <= n - m; i++) {
int j;
for (j = 0; j < m; j++) {
if ([Link](i + j) != [Link](j))
break;
}
if (j == m)
[Link]("Pattern found at index " + i);
}
}
public static void main(String[] args) {
search("ABABDABACDABABCABAB", "ABABCABAB");
}
}
BEST CASE: O(n)
AVERAGE CASE: O(n * m)
WORST CASE: O(n * m)
SPACE COMPLEXITY: O(1)
18 | Design and Analysis of Algorithms
VIVEK SHARMA (2309005370095)
b.Rabin Karp
class RabinKarp {
static final int d = 256; // number of characters in input alphabet
static final int q = 101; // a prime number
static void search(String text, String pattern) {
int m = [Link]();
int n = [Link]();
int p = 0, t = 0, h = 1;
for (int i = 0; i < m - 1; i++)
h = (h * d) % q;
for (int i = 0; i < m; i++) {
p = (d * p + [Link](i)) % q;
t = (d * t + [Link](i)) % q;
}
for (int i = 0; i <= n - m; i++) {
if (p == t) {
int j;
for (j = 0; j < m; j++) {
if ([Link](i + j) != [Link](j))
break;
}
if (j == m)
[Link]("Pattern found at index " + i);
}
if (i < n - m) {
t = (d * (t - [Link](i) * h) + [Link](i + m)) %
q;
if (t < 0)
t = (t + q);
}
}
}
public static void main(String[] args) {
search("ABABDABACDABABCABAB", "ABABCABAB");
}
}
BEST CASE: O(n + m)
AVERAGE CASE: O(n + m)
WORST CASE: O(n * m)
SPACE COMPLEXITY: O(1)
19 | Design and Analysis of Algorithms
VIVEK SHARMA (2309005370095)
c.Knuth Morris Pratt
class KMP {
static void computeLPSArray(String pattern, int[] lps) {
int len = 0;
lps[0] = 0;
int i = 1;
while (i < [Link]()) {
if ([Link](i) == [Link](len)) {
len++;
lps[i] = len;
i++;
} else {
if (len != 0) {
len = lps[len - 1];
} else {
lps[i] = 0;
i++;
}
}
}
}
static void search(String text, String pattern) {
int m = [Link]();
int n = [Link]();
int[] lps = new int[m];
computeLPSArray(pattern, lps);
int i = 0, j = 0;
while (i < n) {
if ([Link](j) == [Link](i)) {
i++;
j++;
}
if (j == m) {
[Link]("Pattern found at index " + (i - j));
j = lps[j - 1];
} else if (i < n && [Link](j) != [Link](i)) {
if (j != 0)
j = lps[j - 1];
else
i++;
20 | Design and Analysis of Algorithms
VIVEK SHARMA (2309005370095)
}
}
}
public static void main(String[] args) {
search("ABABDABACDABABCABAB", "ABABCABAB");
}
}
BEST CASE: O(n)
AVERAGE CASE: O(n)
WORST CASE: O(n + m)
SPACE COMPLEXITY: O(m)
21 | Design and Analysis of Algorithms