LABORATORY MANUAL

DESIGN AND ANALYSIS OF ALGORITHMS

(CSP-350)

Academic Year : 2023-24

Course : B.Tech
Semester : 5th

(Instructor Version)

Prepared by: Dr. Bharat Bhushan

Department of Computer Science and Engineering

School of Engineering & Technology, Sharda University
Greater Noida, Uttar Pradesh 201310
www.sharda.ac.in
The document is for internal circulation only.

Copyright © 2023 Sharda University. All rights reserved.

All materials on these pages are copyrighted by the Sharda University. All rights reserved. Reproduction,
modification, retransmission, in any form or by any means, electronic, mechanical or otherwise, for
reasons other than personal use, is strictly prohibited without prior written permission.

First Edition
January,2021

Published by:
Department of Computer Science and Engineering
School of Engineering and Technology
SHARDA UNIVERSITY
Page 2 of 57
 PREFACE
The Department of Computer Science and Engineering, School of Engineering & Technology,
Sharda University has prepared this laboratory manual. It is designed as an instruction book for
purposes listed in order of importance as follows:
1. To provide techniques, procedures and precautions related to the experiments.
2. To provide the laboratory safety and general rules and instructions.
3. To provide a general reference book that will give information which will assist in the
understanding of details about the laboratory and the experiment to be performed.

The manual is prepared with the idea that the revisions must be made periodically in order to
have the available text that represents the experiments. It has been tried to maintain the format
with diagrams, tables and illustrations.
It is believed that the information in the manual will enhance the practical skills of the students
along with developing the base of the subject.
Any suggestions and comments for further improvement of this manual will be gratefully
acknowledged.

Authors
Department of Computer Science and Engineering

Page 4 of 57
Table of Contents
Vision and Mission of the University.....................................................................................................................
Vision and Mission of the Department...................................................................................................................
Program Educational Objectives............................................................................................................................
Program Outcomes.................................................................................................................................................
General Rules and Instructions:.............................................................................................................................
Instruction for Students..........................................................................................................................8
General discipline in the Lab..................................................................................................................8
Preparations and Performance..............................................................................................................8
Lab Report Guidelines.............................................................................................................................9
Safety Measures.....................................................................................................................................................
Experimental Setup Details................................................................................................................................
Software Requirements........................................................................................................................10
Hardware Requirements.......................................................................................................................10
Syllabus.................................................................................................................................................................
CO and PO Mapping.............................................................................................................................................
List of Experiments.............................................................................................................................................
Write a program to find the root to the quadratic equations.............................................................................18
An ATM contains Indian Currency notes of 100,200,500 and 2000. Once the user enters amount to be withdrawn.
Display the minimum number of notes required to dispense from the ATM.......................................................19
Solve the following system of linear equations using the linalg module of NumPy. Also check correctness of the
solution.....................................................................................................................................................20
Write a program that plots a comparative graph of X2 vs Xx.............................................................................21
Vision and Mission of the University

Vision of the University

To serve the society by being a global University of higher learning in pursuit of academic
excellence, innovation and nurturing entrepreneurship.
Mission of the University
1. Transformative educational experience.
2. Enrichment by educational initiative that encourage global outlook.
3. Develop research, support disruptive innovations and accelerate entrepreneurship.
4. Seeking beyond boundaries.

Page 6 of 57
Vision and Mission of Department

Vision of the Department

To be recognized as the fountainhead of excellence in technical knowledge and research in
computer science and engineering to attract students and scholars across the globe.
Mission of the Department
1. To strengthen core competency of students to be successful, ethical, effective problem
solver in Computer Science & Engineering through analytical learning.
2. To promote interdisciplinary research & innovation-based activities in emerging areas of
technology globally.
3. To facilitate and foster the industry-academia collaboration to enhance entrepreneurship
skills and acquaintance with corporate culture.
4. To inculcate in them a higher degree of social consciousness and moral values towards
solving interdisciplinary societal problems using industry-academia collaboration
Program Educational Objectives

Page 8 of 57
Program Outcomes

Engineering knowledge: Apply the knowledge of mathematics, science,

PO1 engineering fundamentals, and an engineering specialization to the solution of
complex engineering problems.
Problem analysis: Identify, formulate, review research literature, and analyze
PO2 complex engineering problems reaching substantiated conclusions using first
principles of mathematics, natural sciences, and engineering sciences.
Design/development of solutions: Design solutions for complex engineering
PO3 problems and design system components or processes that meet the specified
needs with appropriate consideration for the public health and safety, and the
cultural, societal, and environmental considerations.
Conduct investigations of complex problems: Use research-based knowledge
PO4 and research methods including design of experiments, analysis and interpretation
of data, and synthesis of the information to provide valid conclusions
Modern tool usage: Create, select, and apply appropriate techniques, resources,
PO5 and modern engineering and IT tools including prediction and modeling to
complex engineering activities with an understanding of the limitations.
The engineer and society: Apply reasoning informed by the contextual
PO6 knowledge to assess societal, health, safety, legal and cultural issues and the
consequent responsibilities relevant to the professional engineering practice.
Environment and sustainability: Understand the impact of the professional
PO7 engineering solutions in societal and environmental contexts, and demonstrate the
knowledge of, and need for sustainable development
PO8 Ethics: Apply ethical principles and commit to professional ethics and
responsibilities and norms of the engineering practice.

PO9 Individual and team work: Function effectively as an individual, and as a

member or leader in diverse teams, and in multidisciplinary settings.
Communication: Communicate effectively on complex engineering activities
PO10 with the engineering community and with society at large, such as, being able to
comprehend and write effective reports and design documentation, make effective
presentations, and give and receive clear instructions.
Project management and finance: Demonstrate knowledge and understanding
PO11 of the engineering and management principles and apply these to one’s own work,
as a member and leader in a team, to manage projects and in multidisciplinary
environments.
Life-long learning: Recognize the need for, and have the preparation and ability
PO12 to engage in independent and life-long learning in the broadest context of
technological change.
General Rules and Instructions:
Instruction for Students

To complete all the experiments within time, to understand them completely and effectively, each
student must obey the following points:

General discipline in the Lab

Discipline is always given the highest precedence for maintaining the quality standard of your lab. Any
misconduct will be seriously dealt with and immediately responded without prior notification.
To ensure a pleasant, productive, and comfortable experience for all of our users, you are directed to
adhere to the following guidelines:
 Students will not be allowed after ten minutes from the scheduled time.
 Students will not leave the lab till the period is over.
 Attendance in the lab class is compulsory.
 Students should maintain silence while performing the experiments.
 Students should not attend a different lab group/section other than the one assigned at the
beginning of the session.
 Please help us to keep the facility (Equipment’s- etc.) clean by discarding trash in the
receptacles.
 Please respect the sensitivities of your peers and refrain from viewing any inappropriate
content.
 Any attempt on Hacking information will be reciprocated with serious consequences.

Please abide by the rules and make appropriate use of all facilities. Users found to be damaging
computer configurations, accessing content or systems illegally or attempting to compromise security
may be deprived of the facility or will be fined.

Preparations and Performance

 Students should come to the lab thoroughly prepared on the experiments they are assigned to
perform on that day.
 Faculty may check their preparation and understanding of the experiments. If not found
satisfactory, students may be debarred from doing the experiments.

Page 10 of 57
 Students should save the results (Screenshots) of their programs performed during lab session.
 Students must bring the lab manual on each practical class with Algorithm, Flowchart, Program
and Results (Screenshots) of the last experiments performed complete in all respect.
 Students without lab manual will not be allowed to do the experiments and hence lose their
attendance.
Lab Report Guidelines

 Each student is required to write a complete report of the experiment he has performed and
bring to lab class for evaluation in the next working lab.
 Report should be written very clearly and lab record should be maintained neatly.
 the lab report must contain
‒ Duly completed title page
‒ Theory/ Algorithms/ Flowcharts
‒ Source Code of Program
‒ Screenshots of Results

Safety Measures

 Do not leave your personal belongings unattended. The Computing Labs and Staff will not be
responsible for any lost personal items.

 In the case of fire, please follow the standard instructions.

Page 12 of 57
Experimental Setup Details

Software Requirements

Turbo C 2.0/ Turbo C++3.0+

Hardware Requirements

No specific requirements. Any computer Hardware capable of running DOS can be used for this
course.

Online platform

Codeblocks
Syllabus

School: SET Batch:

Program: B-Tech Current Academic Year: 2022-2023
Branch: CSE Semester: V
1 Course Code CSP 350
2 Course Title Design and Analysis of Algorithm lab
3 Credits
4 Contact 0-0-2
Hours
(L-T-P)
Course Status Compulsory/Elective
5 Course Objective of this course is to
Objective 1. Reinforce basic design concepts (e.g., pseudocode,
specifications, top-down design)
2. Knowledge of algorithm design strategies
3. Familiarity with an assortment of important algorithms.
4. Enable students to analyze time and space complexity
6 Course Students will be able to:
Outcomes CO1: Calculate time complexity of searching algorithm
CO2: Write program based on dynamic programming.
(same as CO3: Apply greedy algorithm to any problem
theory course) CO4: Develop program based on advanced data structure
CO5: Design a program based on different string matching
algorithm
CO6: Implement real world problem based on greedy and dynamic
algorithm
7 Course This course introduces concepts related to the design and analysis of
Description algorithms. Specifically, it discusses recurrence relations, and
illustrates their role in asymptotic and probabilistic analysis of
algorithms. It covers in detail greedy strategies divide and conquer
techniques, dynamic programming and max flow - min cut theory for
designing algorithms, and illustrates them using a number of well-
known problems and applications.
8 Outline syllabus CO Mapping
Unit 1 Practical based on Searching and sorting
1. WAP to demonstrate the concept of Linear CO1
and Binary Search
2. WAP to implement Merge sort
3. WAP to implement Quick Sort

Unit 2 Practical based on Dynamic Programming

1. WAP to implement Matrix Chain CO2, CO6
Multiplication problem
2. WAP to demonstrate the concept of
Longest Common Subsequence(LCS)
3. WAP to demonstrate concept of 0 – 1
Knapsack Problem

Unit 3 Practical based on Greedy Programming

Page 14 of 57
 1. WAP to demonstrate concept of Minimum CO3, CO6
Spanning Tree(Prim’s Algorithm)
2. WAP to demonstrate concept of Fractional
Knapsack Problem
3. WAP to implement single source shortest
problem using Dijkstra’s Algorithm

Unit 4 Practical based on Advance concepts

1. WAP to demonstrate concept of Red Black CO4
Tree insertion and Deletion
Unit 5 Practical based on String Matching
1. WAP to demonstrate the concept of Naïve CO5
String matching algorithm.
2. WAP to demonstrate the concept of Robin
Karp Algorithm.

Mode of Jury/Practical/Viva
examination
Weightage CA MTE ETE
Distribution 60% 0% 40%
Text book/s* - Cormen et al., “Introduction of Computer
Algorithms”, Prentice Hall India
Other 1. Sahni et al., “Fundamentals of Computer
References Algorithms”, Galgotia Publications.
2. Hopcroft A, The Design And Analysis
Computer Algorithms, Addison Wesley
CO, PO & PSO Mapping

S. Course Outcome Program Outcomes (PO) & Program Specific

No. Outcomes (PSO)
1. Calculate time complexity of searching PO1,PO2,PO3,PO4,PO5,PO9, PSO1, PSO2,
algorithm PSO3
2. Write program based on dynamic PO1,PO2,PO3,PO4,PO5,PO9, PSO1, PSO2,
programming PSO3
3. Apply greedy algorithm to any problem PO1,PO2,PO3,PO5,PO9, PSO1, PSO2
4. Develop program based on advanced data PO1,PO2,PO3,PO4,PO5,PO9, PSO1, PSO2,
structure PSO3
5. Design a program based on different PO1,PO2,PO3,PO4,PO5,PO9, PSO1, PSO2,
string-matching algorithm PSO3
6. Implement real world problem based on PO1,PO2,PO3,PO4,PO5,PO9, PSO1, PSO2,
greedy and dynamic algorithm PSO3

PO and PSO mapping with level of strength for Course Name-Design and Analysis of Algorithms
(Course Code CSP 350)

P
PO PO PO PO PO PO PO PO PO1 PO1 PO1 PSO PSO PSO
Cos O
2 3 4 5 6 7 8 9 0 1 2 1 2 3
1
CO1 2 3 1 2 - -- -- - 2 - - - 3 2 2
CO2 2 2 2 2 - -- -- - 3 - - - 2 3 2
CO3 2 1 2 - - -- -- - 1 - - - 3 2 -
CO4 1 2 2 3 - -- -- - 2 - - - 2 2 2
CO5 3 3 1 3 - - - - 3 - - - 2 1 3
CO6 2 2 3 2 2 - - -- 2 - - - 3 2 -

Average of non-zeros entry in following table.

Cour
Course PO PO PO PO PO PO PO PO PO PO PO PO PS PS PS
se
Name 1 2 3 4 5 6 7 8 9 10 11 12 O1 O2 O3
Code

Design
CSP and
2.5 2.7 2.5 2.4 2 - - - 1.8 - - - 2.5 2.3 2.2
350 Analysis
of
Algorith
ms Lab

Strength of Correlation

1. Addressed to Slight (Low=1) extent 2. Addressed to Moderate (Medium=2) extent

3. Addressed to Substantial (High=3) extent

Page 16 of 57
 SCHOOL OF ENGINEERING & TECHNOLOGY DEPARTMENT
OF COMPUTER SCIENCE AND ENGINEERING

COURSE TITLE L T P C
COURSE DESIGN & ANALYSIS OF ALGORITHMS LAB
CODE
LIST OF EXPERIMENT 0 0 2 1
CSP350

CO1: Calculate time complexity of searching algorithm

CO2: Apply greedy algorithm to any problem

CO3: Write program based on dynamic programming

CO4: Develop program based on advanced data structure

CO5: Design a program based on different string matching algorithm
CO6: Implement real world problem based on greedy and dynamic algorithm

LIST OF EXPERIMENTS
COURSE
S.NO. EXPERIMENT NAME
OUTCOME
Write a program to search an element in the array using Binary
1 CO1
search determine the time required to search the element.
Write a program to sort given set of numbers in CO1
2
ascending/descending order using Quick Sort.
Write a program to sort given set of numbers in CO1
3 ascending/descending order using Merge Sort and determine
the time required to sort the elements.
Write a program to sort given set of numbers in CO1
4
ascending/descending order using Counting Sort
Write a program to sort given set of numbers in CO1
5
ascending/descending order using Bucket Sort.
Write a program to sort given set of numbers in CO1
6
ascending/descending order using Radix Sort.
Write a program to implement Longest Common Subsequences CO3
7
(LCS).
8 Write a program to implement Matrix chain multiplication CO3
Write a program to implement 0/1 Knapsack problem Using CO2
9
greedy approach.
Write a program to implement fractional Knapsack problem CO2
10
Using greedy approach.
From a given vertex in a weighted connected graph, find
11 CO2
shortest paths to other vertices using Dijkstra's algorithm.
12 Write a program to implement Sum of Subset problem. CO4
 WAP to demonstrate concept of Red Black Tree insertion and CO4
13
Deletion.
Implement All-Pairs Shortest Paths Problem using Floyd's
14 CO6
algorithm.
15 Write a program to implement Naïve string matching problem CO5
16 Write a program to implement Rabin Karp Algorithm problem. CO5
You are given a string of 2N characters consisting of N ‘[‘
brackets and N ‘]’ brackets. A string is considered balanced if it
can be represented in the for S2[S1] where S1 and S2 are
17 balanced strings. We can make an unbalanced string balanced CO6
by swapping adjacent characters. Calculate the minimum
number of swaps necessary to make a string balanced.
There are N Mice and N holes are placed in a straight line. Each
hole can accommodate only 1 mouse. A mouse can stay at his
position, move one step right from x to x + 1, or move one step
18 left from x to x -1. Any of these moves consumes 1 minute. CO6
Assign mice to holes so that the time when the last mouse gets
inside a hole is minimized.

VALUE ADDED EXPERIMENTS

COURSE
S.NO. EXPERIMENT NAME
OUTCOME
A Present and analyse 5 different implementations of greedy CO6
dominating set algorithm.
B Design a novel algorithm that can schedule 2 salesmen in a CO6
network.
Hint: The two-server problem is concerned with the movement
of two servers to request points in a metric space. Consider an
offline version of the problem in a graph in which the requests
may be served in any order. A family of approximations
algorithms can be developed for this NPcomplete problem.
C Given the input n >= 2, Design and write an algorithm to CO6
implement n-ary search.
D Implement the N-queen Problem using graphical view. CO6
E Create and implement a complete graphical environment for CO6
performing Matrix Chain Multiplication.

Sign. of Course Coordinator Sign. of Lab. Coordinator Sign. of HOD

Name of Course Coordinator Name of Lab. Coordinator Prof. (Dr.) Sanjeev Kumar Pippal

Page 18 of 57
Experiment 1:

Aim: Write a program to search an element in the array using Binary search. Also, Determine the
time required to search the element.

Program:
1./*
2. * C Program to Perform Binary Search using Recursion
3. */
4.
5.#include <stdio.h>
6.
7.void binary_search(int [], int, int, int);
8.void bubble_sort(int [], int);
9.
10. int main()
11. {
12. int key, size, i;
13. int list[25];
14.
15. printf("Enter size of a list: ");
16. scanf("%d", &size);
17. printf("Enter elements\n");
18. for(i = 0; i < size; i++)
19. {
20. scanf("%d",&list[i]);
21. }
22. bubble_sort(list, size);
23. printf("\n");
24. printf("Enter key to search\n");
25. scanf("%d", &key);
26. binary_search(list, 0, size, key);
27.
28. }
29.
30. void bubble_sort(int list[], int size)
31. {
32. int temp, i, j;
33. for (i = 0; i < size; i++)
34. {
35. for (j = i; j < size; j++)
36. {
37. if (list[i] > list[j])
38. {
39. temp = list[i];
40. list[i] = list[j];
41. list[j] = temp;
42. }
43. }
44. }
45. }
46.
47. void binary_search(int list[], int lo, int hi, int key)
48. {
49. int mid;
50.
51. if (lo > hi)
52. {
53. printf("Key not found\n");
54. return;
55. }
 56. mid = (lo + hi) / 2;
57. if (list[mid] == key)
58. {
59. printf("Key found\n");
60. }
61. else if (list[mid] > key)
62. {
63. binary_search(list, lo, mid - 1, key);
64. }
65. else if (list[mid] < key)
66. {
67. binary_search(list, mid + 1, hi, key);
68. }
69. }

Output:

Page 20 of 57
Experiment 2:

Aim: Write a program to sort given set of numbers in ascending/descending order using Quick Sort.

Program:

1./*
2.* C Program to Perform Quick Sort on a set of Entries from a File
3.* using Recursion
4.*/
5.#include <stdio.h>
6.
7.void quicksort (int [], int, int);
8.
9.int main()
10. {
11. int list[50];
12. int size, i;
13.
14. printf("Enter the number of elements: ");
15. scanf("%d", &size);
16. printf("Enter the elements to be sorted:\n");
17. for (i = 0; i < size; i++)
18. {
19. scanf("%d", &list[i]);
20. }
21. quicksort(list, 0, size - 1);
22. printf("After applying quick sort\n");
23. for (i = 0; i < size; i++)
24. {
25. printf("%d ", list[i]);
26. }
27. printf("\n");
28.
29. return 0;
30. }
31. void quicksort(int list[], int low, int high)
32. {
33. int pivot, i, j, temp;
34. if (low < high)
35. {
36. pivot = low;
37. i = low;
38. j = high;
39. while (i < j)
40. {
41. while (list[i] <= list[pivot] && i <= high)
42. {
43. i++;
44. }
45. while (list[j] > list[pivot] && j >= low)
46. {
47. j--;
48. }
49. if (i < j)
50. {
51. temp = list[i];
52. list[i] = list[j];
 53. list[j] = temp;
54. }
55. }
56. temp = list[j];
57. list[j] = list[pivot];
58. list[pivot] = temp;
59. quicksort(list, low, j - 1);
60. quicksort(list, j + 1, high);
61. }
62. }

Output:

Page 22 of 57
Experiment 3:

Aim: Write a program to sort given set of numbers in ascending/descending order using Merge Sort
and determine the time required to sort the elements.

Program:

1./*
2. * C Program to Input Few Numbers & Perform Merge Sort on them using
Recursion
3. */
4.
5.#include <stdio.h>
6.
7.void mergeSort(int [], int, int, int);
8.void partition(int [],int, int);
9.
10. int main()
11. {
12. int list[50];
13. int i, size;
14.
15. printf("Enter total number of elements:");
16. scanf("%d", &size);
17. printf("Enter the elements:\n");
18. for(i = 0; i < size; i++)
19. {
20. scanf("%d", &list[i]);
21. }
22. partition(list, 0, size - 1);
23. printf("After merge sort:\n");
24. for(i = 0;i < size; i++)
25. {
26. printf("%d ",list[i]);
27. }
28.
29. return 0;
30. }
31.
32. void partition(int list[],int low,int high)
33. {
34. int mid;
35.
36. if(low < high)
37. {
38. mid = (low + high) / 2;
39. partition(list, low, mid);
40. partition(list, mid + 1, high);
41. mergeSort(list, low, mid, high);
42. }
43. }
44.
45. void mergeSort(int list[],int low,int mid,int high)
46. {
 47. int i, mi, k, lo, temp[50];
48.
49. lo = low;
50. i = low;
51. mi = mid + 1;
52. while ((lo <= mid) && (mi <= high))
53. {
54. if (list[lo] <= list[mi])
55. {
56. temp[i] = list[lo];
57. lo++;
58. }
59. else
60. {
61. temp[i] = list[mi];
62. mi++;
63. }
64. i++;
65. }
66. if (lo > mid)
67. {
68. for (k = mi; k <= high; k++)
69. {
70. temp[i] = list[k];
71. i++;
72. }
73. }
74. else
75. {
76. for (k = lo; k <= mid; k++)
77. {
78. temp[i] = list[k];
79. i++;
80. }
81. }
82.
83. for (k = low; k <= high; k++)
84. {
85. list[k] = temp[k];
86. }
87. }

Output:

Page 24 of 57
Experiment 4:

Aim: Write a program to sort given set of numbers in ascending/descending order using Counting
Sort

Program:
1./*
2. * C Program for counting sort
3. */
4.#include <stdio.h>
5.
6./* Counting sort function */
7.void counting_sort(int A[], int k, int n)
8.{
9. int i, j;
10. int B[15], C[100];
11. for (i = 0; i <= k; i++)
12. C[i] = 0;
13. for (j = 1; j <= n; j++)
14. C[A[j]] = C[A[j]] + 1;
15. for (i = 1; i <= k; i++)
16. C[i] = C[i] + C[i-1];
17. for (j = n; j >= 1; j--)
18. {
19. B[C[A[j]]] = A[j];
20. C[A[j]] = C[A[j]] - 1;
21. }
22. printf("The Sorted array is : ");
23. for (i = 1; i <= n; i++)
24. printf("%d ", B[i]);
25. }
26. /* End of counting_sort() */
27.
28. /* The main() begins */
29. int main()
30. {
31. int n, k = 0, A[15], i;
32. printf("Enter the number of input : ");
33. scanf("%d", &n);
34. printf("\nEnter the elements to be sorted :\n");
35. for (i = 1; i <= n; i++)
36. {
37. scanf("%d", &A[i]);
38. if (A[i] > k) {
39. k = A[i];
40. }
41. }
42. counting_sort(A, k, n);
43. printf("\n");
44. return 0;
45. }
Output:

Page 26 of 57
Experiment 5

Aim: Write a program to sort given set of numbers in ascending/descending order using Bucket Sort.

Program:

1./*
2. * C Program to Sort Array using Bucket Sort
3. */
4.#include <stdio.h>
5.
6./* Function for bucket sort */
7.void Bucket_Sort(int array[], int n)
8.{
9. int i, j;
10. int count[n];
11. for (i = 0; i < n; i++)
12. count[i] = 0;
13.
14. for (i = 0; i < n; i++)
15. (count[array[i]])++;
16.
17. for (i = 0, j = 0; i < n; i++)
18. for(; count[i] > 0; (count[i])--)
19. array[j++] = i;
20. }
21. /* End of Bucket_Sort() */
22.
23. /* The main() begins */
24. int main()
25. {
26. int array[100], i, num;
27.
28. printf("Enter the size of array : ");
29. scanf("%d", &num);
30. printf("Enter the %d elements to be sorted:\n",num);
31. for (i = 0; i < num; i++)
32. scanf("%d", &array[i]);
33. printf("\nThe array of elements before sorting : \n");
34. for (i = 0; i < num; i++)
35. printf("%d ", array[i]);
36. printf("\nThe array of elements after sorting : \n");
37. Bucket_Sort(array, num);
38. for (i = 0; i < num; i++)
39. printf("%d ", array[i]);
40. printf("\n");
41. return 0;
42. }
Output:

Page 28 of 57
Experiment 6

Aim: Write a program to sort given set of numbers in ascending/descending order using Radix Sort.

Program:

1./*
2. * C Program to Sort an Integer Array using LSDRadix Sort Algorithm
3. */
4.#include <stdio.h>
5.
6.int min = 0, count = 0, array[100] = {0}, array1[100] = {0};
7.
8.void main()
9.{
10. int k, i, j, temp, t, n;
11.
12. printf("Enter size of array :");
13. scanf("%d", &count);
14. printf("Enter elements into array :");
15. for (i = 0; i < count; i++)
16. {
17. scanf("%d", &array[i]);
18. array1[i] = array[i];
19. }
20. for (k = 0; k < 3; k++)
21. {
22. for (i = 0; i < count; i++)
23. {
24. min = array[i] % 10; /* To find minimum lsd */
25. t = i;
26. for (j = i + 1; j < count; j++)
27. {
28. if (min > (array[j] % 10))
29. {
30. min = array[j] % 10;
31. t = j;
32. }
33. }
34. temp = array1[t];
35. array1[t] = array1[i];
36. array1[i] = temp;
37. temp = array[t];
38. array[t] = array[i];
39. array[i] = temp;
40.
41. }
 42. for (j = 0; j < count; j++) /*to find MSB */
43. array[j] = array[j] / 10;
44. }
45. printf("Sorted Array (lSdradix sort) : ");
46. for (i = 0; i < count; i++)
47. printf("%d ", array1[i]);
48. }

Output:

Page 30 of 57
Experiment 7
Aim: Write a program to implement Longest Common Subsequences (LCS).

Program:

1.#include<iostream>
2.#include<string>
3.
4.using namespace std;
5.
6.int longestCommonSubsequece(string str1, string str2, int len1, int len2)
7.{
8. int i, j;
9. //create a matrix of order (len1+1)*(len2+1) to tabulate values
10. int LCS[len1+1][len2+1];
11. //LCS[i][j]=Length of longest common subsequence of str1[0....
(i-1)] and str2[0...(j-1)]
12. //initializing
13. for(i=0;i<=len1;i++)
14. LCS[i][0]=0; //empty str2
15. for(j=0;j<=len2;j++)
16. LCS[0][j]=0; //empty str1
17. //now, start filling the matrix row wise
18. for(i=1;i<=len1;i++)
19. {
20. for(j=1;j<=len2;j++)
21. {
22. //if current character of both strings match
23. if(str1[i-1]==str2[j-1])
24. {
25. LCS[i][j]=1+LCS[i-1][j-1];
26. }
27. //mismatch
28. else
29. {
30. LCS[i][j]=max(LCS[i-1][j],LCS[i][j-1]);
31. }
32. }
33. }
34. //now, return the final value
35. return LCS[len1][len2];
36. }
37. int main()
38. {
39. string str1,str2;
40.
41. cout<<"Enter first string ";
42. getline(cin, str1);
43.
44. cout<<"Enter second string ";
45. getline(cin, str2);
46.
47. int len1=str1.length(); //length of str1
48. int len2=str2.length(); //length of str2
49.
50. cout<<"Length of longest common subsequence is
"<<longestCommonSubsequece(str1,str2,len1,len2);
51.
52. cout<<endl;
53. return 0;
54. }

Page 32 of 57
Output:
Experiment 8

Aim: Write a program to implement Matrix chain multiplication

Program:

1.#include<iostream>
2.#include<climits>
3.using namespace std;
4.
5.int matrixChain(int n, int order[])
6.{
7. int i,j,k;
8. int tempValue;
9.
10. int dp[n+1][n+1];
11.
12. //dp[i][j] denotes the minimum number of multiplication
operations required to compute the matrix chain product of chain of
matrix i to matrix j
13.
14. //initialization
15. //No multiplication operations will be done if the chain
consists of a single matrix
16. for(i=1;i<=n;i++)
17. {
18. dp[i][i]=0;
19. }
20.
21. //first we will calculate min. operations for a all chains of
size of 2, then for all chains of size 3 and finally for the original
chain ie., of size n
22. for(int size=2;size<=n;size++)
23. {
24. //i is the first matrix of the chain
25. for(i=1;i<=(n-size+1);i++)
26. {
27. //j is the first matrix of the chain
28. j=i+size-1;
29.
30. //now, calculate the min. multiplications required to
compute product of the chain with matrices i, i+1,...,j
31. //First initialize the result to infinity and then
replace if lesser results are obtained
32. dp[i][j]=INT_MAX;
33.
34. //now, divide the chain of matrices i....j into two
sub-chains i...k and k+1...j and use the already computed results of
these sub-chains to compute the result of original chain
35. for(k=i;k<j;k++)
36. {
37. tempValue=dp[i][k]+dp[k+1][j]+order[i-
1]*order[k]*order[j];
38.
39. //if tempValue is lesser than the current value of
dp[i][j], replace it
40. if(tempValue<dp[i][j])
41. {
42. dp[i][j]=tempValue;
43. }

Page 34 of 57
 44. }
45.
46. }
47.
48. }
49.
50. //return the min. multiplication operations for the original
matrix
51. return dp[1][n];
52.
53. }
54.
55. int main()
56. {
57. int i,j;
58. int n;
59.
60. cout<<"Enter the number of matrices in the chain(greater than
1) ";
61. cin>>n;
62.
63. int order[n+1];
64.
65. //order of matrix i will be given by order[i-1]*order[i]
66. cout<<"Enter the order array of the matrix chain ("<<n+1<<"
elements)"<<endl;
67. for(i=0;i<=n;i++)
68. {
69. cin>>order[i];
70. }
71.
72. cout<<"The minimum number of multiplication operations
required to multiply the matrix chain is "<<matrixChain(n,order);
73.
74. cout<<endl;
75. return 0;
76. }

Output:
Experiment 9

Aim: Write a program to implement 0/1 Knapsack problem

Program:

1.#include<iostream>
2.using namespace std;
3.
4.//function to recursive check every subset of items
5.int knapsack(int w[], int p[], int n, int M)
6.{
7. //In every pass, we can either include nth item or not
8.
9. //if the capacity of knapsack is left to NIL, no value can be attained
10. if(M==0)
11. return 0;
12.
13. //if no more items are left, no value can be attained
14. if(n==0)
15. return 0;
16.
17. //if current item, weighs more than the capacity of knapsack,
it can not be included
18. if(w[n-1]>M)
19. return knapsack(w,p,n-1,M);
20.
21. //else select the maximum value of once including the current
item and once not including it
22. return max(knapsack(w,p,n-1,M),p[n-1]+knapsack(w,p,n-1,M-w[n-
1]));
23. }
24.
25. int main()
26. {
27. int i,n;
28. int M; //capacity of knapsack
29.
30. cout<<"Enter the no. of items ";
31. cin>>n;
32.
33. int w[n]; //weight of items
34. int p[n]; //value of items
35.
36. cout<<"Enter the weight and price of all items"<<endl;
37. for(i=0;i<n;i++)
38. {
39. cin>>w[i]>>p[i];
40. }
41.
42. cout<<"enter the capacity of knapsack ";
43. cin>>M;
44.
45. cout<<"The maximum value of items that can be put into
knapsack is "<<knapsack(w,p,n,M);
46.
Page 36 of 57
47. return 0;
48. }
1.#include<bits/stdc++.h>
2.using namespace std;
3.
4.int knapsack_dp(int n, int M, int w[], int p[])
5.{
6. int i,j;
7.
8. //create a matrix to memoize the values using dynamic programming
9. int knapsack[n+1][M+1];
10.
11. //knapsack[i][j] denotes the maximum attainable value of items
in knpasack with i available
12. //items and capacity of knapsack being j
13.
14. //initializing knapsack[0][j]=0 for 0<=j<=M
15. //because if there is no item, no value can be attained
16. for(j=0;j<=M;j++)
17. knapsack[0][j]=0;
18.
19. //initializing knapsack[i][0]=0 for 0<=i<=n,
20. //because in a bag of zero capacity, no item can be placed
21. for(i=0;i<=n;i++)
22. knapsack[i][0]=0;
23.
24. //now, filling the matrix in bottom up manner
25. for(i=1;i<=n;i++)
26. {
27. for(j=1;j<=M;j++)
28. {
29. //check if the weight of current item i is less than
or equal to the capacity of sack,
30. //take maximum of once including the current item and
once not including
31. if(w[i-1]<=j)
32. {
33. knapsack[i][j]=max(knapsack[i-1][j],p[i-
1]+knapsack[i-1][j-w[i-1]]);
34. }
35.
36. //can not include the current item in this case
37. else
38. {
39. knapsack[i][j]=knapsack[i-1][j];
40. }
41. }
42. }
43.
44.
45. return knapsack[n][M];
46.
47.
48. }
49.
50. int main()
51. {
52. int i,j;
53. int n; //number of items
54. int M; //capacity of knapsack
55.
56. cout<<"Enter the no. of items ";
57. cin>>n;
58.
 59. int w[n]; //weight of items
60. int p[n]; //value of items
61.
62. cout<<"Enter the weight and price of all items"<<endl;
63. for(i=0;i<n;i++)
64. {
65. cin>>w[i]>>p[i];
66. }
67.
68. cout<<"enter the capacity of knapsack ";
69. cin>>M;
70.
71.
72. int result=knapsack_dp(n,M,w,p);
73.
74. //the maximum value will be given by knasack[n][M], ie. using
n items with capacity M
75. cout<<"The maximum value of items that can be put into
knapsack is "<<result;
76.
77. return 0;
78. }

Output:

Page 38 of 57
Experiment 10

Aim: Write a program to implement fractional Knapsack problem.

Program:

1.#include <stdio.h>
2.
3.int n = 5; /* The number of objects */
4.int c[10] = {12, 1, 2, 1, 4}; /* c[i] is the *COST* of the ith object;
i.e. what
5. YOU PAY to take the object */
6.int v[10] = {4, 2, 2, 1, 10}; /* v[i] is the *VALUE* of the ith object;
i.e.
7. what YOU GET for taking the object */
8.int W = 15; /* The maximum weight you can take */
9.
10. void simple_fill() {
11. int cur_w;
12. float tot_v;
13. int i, maxi;
14. int used[10];
15.
16. for (i = 0; i < n; ++i)
17. used[i] = 0; /* I have not used the ith object yet */
18.
19. cur_w = W;
20. while (cur_w > 0) { /* while there's still room*/
21. /* Find the best object */
22. maxi = -1;
23. for (i = 0; i < n; ++i)
24. if ((used[i] == 0) &&
25. ((maxi == -1) || ((float)v[i]/c[i] >
(float)v[maxi]/c[maxi])))
26. maxi = i;
27.
28. used[maxi] = 1; /* mark the maxi-th object as used */
29. cur_w -= c[maxi]; /* with the object in the bag, I can
carry less */
30. tot_v += v[maxi];
31. if (cur_w >= 0)
32. printf("Added object %d (%d$, %dKg) completely in the
bag. Space left: %d.\n", maxi + 1, v[maxi], c[maxi], cur_w);
33. else {
34. printf("Added %d%% (%d$, %dKg) of object %d in the
bag.\n", (int)((1 + (float)cur_w/c[maxi]) * 100), v[maxi], c[maxi], maxi
+ 1);
35. tot_v -= v[maxi];
36. tot_v += (1 + (float)cur_w/c[maxi]) * v[maxi];
37. }
38. }
39.
40. printf("Filled the bag with objects worth %.2f$.\n", tot_v);
41. }
 42.
43. int main(int argc, char *argv[]) {
44. simple_fill();
45.
46. return 0;
47. }

Output:

Page 40 of 57
Experiment 11

Aim: From a given vertex in a weighted connected graph, find shortest paths to other vertices using
Dijkstra's algorithm.

Program:
1. #include<stdio.h>
2. #define INFINITY 9999
3. #define MAX 10
4.
5. void dijkstra(int G[MAX][MAX],int n,int startnode);
6.
7. int main()
8. {
9. int G[MAX][MAX],i,j,n,u;
10. printf("Enter no. of vertices:");
11. scanf("%d",&n);
12. printf("\nEnter the adjacency matrix:\n");
13.
14. for(i=0;i<n;i++)
15. for(j=0;j<n;j++)
16. scanf("%d",&G[i][j]);
17.
18. printf("\nEnter the starting node:");
19. scanf("%d",&u);
20. dijkstra(G,n,u);
21.
22. return 0;
23. }
24.
25. void dijkstra(int G[MAX][MAX],int n,int startnode)
26. {
27.
28. int cost[MAX][MAX],distance[MAX],pred[MAX];
29. int visited[MAX],count,mindistance,nextnode,i,j;
30.
31. //pred[] stores the predecessor of each node
32. //count gives the number of nodes seen so far
33. //create the cost matrix
34. for(i=0;i<n;i++)
35. for(j=0;j<n;j++)
36. if(G[i][j]==0)
37. cost[i][j]=INFINITY;
38. else
39. cost[i][j]=G[i][j];
40.
41. //initialize pred[],distance[] and visited[]
42. for(i=0;i<n;i++)
43. {
44. distance[i]=cost[startnode][i];
45. pred[i]=startnode;
46. visited[i]=0;
47. }
48.
49. distance[startnode]=0;
50. visited[startnode]=1;#include<stdio.h>
51. #define INFINITY 9999
52. #define MAX 10
53.
54. void dijkstra(int G[MAX][MAX],int n,int startnode);
55.
56. int main()
57. {
58. int G[MAX][MAX],i,j,n,u;
59. printf("Enter no. of vertices:");
60. scanf("%d",&n);
61. printf("\nEnter the adjacency matrix:\n");
62.
63. for(i=0;i<n;i++)
64. for(j=0;j<n;j++)
65. scanf("%d",&G[i][j]);
66.
67. printf("\nEnter the starting node:");
68. scanf("%d",&u);
69. dijkstra(G,n,u);
70.
71. return 0;
72. }
73.
74. void dijkstra(int G[MAX][MAX],int n,int startnode)
75. {
76.
77. int cost[MAX][MAX],distance[MAX],pred[MAX];
78. int visited[MAX],count,mindistance,nextnode,i,j;
79.
80. //pred[] stores the predecessor of each node
81. //count gives the number of nodes seen so far
82. //create the cost matrix
83. for(i=0;i<n;i++)
84. for(j=0;j<n;j++)
85. if(G[i][j]==0)
86. cost[i][j]=INFINITY;
87. else
88. cost[i][j]=G[i][j];
89.
90. //initialize pred[],distance[] and visited[]
91. for(i=0;i<n;i++)
92. {
93. distance[i]=cost[startnode][i];
94. pred[i]=startnode;
95. visited[i]=0;
96. }
97.
98. distance[startnode]=0;
99. visited[startnode]=1;
100. count=1;
101.
102. while(count<n-1)
103. {
104. mindistance=INFINITY;
105.
106. //nextnode gives the node at minimum distance

Page 42 of 57
107. for(i=0;i<n;i++)
108. if(distance[i]<mindistance&&!visited[i])
109. {
110. mindistance=distance[i];
111. nextnode=i;
112. }
113.
114. //check if a better path exists through nextnode
115. visited[nextnode]=1;
116. for(i=0;i<n;i++)
117. if(!visited[i])
118. if(mindistance+cost[nextnode][i]<distance[i])
119. {
120. distance[i]=mindistance+cost[nextnode][i];
121. pred[i]=nextnode;
122. }
123. count++;
124. }
125.
126. //print the path and distance of each node
127. for(i=0;i<n;i++)
128. if(i!=startnode)
129. {
130. printf("\nDistance of node%d=%d",i,distance[i]);
131. printf("\nPath=%d",i);
132.
133. j=i;
134. do
135. {
136. j=pred[j];
137. printf("<-%d",j);
138. }while(j!=startnode);
139. }
140. }
141. count=1;
142.
143. while(count<n-1)
144. {
145. mindistance=INFINITY;
146.
147. //nextnode gives the node at minimum distance
148. for(i=0;i<n;i++)
149. if(distance[i]<mindistance&&!visited[i])
150. {
151. mindistance=distance[i];
152. nextnode=i;
153. }
154.
155. //check if a better path exists through nextnode
156. visited[nextnode]=1;
157. for(i=0;i<n;i++)
158. if(!visited[i])
159. if(mindistance+cost[nextnode][i]<distance[i])
160. {
161. distance[i]=mindistance+cost[nextnode][i];
162. pred[i]=nextnode;
163. }
164. count++;
165. }
166.
167. //print the path and distance of each node
168. for(i=0;i<n;i++)
169. if(i!=startnode)
170. {
 171. printf("\nDistance of node%d=%d",i,distance[i]);
172. printf("\nPath=%d",i);
173.
174. j=i;
175. do
176. {
177. j=pred[j];
178. printf("<-%d",j);
179. }while(j!=startnode);
180. }
181. }

Output:

Page 44 of 57
Experiment 12

Aim: Write a program to implement Sum of Subset problem.

Program:

1.#include<iostream>
2.using namespace std;
3.
4.bool subset_sum(int a[],int n, int sum)
5.{
6. //boolean matrix to store results
7. bool dp[n+1][sum+1];
8.
9. //dp[i][j]=whethere there is a subset of sum j in subarray a[0....i-1]
10.
11. int i,j;
12.
13. //initialization
14. //for sum=0, there is always a subset possible ie., the empty
set
15. for(i=0;i<=n;i++)
16. dp[i][0]=true;
17.
18. //if there are no elements in the array, no subset is possible
for a non-zero sum
19. for(j=1;j<=sum;j++)
20. dp[0][j]=false;
21.
22. //i represents the no. of elements of array considered
23. for(i=1;i<=n;i++)
24. {
25. //j represents the sum of subset being searched for
26. for(j=1;j<=sum;j++)
27. {
28. //if using i-1 elements, there is a subset of desired
sum
29. //no need to search further
30. //the result is true
31. if(dp[i-1][j]==true)
32. dp[i][j]=true;
33.
34. //otherwise, we will inspect
35. else
 36. {
37. //if value of current element is greater than the
required sum
38. //this element cannot be considered
39. if(a[i-1]>j)
40. dp[i][j]=false;
41.
42. //check that after including this element, Is
there any subset present for the remaining sum ie., j-a[i-1]
43. else
44. dp[i][j]=dp[i-1][j-a[i-1]];
45. }
46. }
47. }
48.
49. //return the overall result
50. return dp[n][sum];
51. }
52.
53. int main()
54. {
55. int i;
56. int n;
57. int sum;
58.
59. cout<<"Enter the value of sum"<<endl;
60. cin>>sum;
61.
62. cout<<"Enter the number of elements in the set"<<endl;
63. cin>>n;
64. int a[n];
65.
66. cout<<"Enter the values"<<endl;
67. for(i=0;i<n;i++)
68. cin>>a[i];
69.
70. bool result=subset_sum(a,n,sum);
71.
72. if(result==true)
73. cout<<"subset with the given sum found";
74.
75. else
76. cout<<"no required subset found";
77.
cout<<endl;
return 0;
}

Output:

Page 46 of 57
Experiment 13

Aim:

Program:

#include <stdio.h>
#include <stdlib.h>

// Structure to represent each

// node in a red-black tree
struct node {
int d; // data
int c; // 1-red, 0-black
struct node* p; // parent
struct node* r; // right-child
struct node* l; // left child
};

// global root for the entire tree

struct node* root = NULL;

// function to perform BST insertion of a node

struct node* bst(struct node* trav,
struct node* temp)
{
// If the tree is empty,
// return a new node
if (trav == NULL)
return temp;
 // Otherwise recur down the tree
if (temp->d < trav->d)
{
trav->l = bst(trav->l, temp);
trav->l->p = trav;
}
else if (temp->d > trav->d)
{
trav->r = bst(trav->r, temp);
trav->r->p = trav;
}

// Return the (unchanged) node pointer

return trav;
}

// Function performing right rotation

// of the passed node
void rightrotate(struct node* temp)
{
struct node* left = temp->l;
temp->l = left->r;
if (temp->l)
temp->l->p = temp;
left->p = temp->p;
if (!temp->p)
root = left;
else if (temp == temp->p->l)
temp->p->l = left;
else
temp->p->r = left;
left->r = temp;
temp->p = left;
}

// Function performing left rotation

// of the passed node
void leftrotate(struct node* temp)
{
struct node* right = temp->r;
temp->r = right->l;
if (temp->r)
temp->r->p = temp;
right->p = temp->p;
if (!temp->p)
root = right;
else if (temp == temp->p->l)
temp->p->l = right;
else
temp->p->r = right;
right->l = temp;
temp->p = right;
}

// This function fixes violations

// caused by BST insertion
void fixup(struct node* root, struct node* pt)
{
struct node* parent_pt = NULL;
struct node* grand_parent_pt = NULL;

while ((pt != root) && (pt->c != 0)

Page 48 of 57
 && (pt->p->c == 1))
{
parent_pt = pt->p;
grand_parent_pt = pt->p->p;

/* Case : A
Parent of pt is left child
of Grand-parent of
pt */
if (parent_pt == grand_parent_pt->l)
{

struct node* uncle_pt = grand_parent_pt->r;

/* Case : 1
The uncle of pt is also red
Only Recoloring required */
if (uncle_pt != NULL && uncle_pt->c == 1)
{
grand_parent_pt->c = 1;
parent_pt->c = 0;
uncle_pt->c = 0;
pt = grand_parent_pt;
}

else {

/* Case : 2
pt is right child of its parent
Left-rotation required */
if (pt == parent_pt->r) {
leftrotate(parent_pt);
pt = parent_pt;
parent_pt = pt->p;
}

/* Case : 3
pt is left child of its parent
Right-rotation required */
rightrotate(grand_parent_pt);
int t = parent_pt->c;
parent_pt->c = grand_parent_pt->c;
grand_parent_pt->c = t;
pt = parent_pt;
}
}

/* Case : B
Parent of pt is right
child of Grand-parent of
pt */
else {
struct node* uncle_pt = grand_parent_pt->l;

/* Case : 1
The uncle of pt is also red
Only Recoloring required */
if ((uncle_pt != NULL) && (uncle_pt->c == 1))
{
grand_parent_pt->c = 1;
parent_pt->c = 0;
uncle_pt->c = 0;
pt = grand_parent_pt;
}
 else {
/* Case : 2
pt is left child of its parent
Right-rotation required */
if (pt == parent_pt->l) {
rightrotate(parent_pt);
pt = parent_pt;
parent_pt = pt->p;
}

/* Case : 3
pt is right child of its parent
Left-rotation required */
leftrotate(grand_parent_pt);
int t = parent_pt->c;
parent_pt->c = grand_parent_pt->c;
grand_parent_pt->c = t;
pt = parent_pt;
}
}
}

root->c = 0;
}

// Function to print inorder traversal

// of the fixated tree
void inorder(struct node* trav)
{
if (trav == NULL)
return;
inorder(trav->l);
printf("%d ", trav->d);
inorder(trav->r);
}

// driver code
int main()
{
int n = 7;
int a[7] = { 7, 6, 5, 4, 3, 2, 1 };

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

// allocating memory to the node and initializing:

// 1. color as red
// 2. parent, left and right pointers as NULL
// 3. data as i-th value in the array
struct node* temp
= (struct node*)malloc(sizeof(struct node));
temp->r = NULL;
temp->l = NULL;
temp->p = NULL;
temp->d = a[i];
temp->c = 1;

// calling function that performs bst insertion of

// this newly created node
root = bst(root, temp);

// calling function to preserve properties of rb

// tree
fixup(root, temp);

Page 50 of 57
 }

printf("Inoder Traversal of Created Tree\n");

inorder(root);

return 0;
}

Output:

Experiment 14

Aim: Implement All-Pairs Shortest Paths Problem using Floyd's algorithm.

Program:

// C Program for Floyd Warshall Algorithm

#include<stdio.h>

// Number of vertices in the graph

#define V 4

/* Define Infinite as a large enough

value. This value will be used
for vertices not connected to each other */
#define INF 99999

// A function to print the solution matrix

void printSolution(int dist[][V]);

// Solves the all-pairs shortest path

// problem using Floyd Warshall algorithm
void floydWarshall (int graph[][V])
{
 int dist[V][V], i, j, k;
for (i = 0; i < V; i++)
for (j = 0; j < V; j++)
dist[i][j] = graph[i][j];
for (k = 0; k < V; k++)
{
// Pick all vertices as source one by one
for (i = 0; i < V; i++)
{
// Pick all vertices as destination for the
// above picked source
for (j = 0; j < V; j++)
{
// If vertex k is on the shortest path from
// i to j, then update the value of dist[i][j]
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}

// Print the shortest distance matrix

printSolution(dist);
}

/* A utility function to print solution */

void printSolution(int dist[][V])
{
printf ("The following matrix shows the shortest distances"
" between every pair of vertices \n");
for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
{
if (dist[i][j] == INF)
printf("%7s", "INF");
else
printf ("%7d", dist[i][j]);
}
printf("\n");
}
}

// driver program to test above function

int main()
{
/* Let us create the following weighted graph
10
(0)------->(3)
| /|\
5 | |
| | 1
\|/ |
(1)------->(2)
3 */
int graph[V][V] = { {0, 5, INF, 10},
{INF, 0, 3, INF},
{INF, INF, 0, 1},
{INF, INF, INF, 0}
};

// Print the solution

floydWarshall(graph);

Page 52 of 57
 return 0;
}

Output:

Experiment 15

Aim: Write a program to implement Naïve string matching problem

Program:

#include<stdio.h>
#include<string.h>
// d is the number of characters in input alphabet
#define d 256
/* pat -> pattern
txt -> text
q -> A prime number
*/
void search(char *pat, char *txt, int q)
{
int M = strlen(pat);
int N = strlen(txt);
int i, j;
int p = 0; // hash value for pattern
int t = 0; // hash value for txt
int h = 1;
 // The value of h would be "pow(d, M-1)%q"
for (i = 0; i < M-1; i++)
h = (h*d)%q;

// Calculate the hash value of pattern and first window of text

for (i = 0; i < M; i++)
{
p = (d*p + pat[i])%q;
t = (d*t + txt[i])%q;
}

// Slide the pattern over text one by one

for (i = 0; i <= N - M; i++)
{

// Chaeck the hash values of current window of text and pattern

// If the hash values match then only check for characters on by one
if ( p == t )
{
/* Check for characters one by one */
for (j = 0; j < M; j++)
{
if (txt[i+j] != pat[j])
break;
}
if (j == M) // if p == t and pat[0...M-1] = txt[i, i+1, ...i+M-
1]
{
printf("Pattern found at index %d \n", i);
}
}

// Calulate hash value for next window of text: Remove leading

digit,
// add trailing digit
if ( i < N-M )
{
t = (d*(t - txt[i]*h) + txt[i+M])%q;

// We might get negative value of t, converting it to positive

if(t < 0)
t = (t + q);
}
}
}

/* Driver program to test above function */

int main()
{
char *txt = "GEEKS FOR GEEKS";
char *pat = "GEEK";
int q = 101; // A prime number
search(pat, txt, q);
getchar();
return 0;
}

Output:

Page 54 of 57
Experiment 16

Aim: Write a program to implement Rabin Karp Algorithm problem

Program:

#include <stdio.h>
#include <string.h>

// d is the number of characters in the input alphabet

#define d 256

/* pat -> pattern

txt -> text
q -> A prime number
 */
void search(char pat[], char txt[], int q)
{
int M = strlen(pat);
int N = strlen(txt);
int i, j;
int p = 0; // hash value for pattern
int t = 0; // hash value for txt
int h = 1;

// The value of h would be "pow(d, M-1)%q"

for (i = 0; i < M - 1; i++)
h = (h * d) % q;

// Calculate the hash value of pattern and first

// window of text
for (i = 0; i < M; i++) {
p = (d * p + pat[i]) % q;
t = (d * t + txt[i]) % q;
}

// Slide the pattern over text one by one

for (i = 0; i <= N - M; i++) {

// Check the hash values of current window of text

// and pattern. If the hash values match then only
// check for characters on by one
if (p == t) {
/* Check for characters one by one */
for (j = 0; j < M; j++) {
if (txt[i + j] != pat[j])
break;
}

// if p == t and pat[0...M-1] = txt[i, i+1, ...i+M-1]

if (j == M)
printf("Pattern found at index %d \n", i);
}

// Calculate hash value for next window of text: Remove

// leading digit, add trailing digit
if (i < N - M) {
t = (d * (t - txt[i] * h) + txt[i + M]) % q;

// We might get negative value of t, converting it

// to positive
if (t < 0)
t = (t + q);
}
}
}

/* Driver program to test above function */

int main()
{
char txt[] = "GEEKS FOR GEEKS";
char pat[] = "GEEK";
int q = 101; // A prime number
search(pat, txt, q);
return 0;
}

Output:
Page 56 of 57