Master Lab Manual

Course Name Data Structures and Algorithms

Course Code CSC211

Department of Electrical and Computer Engineering

CUI Attock Campus

Program: Computer Engineering

Prepared by: Engr. Iram Shahzadi

Verified by: Dr. Ajmal Khan

Session: FA20
 COMSATS UNIVERSITY ISLAMABAD, ATTOCK CAMPUS

CSC211 Data Structures and Algorithms

Laboratory
Fall 2020
Lab Course Catalog Description
In order to develop efficient software systems, it is essential that efficient algorithms and appropriate data structures are used. This lab
course focuses on the implementation of the different algorithms work, particularly those concerned with sorting and searching have a good
understanding of the fundamental data structures.

Course Details
Credit Hours 01
Core BS CE

Course Prerequisite(s)/Co-Requisite(s)
Pre-requisites: Programming Fundamentals
Co-requisites: Operating Systems

Course Offering Details

Lecture(s) No. of Lec(s) Per 2 Duration 1.5 hrs
Week
No. of Session(s) Per
Lab (if any ) per week 1 Duration 3 hrs
Week

Course Instructors Details:

Course Instructor Dr. Ajmal Khan
Office No. Ext: 256
Office Hours
Email drajmal@cuiatk.edu.pk
Lab Instructor Engr. Iram Shahzadi
Lab Conducting Place Computer Lab
Lab Timing As per TimeTable
Lab Instructor Email iram@cuiatk.edu.pk

Course Learning Outcomes

CLO 1 Use the concepts of data structures and algorithms to perform lab experiments
CLO 2 Analyze different data structures and algorithms for performance comparison in terms of time complexity and code
efficiency
CLO 3 Implement various algorithms following design and coding standards
CLO 4 Use an appropriate tool e.g Dev C/C++ or Code Block for implementation of different data structures and algorithms.
CLO 5 Demonstrate their technical projects and lab activities to a diverse audience through lab reports, viva, presentations, and
posters.

Mapping of CLOs to PLOs:

CLO Attainment
CSC211 LAB Related Level of Teaching Methods
Mechanism
CLOs PLOs Learning
CLO 1 PLO1 C2 Tutorials, Instructions, Lab Manuals and In Lab, Post Lab and Lab
Demos Exams
CLO 2 PLO2 C3 Tutorials, Instructions, Lab Manuals and In Lab, Post Lab and Lab
Demos Exams
CLO 3 PLO 3 C5 Tutorials, Instructions, Lab Manuals and In Lab, Post Lab and Lab
Demos Exams
 COMSATS UNIVERSITY ISLAMABAD, ATTOCK CAMPUS

CLO 4 PLO 5 C3 Tutorials, Instructions, Lab Manuals and In Lab, Post Lab and Lab
Demos Exams
CLO 5 PLO 10 A4 Tutorials, Instructions, Lab Manuals and In Lab, Post Lab and Lab
Demos Exams

Overview

Recommended
Week Topics
Readings (if any)
1. Operations on Array Data
2. Sequential Search and Binary Search
3. Selection Sort and Bubble Sort
4. Recurse Functions
5. Insertion Sort and Merge Sort
6. Sessional I
7. Quick Sort
8. Structures and Classes
9. Array implementation of Stack
10. Array implementation of Queue
11. Sessional II
12. Linked-list Implementation
13. Binary Search Tree Implementation
14. Graphs
15. Terminal Exam

Important Note: Students will be required to submit their Lab work and Lab handout.

Textbook(s)/Supplementary Readings
[1]. A lab manual will be provided to the students at the beginning of the each lab that carries the details of the experiments and related
instructions to perform those experiments.

Grading Breakup and Policy

Lab Terminal: 50%
Lab Sessions (12): 25%
Lab Exams (2): 25%
 Rubrics for Assessments of Lab Reports and Lab Exams
Rubrics for PLO#1 (Engineering Knowledge)
Exceeds expectations [9-10] Meets expectations[7-9) Average [5-7) Unsatisfactory [1-5)

.
R1: Lab Safety Rules: While working in the lab, the While working in the lab, the While working in the lab, the While working in the lab, the
Ability to observe safety, be student demonstrates student is attentive to safety, student is mostly attentive to student is unattentive to safety,
courteous to others, attentive exemplary behavior in respectful to instructors and safety, respectful to instructors disrespectful to others, and
to safety, and tidy in the lab. courtesy and safety, and leaves peers, and neat, cleaning the and peers, and neat, Might messy, leaving the area untidy
the area spotless. area before leaving. need reminders to leave the even after being reminded.
area clean.
R2: Use of Engineering
Knowledge and follow The procedure is efficiently The procedure is well The procedure could be better The procedure is inadequately
Engineering Experiment Procedures: followed and student skillfully followed and student followed, but student controls followed, and student does not
Knowledge Ability to follow experimental controls all chosen variables. demonstrates control of all all chosen variables. Most control chosen variables. Many
procedures, control variables, Know all procedural steps, and chosen variables. All procedural steps are recorded procedural steps are not entered
and record procedural steps are clearly and concisely procedural steps are on the lab report. on the lab report.
on lab report. recorded on lab report recorded on the lab report.
R3: Interpretation of Demonstrates a skillful ability Demonstrates an ability to Demonstrates some ability Demonstrates minimal or no
Subject Knowledge: to provide rational provide rational to provide explanations of ability to provide explanation of
Ability to interpret and explanations, and on the basis explanations of mathematical and/or visual mathematical
explain mathematical and/or of that information, can make mathematical and/or forms, and makes occasional and/or visual forms. Frequently
visual forms, including fitting inferences. visual forms. mistakes. misinterprets
equations,
diagrams, graphics, figures
and tables.
Rubrics for PLO#2 (Problem Analysis)
Exceeds expectations [9-10] Meets expectations[7-9) Average [5-7) Unsatisfactory [1-5)

.
R4: Limitations and Point out all significant Point out many significant Point out some limitations Minimal or no ability to identify
Implications: limitations and limitations and implications. and implications. limitations or implications. Has
Ability to point out implications. Demonstrates Demonstrates recognition Demonstrates some no knowledge of hardware or
limitations and implications skillful recognition and and consideration of recognition and software implementation
of Hardware and software consideration of important important assumptions, Consideration of important requirements for the problem
Components. assumptions, hardware or hardware or software requirements of hardware or solution. Didn’t mention about
software requirements requirements when solving software. .Has mentioned assumption and constraints.
Problem when solving a problem. a problem. some of the assumptions.
Analysis
 R5: Data/Evidence Raw data/evidence, as well as Raw data/evidence, as well Raw data/evidence, as well as Raw data/evidence, as well as
Measurements: units, are skillfully recorded. as units, are appropriately units, are recorded although units, are not recorded suitably.
Ability to record raw data / The data table is clearly and and clearly recorded. The not as clearly or suitably as The data table is not labeled
evidence. concisely, and/or creatively data table is appropriately they might be. The data table and/or formatted.
labeled and formatted. labeled and formatted. may lack appropriate labels
and/or format.
R6: Experimental Data Accurately analyze the Accurately analyze the Analyze the collected data and Analysis and interpretation of the
Analysis: collected data and interpret the collected data and interpret interpret the findings with findings is illogical, and the
Ability to interpret findings, findings insightfully, and the findings. Correlates minor errors. Correlates findings. No attempt to correlate
compare them to values in the skillfully. Correlates experimental results to experimental results to known experimental results with known
literature, identify weaknesses experimental results to known known theoretical values; theoretical values; accounts for theoretical values; incapable of
and limitations. theoretical values; accounts for accounts for measurement measurement errors and explaining measurement errors or
measurement errors and errors and parameters that parameters that affect parameters that affect the
parameters that affect affect experimental results. experimental results. experimental results.
experimental results.

Rubrics for PLO#3 (Design)

Exceeds expectations [9-10] Meets expectations[7-9) Average [5-7) Unsatisfactory [1-5)

R7: Implementing .
Design Strategy: Ability Demonstrates a skillful Demonstrates an ability Demonstrates some ability Demonstrates minimal or no
to execute a solution (thorough/insightful/creative) to execute a solution to execute a solution that ability to execute a solution.
taking into consideration ability to execute a solution taking into consideration attends to the problem, but Solution does not directly
design requirements and taking into consideration all design requirements and omits some design attend to the problem.
pertinent contextual design requirements and some contextual requirements and/or
elements. pertinent contextual elements. elements. pertinent contextual
[Block Diagram/Flow elements.
Engineering chart/Circuit Diagram]
Design R8: Best Coding Standards: Coding standards, best Coding standards, best Coding standards, best Coding standards, best
Ability to follow the coding programming practices are programming practices are programming practices are programming practices are not or
standards and programming followed extensively. followed appropriately not appropriately followed. rarely followed.
practices.

Rubrics for PLO#5 (Modern Tools Usage)

Exceeds expectations [9-10] Meets expectations[7-9) Average [5-7) Unsatisfactory [1-5)

R9: Understand Tools: .

Ability to describe and Demonstrates skillful ability to Demonstrates ability to Demonstrates some ability to Demonstrates minimal or no
explain the principles behind describe and explain the describe and explain the describe and/or explain the ability to describe and/or
and applicability of principles behind and principles behind and principles behind and explain the principles behind
engineering tools. applicability of engineering applicability of engineering applicability of engineering and applicability of
tools. tools. tools. engineering tools.
 R10: Realization of Selects relevant equipment Mostly select relevant Need guidance to select Incapable to select relevant
Hardware and Software to the experiment, develops equipment to the experiment, relevant equipment to the equipment to the experiment,
Modern Tools for Experiments: setup diagrams of develops setup diagrams of experiment, develops setup develops setup diagrams of
Tools Usage Ability to select relevant equipment connections or equipment connections or diagrams of equipment equipment connections or
hardware tools or software wiring. Or Select relevant wiring. Or Mostly select connections or wiring. Or wiring. Incapable to select
components (P3) software libraries, relevant software libraries, Need guidance to select relevant software libraries,
functions, and directive to functions, and directive to relevant software libraries, functions, and directive to
develop the code. develop the code. functions, and directive to develop the code.
develop the code.
R11: Tools Evaluation: Demonstrates skillful ability to Ability to simulate and Demonstrates some ability to Incapable to simulate and
Ability to simulate the simulate and evaluate the evaluate the limitations of simulate and evaluate the evaluate the limitations of tools
experiment and then using limitations of tools and tools and discusses the limitations of tools and and discusses the assumptions.
hardware tools to verify the discusses the assumptions. assumptions. discusses the assumptions.
results (P4)
Rubrics for PLO#9 (Individual and Teamwork)
Exceeds expectations [9-10] Meets expectations[7-9) Average [5-7) Unsatisfactory [1-5)

R12: Individual Work .

Contributions: Designated jobs are Designated jobs are Designated jobs are Some designated jobs are
Ability to carry out accomplished by deadline; accomplished by deadline; accomplished by deadline; accomplished by deadline;
individual responsibilities. completed work is carefully completed work meets completed work meets most completed work meets some
and meticulously prepared requirements. requirements. requirements.
Individual and meets all requirements.
and
Teamwork R13: Management of Team Has great appreciation for and Has appreciation for and Has some appreciation for and Has no appreciation for or
Work: understanding of disciplines understanding of disciplines understanding of disciplines understanding of disciplines
Ability to appreciate, outside of own. Works outside of own. Works outside of own, but works less outside of own. Is unable to
understand and work with profitably with other effectively with team effectively with other team work effectively with team
multidisciplinary team members. members. members. members.
members.
 Data Structures and Algorithms Lab

Lab #:

Lab Title:

Submitted by:

Name Registration #

Rubrics name & number Marks

In-Lab Post-Lab

Engineerin R2: Use of Engineering Knowledge and follow Experiment Procedures:

g Ability to follow experimental procedures, control variables, and record
Knowledge procedural steps on lab report.
R3: Interpretation of Subject Knowledge: Ability to interpret and explain
mathematical and/or visual forms, including equations, diagrams, graphics,
figures and tables.
Problem R5: Data/Evidence Measurements:
Analysis Ability to record raw data / evidence.
R6: Experimental Data Analysis:
Ability to interpret findings, compare them to values in the literature, identify
weaknesses and limitations.
Design R8: Best Coding Standards:
Ability to follow the coding standards and programming practices.

Modern
Tools R9: Understand Tools: Ability to describe and explain the principles behind
Usage and applicability of engineering tools.

Individual R12: Individual Work Contributions:

and Ability to carry out individual responsibilities.
Teamwork

Rubrics to follow

Rubrics # R2 R3 R5 R6 R8 R9 R12

In –Lab

Post- Lab
LAB#1
Operations on Array Data

Objectives:
At the end of the lab, students are expected to be able to do the following

• Declare and initialize an array

• Perform different operations on arrays

Introduction:
In C++, an array is a variable that can store multiple values of the same type. For example,
Suppose a class has 27 students, and we need to store the grades of all of them. Instead of creating 27
separate variables, we can simply create an array:
int array[27];

Here, grade is an array that can hold a maximum of 27 elements of double type.
In C++, the size and type of arrays cannot be changed after its declaration.

Array Declaration
dataType arrayName[arraySize];

For example,
int x[6];

Here,

• int - type of element to be stored

• x - name of the array
• 6 - size of the array

Access Elements in Array

In C++, each element in an array is associated with a number. The number is known as an array index.
We can access elements of an array by using those indices.
// syntax to access array elements
array[index];

Consider the array x we have seen above.

Data Structures and Algorithms (CSC211) Lab Manual

 Figure 1: Elements of an array

• The array indices start with 0. Meaning x[0] is the first element stored at index 0.
• If the size of an array is n, the last element is stored at index (n-1). In this example, x[5] is the last
element.
• Elements of an array have consecutive addresses. For example, suppose the starting address
of x[0] is 2120d. Then, the address of the next element x[1] will be 2124d, the address
of x[2] will be 2128d and so on.

Here, the size of each element is increased by 4. This is because the size of int is 4 bytes.

Array Initialization
In C++, it's possible to initialize an array during declaration. For example,
// declare and initialize and array
int x[6] = {19, 10, 8, 17, 9, 15};

Figure 2: Initialization of array elements

Example 1: Displaying Array Elements

Code:
#include <iostream>
using namespace std;

int main() {
int numbers[5] = {7, 5, 6, 12, 35};

cout << "\nThe numbers are: ";

Data Structures and Algorithms (CSC211) Lab Manual

 // Printing array elements
// using traditional for loop
for (int i = 0; i <=4; i++) {
cout << numbers[i] << " ";
}
return 0;
}

Output:
The numbers are: 7 5 6 12 35

Here, we have used a for loop to iterate from i = 0 to i = 4. In each iteration, we have printed numbers[i].

Example 2: Take Inputs from User and Store Them in an Array

Code:
#include <iostream>
using namespace std;

int main() {
int numbers[5];

cout << "Enter 5 numbers: " << endl;

// store input from user to array

for (int i = 0; i < 5; ++i) {
cin >> numbers[i];
}
cout << "The numbers are: ";

// print array elements

for (int n = 0; n < 5; ++n) {
cout << numbers[n] << " ";
}
return 0;
}

Output:
Enter 5 numbers:
11
12
13
14
15
The numbers are: 11 12 13 14 15

Data Structures and Algorithms (CSC211) Lab Manual

Once again, we have used a for loop to iterate from i = 0 to i = 4. In each iteration, we took an input from
the user and stored it in numbers[i].
Then, we used another for loop to print all the array elements.

Example 3: Display Sum and Average of Array Elements Using for Loop
Code:
#include <iostream>
using namespace std;

int main() {

// initialize an array without specifying size

double numbers[6] = {7, 5, 6, 3, 1, 2};
int i,count=0;
double sum = 0;
double average;

cout << "The numbers are: ";

// print array elements

for (i=0;i<=5;i++) {

cout<<numbers[i]<<" ";
// calculate the sum
sum = sum+numbers[i];
count=count+1;
}

// print the sum

cout << "\nTheir Sum = " << sum << endl;

// find the average

average = sum / count;
cout << "Their Average = " << average << endl;

return 0;
}

Output:
The numbers are: 7 5 6 3 1 2
Their Sum = 24
Their Average = 4

Data Structures and Algorithms (CSC211) Lab Manual

In this program
We have initialized a double array named numbers but without specifying its size. We also declared three
double variables sum, count, and average.

Here, sum =0 and count = 0.

Then we used a for loop to print the array elements. In each iteration of the loop, we add the current array
element to sum.
We also increase the value of count by 1 in each iteration, so that we can get the size of the array by the
end of the for loop.
After printing all the elements, we print the sum and the average of all the numbers. The average of the
numbers is given by average = sum / count

Data Structures and Algorithms (CSC211) Lab Manual

 In-Lab Tasks
Task#1 Take an array from the user and then swap its first and last values.
Task#2 Take an element of an array from user, display its location and then take a new element from the
user to replace the previous element.

Post-Lab Tasks
Task#1 Take an element of an array from the user to delete it and then display the new array.

Data Structures and Algorithms (CSC211) Lab Manual

LAB#2

Sequential Search and Binary Search

Objectives:
At the end of the lab, students are expected to be able to do the following:

• Understand the searching technique concept and the purpose of searching operation
• Understand the implementation of basic searching algorithm such as sequential search and binary
search

Introduction:
Clifford A. Shaffer [1997] define searching as a process to determine whether an element is a member of
a certain data set. Sorting is the process of finding the location of an element with a specific value (key)
within a collection of elements. This process can also be seen as an attempt to search for a certain record in
a file. Each record contains data field and key field. Key field is a group of characters or numbers used as
an identifier for each record. Searching can done based on the key field.

Sequential search:

Sequential search is a very basic and simple search algorithm. In sequential search, we search an
element or value in a given array by traversing the array from the starting, till the desired element
or value is found.

It compares the element to be searched with all the elements present in the array and when the
element is matched successfully, it returns the index of the element in the array, else it returns -1.
Sequential Search is applied on unsorted or unordered lists, when there are fewer elements in a
list.

Features of Sequential Search Algorithm

1. It is used for unsorted and unordered small list of elements.

2. It has a time complexity of O(n), which means the time is linearly dependent on the number
of elements, which is not bad, but not that good too.

3. It has a very simple implementation.

Data Structures and Algorithms (CSC211) Lab Manual

Sequential Search:

Code:
#include<iostream.h>
#include<conio.h>
main()
{
int arr1[5];
int req;
int location=-5;
cout<<"Enter 5 numbers to store in array: "<<endl;
for(int i=0; i<5; i++)
{
cin>>arr1[i];
}
cout<<endl;
cout<<"Enter the number you want to find :";
cin>>req;
cout<<endl;

for(int w=0;w<5;w++)
{
if(arr1[w] == req)
location=w;
}
if(location !=-5)
{
cout<<"Required number is found out at the location:"<<location+1;
cout<<endl;
}
else
cout<<"Number is not found ";

Output:
Enter 5 numbers to store in array:

3
15
6
4
3

Enter the number you want to find :3

Required number is found out at the location:5

Data Structures and Algorithms (CSC211) Lab Manual

Binary search

Binary Search is used with sorted array or list. In binary search, we follow the following steps:

1. We start by comparing the element to be searched with the element in the middle of the
list/array.

2. If we get a match, we return the index of the middle element.

3. If we do not get a match, we check whether the element to be searched is less or greater
than in value than the middle element.

4. If the element/number to be searched is greater in value than the middle number, then we
pick the elements on the right side of the middle element (as the list/array is sorted, hence
on the right, we will have all the numbers greater than the middle number), and start again
from the step 1.

5. If the element/number to be searched is lesser in value than the middle number, then we
pick the elements on the left side of the middle element, and start again from the step 1.

Binary Search is useful when there are large number of elements in an array and they are sorted.

So, a necessary condition for Binary search to work is that the list/array should be sorted.

Features of Binary Search

1. It is great to search through large sorted arrays.

2. It has a time complexity of O(log n) which is a very good time complexity. We will discuss
this in details in the Binary Search tutorial.

3. It has a simple implementation.

Binary search

Code:
#include <iostream>
using namespace std;

int binarySearch(int[], int, int, int);

int main()
{
int num[10] = {10, 22, 37, 55, 92, 118};
int search_num, loc=-1;

cout<<"Enter the number that you want to search: ";

cin>>search_num;

Data Structures and Algorithms (CSC211) Lab Manual

 loc = binarySearch(num, 0, 6, search_num);

if(loc != -1)
{
cout<<search_num<<" found in the array at the location: "<<loc;
}
else
{
cout<<"Element not found";
}
return 0;
}

int binarySearch(int a[], int first, int last, int search_num)

{
int middle;
if(last >= first)
{
middle = (first + last)/2;
//Checking if the element is present at middle loc
if(a[middle] == search_num)
{
return middle+1;
}

//Checking if the search element is present in greater half

else if(a[middle] < search_num)
{
return binarySearch(a,middle+1,last,search_num);
}

//Checking if the search element is present in lower half

else
{
return binarySearch(a,first,middle-1,search_num);
}

}
return -1;
}
Output:
Enter the number that you want to search: 37

37 found in the array at the location: 3

Data Structures and Algorithms (CSC211) Lab Manual

 IN-LAB TASKS
Task# 1 Take an unsorted array from the user and a search-key to find from that array. Then using
sequential search, find the location of that key. And if that key is not present in the array, display
‘not found’ message on the console window.

Task# 2 Take a sorted array of size 9 from the user and a search-key to find from that array. Then
using binary search, find that key from the array.

POST-LAB TASKS
Task# 1 Take a sorted array of size 10 from the user. Dry run the code of binary search for search
key that is not present in the array. Implement the code in compiler and display the values of
variables that control the ‘while loop’ for each iteration until the loop stops.

Data Structures and Algorithms (CSC211) Lab Manual

LAB#3

Selection Sort and Bubble Sort

Objectives:
At the end of the lab, students are expected to be able to do the following:

• Understand the sorting technique concept and the purpose of sorting operation
• Understand the implementation of basic sorting algorithm such as selection sort and
binary sort

Introduction:
A sorting algorithm is used to arrange elements of an array/list in a specific order. For example,

Here, we are sorting the array in ascending order.

There are various sorting algorithms that can be used to complete this operation. And, we can use
any algorithm based on the requirement.

Different Sorting Algorithms are

• Bubble Sort
• Selection Sort
• Insertion Sort
• Merge Sort
• Quick sort

Data Structures and Algorithms (CSC211) Lab Manual

Selection sort

In the selection sort technique, the list is divided into two parts. In one part all elements are sorted
and in another part the items are unsorted. At first, we take the maximum or minimum data from
the array. After getting the data (say minimum) we place it at the beginning of the list by replacing
the data of first place with the minimum data. After performing the array is getting smaller. Thus,
this sorting technique is done.

Working of Selection Sort

1. Set the first element as minimum.

2. Compare minimum with the second element. If the second element is smaller
than minimum, assign the second element as minimum.

Compare minimum with the third element. Again, if the third element is smaller, then
assign minimum to the third element otherwise do nothing. The process goes on until the
last element.

3. After each iteration, minimum is placed in the front of the unsorted list.

Data Structures and Algorithms (CSC211) Lab Manual

 4. For each iteration, indexing starts from the first unsorted element. Step 1 to 3 are repeated
until all the elements are placed at their correct positions.

Data Structures and Algorithms (CSC211) Lab Manual

Data Structures and Algorithms (CSC211) Lab Manual
Selection sort

Code:
#include<iostream>

using namespace std;

int main()
{
int i,j,n,loc,temp,min,a[30];
cout<<"Enter the number of elements:";
cin>>n;
cout<<"\nEnter the elements\n";

for(i=0;i<n;i++)
{
cin>>a[i];
}

for(i=0;i<n-1;i++)
{
min=a[i];
loc=i;
for(j=i+1;j<n;j++)
{
if(min>a[j])
{
min=a[j];
loc=j;
}
}

temp=a[i];
a[i]=a[loc];
a[loc]=temp;

Data Structures and Algorithms (CSC211) Lab Manual

 }

cout<<"\nSorted list is as follows\n";

for(i=0;i<n;i++)
{
cout<<a[i]<<" ";
}

return 0;
}
Output:
Enter the number of elements:5

Enter the elements

1
5
3
7
2

Sorted list is as follows

1 2 3 5 7

Bubble sort

Bubble sort is a sorting algorithm that compares two adjacent elements and swaps them if they
are not in the intended order.

Working of Bubble Sort

Suppose we are trying to sort the elements in ascending order.

1. First Iteration (Compare and Swap)

1. Starting from the first index, compare the first and the second elements.

2. If the first element is greater than the second element, they are swapped.

3. Now, compare the second and the third elements. Swap them if they are not in order.

Data Structures and Algorithms (CSC211) Lab Manual

The above process goes on until the last element.

Remaining Iterations

The same process goes on for the remaining iterations.

After each iteration, the largest element among the unsorted elements is placed at the end.

Data Structures and Algorithms (CSC211) Lab Manual

In each iteration, the comparison takes place up to the last unsorted element.

The array is sorted when all the unsorted elements are placed at their correct positions.

Bubble sort

Code:
#include<iostream>

using namespace std;

int main()
{
int a[50],n,i,j,temp;
cout<<"Enter the size of array: ";
cin>>n;
cout<<"Enter the array elements: ";

Data Structures and Algorithms (CSC211) Lab Manual

 for(i=0;i<n;++i)
cin>>a[i];
for(i=1;i<n;++i)
{
for(j=0;j<(n-i);++j)
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
cout<<"Array after bubble sort:";
for(i=0;i<n;++i)
cout<<" "<<a[i];
return 0;
}
Output:
Enter the size of array: 5

Enter the array elements: 4

Array after bubble sort: 1 2 3 4 6

Data Structures and Algorithms (CSC211) Lab Manual

 IN-LAB TASKS
Task# 1 Take an unsorted array of size 9. Sort the array in ascending order using Selection Sort
technique.

Task# 2 Take an unsorted array of size 9. Sort the array in ascending order using Bubble Sort
technique. Use a condition to stop your program if the array is already sorted or it’s get sorted in
fewer steps than expected.

POST-LAB TASKS
Task# 1 Take an unsorted array of size 5. Sort the array in descending order using Selection Sort
technique. Dry run your code for each iteration. Implement the code in compiler and display the
values of variables.

Data Structures and Algorithms (CSC211) Lab Manual

LAB#4

Recursive Functions
Objectives:
At the end of the lab, students are expected to be able to do the following:

• Understand the concept of recursion

• Understand the difference between the time complexity of loop and recursive functions

Introduction:
Recursion is a widely used phenomenon in computer science used to solve complex problems by
breaking them down into simpler ones. Recursion is a process by which a function
calls itself directly or indirectly. The corresponding function is called as recursive function.

Using recursive algorithms, certain complex problems can be solved quite easily.

Working of recursion in C++

Recursion performs repetition on the function calls, and it stops the execution when the base case
becomes true. A base case condition should be defined in the recursive function to avoid stack
overflow error message. If no base case is defined it leads to infinite recursion. When a function
is called it pushes them into a stack each time for the reserving resources for each repetition calls.
It gives the best at tree traversal.

The recursion continues until some condition is met.

Data Structures and Algorithms (CSC211) Lab Manual

To prevent infinite recursion, if...else statement (or similar approach) can be used where one
branch makes the recursive call and the other doesn't.

Example 1: Factorial of a Number Using Recursion

Code:
// Factorial of n = 1*2*3*...*n

#include <iostream>
using namespace std;

int factorial(int);

int main() {
int n, result;

cout << "Enter a non-negative number: ";

cin >> n;

result = factorial(n);
cout << "Factorial of " << n << " = " << result;
return 0;
}

int factorial(int n) {
if (n > 1) {
return n * factorial(n - 1);
} else {
return 1;
}
}

Output:
Enter a non-negative number: 4

Factorial of 4 = 24

As we can see, the factorial() function is calling itself. However, during each call, we have
decreased the value of n by 1. When n is less than 1, the factorial() function ultimately returns the
output.

Data Structures and Algorithms (CSC211) Lab Manual

Working of recursive function

Data Structures and Algorithms (CSC211) Lab Manual

Example 1: Factorial of a Number Using for Loop

Code:

#include <iostream>
using namespace std;

int main() {
int n = 5;
int factorial = 1;

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

factorial *= i;

cout << factorial;

}
Output:

Factorial of 5 = 120

Advantages and Disadvantages of Recursion

Below are the pros and cons of using recursion in C++

Advantages of C++ Recursion

• It makes our code shorter and cleaner.

• Recursion is required in problems concerning data structures and advanced algorithms,
such as Graph and Tree Traversal.
Disadvantages of C++ Recursion

• It takes a lot of stack space compared to an iterative program.

• It uses more processor time.
• It can be more difficult to debug compared to an equivalent iterative program.

Data Structures and Algorithms (CSC211) Lab Manual

 IN-LAB TASKS
Task# 1 Implement code for multiplication using addition in C++ compiler using both recursive
functions and loop. And compare the execution time for both.

Task# 2 Write an algorithm for calculating factorial and implement the code in compiler using
both recursive functions and loop. And compare the execution time for both.

POST-LAB TASKS:
Task# 1 Fibonacci series is the sequence in which each number is the sum of the two numbers that
precede it. Write the code to find the next number of the Fibonacci series and also draw the flow
diagram to find the 5th number of the sequence.

Data Structures and Algorithms (CSC211) Lab Manual

LAB#5

Insertion Sort and Merge Sort

Objectives:
At the end of the lab, students are expected to be able to do the following:

• Understand the insertion sort technique and its implementation

• Understand the merge sort technique and its implementation

Introduction:
A sorting algorithm is used to arrange elements of an array/list in a specific order. For example,

Here, we are sorting the array in ascending order.

There are various sorting algorithms that can be used to complete this operation. And, we can use
any algorithm based on the requirement.

Different Sorting Algorithms are

• Bubble Sort
• Selection Sort
• Insertion Sort
• Merge Sort
• Quick sort

Data Structures and Algorithms (CSC211) Lab Manual

Insertion sort

Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards
in your hands. The array is virtually split into a sorted and an unsorted part. Values from the
unsorted part are picked and placed at the correct position in the sorted part.

Working of Insertion Sort

Suppose we need to sort the following array.

1. The first element in the array is assumed to be sorted. Take the second element and store
it separately in key.

Compare key with the first element. If the first element is greater than key, then key is
placed in front of the first element.

2. Now, the first two elements are sorted.

Take the third element and compare it with the elements on the left of it. Placed it just
behind the element smaller than it. If there is no element smaller than it, then place it at the
beginning of the array.

Data Structures and Algorithms (CSC211) Lab Manual

 3. Similarly, place every unsorted element at its correct position.

Data Structures and Algorithms (CSC211) Lab Manual

Insertion sort

Code:
#include<iostream>
using namespace std;

int main()
{
int data[5]={7,8,3,1,6};
int item, n=5;
int pass, insertIndex;

for(pass=1; pass<n;pass++)
{
item = data[pass];
insertIndex = pass;
while((insertIndex >0) &&
(data[insertIndex -1]>item))
{
//insert the right item
data[insertIndex]=
data[insertIndex -1];
insertIndex --;
}
data[insertIndex] = item;
//insert item at the right place

Data Structures and Algorithms (CSC211) Lab Manual

 }

cout<<"The sorted array is =\n";

for(int i=0;i<n;i++)
{
cout<<data[i]<<"\t";
}
}
Output:
The sorted array is =

1 3 6 7 8

Insertion Sort Applications

The insertion sort is used when:

• The array is has a small number of elements

• There are only a few elements left to be sorted

Merge sort

The merge sort technique is based on divide and conquer technique. We divide the while data
set into smaller parts and merge them into a larger piece in sorted order. It is also very effective
for worst cases because this algorithm has lower time complexity for worst case also.

Divide and Conquer Strategy

Using the Divide and Conquer technique, we divide a problem into subproblems. When the
solution to each subproblem is ready, we 'combine' the results from the subproblems to solve the
main problem.

Suppose we had to sort an array A. A subproblem would be to sort a sub-section of this array
starting at index p and ending at index r, denoted as A[p..r].

Divide

If q is the half-way point between p and r, then we can split the subarray A[p..r] into two
arrays A[p..q] and A[q+1, r].

Data Structures and Algorithms (CSC211) Lab Manual

Conquer

In the conquer step, we try to sort both the subarrays A[p..q] and A[q+1, r]. If we haven't yet
reached the base case, we again divide both these subarrays and try to sort them.

Combine

When the conquer step reaches the base step and we get two sorted subarrays A[p..q] and A[q+1,
r] for array A[p..r], we combine the results by creating a sorted array A[p..r] from two sorted
subarrays A[p..q] and A[q+1, r].

Working of merge sort

Data Structures and Algorithms (CSC211) Lab Manual

Merge sort

Code:
#include<iostream>
using namespace std;

void merge(int theArray[],

int first, int mid, int last)
{
//const int MAX_SIZE = maxNmbrItemInArry;
int tempArray[9]; // temp array
int first1 = first; // first subarray begin
int last1 = mid; // end of first subarray
int first2 = mid + 1; // secnd subarry begin
int last2 = last; // end of secnd subarry
// while both subarrays are not empty,
// copy the smaller item into the
// temporary array
int index = first1;
// next available location in tempArray
for (; (first1 <= last1) && (first2 <= last2); ++index)
{
if (theArray[first1] < theArray[first2])
{
tempArray[index] = theArray[first1]; ++first1; }
else
{
tempArray[index] = theArray[first2]; ++first2;
}
} // end if

for (; first1 <= last1; ++first1, ++index)

tempArray[index] = theArray[first1];
// finish off the second
// subarray, if necessary
for (; first2 <= last2; ++first2, ++index)
tempArray[index] = theArray[first2];
// copy the result back
// into the original
// array
for (index = first; index <= last; ++index)
theArray[index] = tempArray[index];
} // end merge function

void mergesort(int theArray[],int first,int last)

{
if (first < last)
{ // sort each half
int mid = (first + last)/2;
// index of midpoint
// sort left half theArray[first..mid]
mergesort(theArray, first, mid);
// sort right half theArray[mid+1..last]

Data Structures and Algorithms (CSC211) Lab Manual

 mergesort(theArray, mid+1, last);
// merge the two halves
merge(theArray, first, mid, last);
} // end if
} // end mergesort

int main()
{
int arr[9] = {5, 15, 7, 2, 4, 1, 8, 10,3};
int n = 9 ,first=0, last=8;
//const int MAX_SIZE = maxNmbrItemInArry;
mergesort(arr, 0, n - 1);

cout<<"The sorted array is =\n";

for(int i=0;i<n;i++)
{
cout<<arr[i]<<"\t";
}
return 0;
}

Output:
The sorted array is =

1 2 3 4 5 7 8 10 15

Merge Sort Applications

• Inversion count problem

• External sorting

• E-commerce applications

Data Structures and Algorithms (CSC211) Lab Manual

 IN-LAB TASKS
Task# 1 Take an unsorted array of size 9. Sort the array in ascending order using Insertion Sort
technique.

Task# 2 Take an unsorted array of size 7. Sort the array in ascending order using Merge Sort
technique. Show how the array will be divided to sub-arrays until each array consists of only one
element.

POST-LAB TASKS
Task# 1 Take an unsorted array of size 7. Sort the array in descending order using Merge Sort
technique. Dry run your code to merge the last sub-arrays together to make the final sorted array.

Data Structures and Algorithms (CSC211) Lab Manual

LAB#6

Quick Sort
Objectives:
At the end of the lab, students are expected to be able to do the following:

• Understand the concept of Quick sort algorithm

• Learn the implementation of Quick sort algorithm

Introduction:
A sorting algorithm is used to arrange elements of an array/list in a specific order. For example,

Here, we are sorting the array in ascending order.

There are various sorting algorithms that can be used to complete this operation. And, we can use
any algorithm based on the requirement.

Different Sorting Algorithms are

• Bubble Sort
• Selection Sort
• Insertion Sort
• Merge Sort
• Quick sort

Data Structures and Algorithms (CSC211) Lab Manual

Quick sort

Quick sort is a highly efficient sorting algorithm and is based on partitioning of array of data into
smaller arrays. A large array is partitioned into two arrays one of which holds values smaller than
the specified value, say pivot, based on which the partition is made and another array holds values
greater than the pivot value.

Quicksort partitions an array and then calls itself recursively twice to sort the two resulting
subarrays. This algorithm is quite efficient for large-sized data sets as its average and worst-case
complexity are O(n2), respectively.

Quicksort is a sorting algorithm based on the divide and conquer approach where

1. An array is divided into subarrays by selecting a pivot element (element selected from the
array).

While dividing the array, the pivot element should be positioned in such a way that
elements less than pivot are kept on the left side and elements greater than pivot are on the
right side of the pivot.

2. The left and right subarrays are also divided using the same approach. This process
continues until each subarray contains a single element.

3. At this point, elements are already sorted. Finally, elements are combined to form a sorted
array.

Working of Quicksort Algorithm

1. Select the Pivot Element

There are different variations of quicksort where the pivot element is selected from
different positions. Here, we will be selecting the rightmost element of the array as the
pivot element.

2. Rearrange the Array

Now the elements of the array are rearranged so that elements that are smaller than the
pivot are put on the left and the elements greater than the pivot are put on the right.

Data Structures and Algorithms (CSC211) Lab Manual

 Here's how we rearrange the array

1. A pointer is fixed at the pivot element. The pivot element is compared with the elements
beginning from the first index.

2. If the element is greater than the pivot element, a second pointer is set for that element.

3. Now, pivot is compared with other elements. If an element smaller than the pivot element is
reached, the smaller element is swapped with the greater element found earlier.

4. Again, the process is repeated to set the next greater element as the second pointer. And,
swap it with another smaller element.

Data Structures and Algorithms (CSC211) Lab Manual

 5. Finally, the pivot element is swapped with the second pointer.

3. Divide Subarrays
Pivot elements are again chosen for the left and the right sub-parts separately. And, step 2 is
repeated.

The subarrays are divided until each subarray is formed of a single element. At this point, the
array is already sorted.

Quick sort

Code:
#include<iostream>
using namespace std;

int partition(int T[], int first,int last)

Data Structures and Algorithms (CSC211) Lab Manual

 {
int pivot, temp;
int loop, cutPoint, bottom, top;
pivot=T[first];
bottom=first; top= last;
loop=1; //always TRUE
while (loop) {
while (T[top]>pivot){
// find smaller value than
// pivot from top array
top--;
}
while(T[bottom]<pivot){
//find larger value than
//pivot from bottom
bottom++;
}

if (bottom<top) {
// change pivot place
temp=T[bottom];
T[bottom]=T[top];
T[top]=temp;
}
else {
loop=0; //loop false
cutPoint = top;
}//end if
}// end while
return cutPoint;
}//end function

void quickSort (int T[],

int first , int last)
{
int cut;
if (first<last){
cut = partition(T, first,last);
quickSort(T, first,cut);
quickSort (T, cut+1, last);
}
}

int main()
{
int arr[9] = {5, 15, 7, 2, 4, 1, 8, 10,3};
int n = 9 ,first=0, last=8;
quickSort(arr, 0, n - 1);

cout<<"The sorted array is =\n";

for(int i=0;i<n;i++)
{
cout<<arr[i]<<"\t";
}
return 0;

Data Structures and Algorithms (CSC211) Lab Manual

 }
Output:
The sorted array is =

1 2 3 4 5 7 8 10 15

Quicksort Applications

Quicksort algorithm is used when

• the programming language is good for recursion

• time complexity matters

• space complexity matters

Data Structures and Algorithms (CSC211) Lab Manual

 IN-LAB TASKS
Task# 1 Take an unsorted array of size 7. Sort the array in ascending order using Quick Sort
technique. Show how the array will be divided to sub-arrays until each array consists of only one
element.

POST-LAB TASKS
Task# 1 Take an unsorted array of size 7. Sort the array in descending order using Quick Sort
technique. Take the first element as pivot element and dry run your code to find the right position
of that pivot element.

Data Structures and Algorithms (CSC211) Lab Manual

LAB#7

Structures and Classes

Objectives:
At the end of the lab, students are expected to be able to do the following:

• To understand and declare user-defined data types i.e., structures

• To declare classes, member functions and member variables of a class
• Understand the importance and use of constructors and destructors

Introduction:
Structures
Many time we have to store the elements of the different data types. Structure is composition of
the different variables of different data types, grouped under same name.
Example
struct {
char name[64];
char course[128];
int age;
int year;
} student;
Definitions of Structures

Each member declared in Structure is called member.

char name[64];

char course[128];

int age;

int year;

Are some examples of members defined above.

Name given to structure is called as tag

student

Structure Initialization

When we declare a structure then memory won’t be allocated for the structure. i.e only writing
below declaration statement will never allocate memory

Data Structures and Algorithms (CSC211) Lab Manual

struct student

int mark1;

int mark2;

int mark3;

};

We need to initialize structure variable to allocate some memory to the structure.

struct student s1 = {89,54,65};

We can initialize structure variable in different ways

1. Declare and Initialize

struct student

char name[20];

int roll;

float marks;

}std1 = { "Pritesh",67,78.3 };

In the above code snippet, the structure is declared and as soon as after declaration we have
initialized the structure variable.
std1 = {"Pritesh",67,78.3};

This is the code for initializing structure variable.

2: Declaring and Initializing Multiple Variables

struct student

char name[20];

Data Structures and Algorithms (CSC211) Lab Manual

 int roll;

float marks;

std1 = {"Pritesh",67,78.3};

std2 = {"Don",62,71.3};

In this example, we have declared two structure variables in above code. After declaration of
variable we have initialized two variables.
std1 = {"Pritesh",67,78.3};

std2 = {"Don",62,71.3};

3: Initializing Single member

struct student

int mark1;

int mark2;

int mark3;

} sub1={67};

Though there are three members of structure, only one is initialized, and then remaining two
members are initialized with Zero. If there are variables of other data type then their initial values
will be

Data Type Default value if not initialized

Integer 0

Float 0.00

Char NULL

Data Structures and Algorithms (CSC211) Lab Manual

4: Initializing inside main

struct student

int mark1;

int mark2;

int mark3;

};

void main()

struct student s1 = {89,54,65};

- - - - --

};

Example: Passing Structures to Function

Code:
#include<iostream>
using namespace std;

struct student
{
int id;
char name[20];
float percentage;
};

void func(student);

int main()
{
student record;
record.id=1;
cout<<"Enter the name= ";
cin>>record.name;
record.percentage = 86.5;
func(record);
return 0;
}

void func(student record)

Data Structures and Algorithms (CSC211) Lab Manual

 {
cout<<" Id is: "<<record.id<<endl;
cout<<" Name is: "<<record.name<<endl;
cout<<" Percentage is: "<<record.percentage<<endl;
}
Output:
Enter the name= xyz

Id is: 1

Name is: xyz

Percentage is: 86.5

Example: Storing date of birth

Code:
#include<iostream>
using namespace std;

struct Date
{
int day;
int month;
int year;
};

int main( )
{
Date birthDate;
cout<<"Enter day of birth"; //enter day
cin>>birthDate.day; //display day
cout<<"Enter month of birth"; //enter month
cin>>birthDate.month; //display month
cout<<"Enter year of birth"; //enter year
cin>>birthDate.year; //display year
cout<<"your date of birth is: "
<<birthDate.day<<"/"<<birthDate.month<<"/"<<birthDate.year<<”\n”;
}
Output:
Enter day of birth: 12

Enter month of birth: 3

Enter year of birth: 98

Your date of birth is: 12/3/98

Data Structures and Algorithms (CSC211) Lab Manual

Classes
Classes are collections of data related to a single object type along with functions to access and
manipulate the data. The functions usually are the only way to modify and access the variables.
This might seem silly at first, but the idea to make programs more modular - the principle itself is
called "encapsulation". The key idea is that the outside world doesn't need to know exactly what
data is stored inside the class -- it just needs to know which functions it can use to access that data.
This allows the implementation to change more easily because nobody should have to rely on it
except the class itself.

The fundamental idea behind object-oriented languages is to combine into a single unit both data
and the functions that operate on that data. Such a unit is called an object. A class serves as a plan,
or blueprint. It specifies what data and what functions will be included in objects of that class. An
object is often called an “instance” of a class Syntax:

Classes are generally declared using the keyword class, with the following format:

Data Structures and Algorithms (CSC211) Lab Manual

Example:

Code:

Data Abstraction

Abstraction is the process of recognizing and focusing on important characteristics of a situation

or object and leaving/filtering out the un-wanted characteristics of that situation or object. For
example, a person will be viewed differently by a doctor and an employer.

• A doctor sees the person as patient. Thus he is interested in name, height, weight, age,
blood group, previous or existing diseases etc of a person

Data Structures and Algorithms (CSC211) Lab Manual

 • An employer sees a person as an employee. Therefore, employer is interested in name, age,
health, degree of study, work experience etc of a person.

Member Functions and Variables

Member variables represent the characteristics of the object and member functions represent the
behavior of the object. For example length & width are the member variables of class Rectangle
and set_values(int,int), area() are the member functions.

Example: Area of rectangle

Code:
#include <iostream>
using namespace std;
class Rectangle
{
private:
int length, width;

public:
void set_values(int,int); //set the values of length and width

int area ()
{
return (length*width);
}
};
void Rectangle : : set_values (int l, int w)
{
length = l;
width = w;
}
int main ()
{
Rectangle rect;
rect.set_values (3,4); //pass values to set length and width
cout<< "area =" <<rect.area( );
return 0;
}
Output:
area= 12

Constructors

It is a special function that is automatically executed when an object of that class is created. It has
no return type and has the same name as that of the class. It is normally defined in classes to
initialize data members.

Data Structures and Algorithms (CSC211) Lab Manual

Syntax
class_name( )

// Constructor body

Destructors

It is a special function that is automatically executed when an object of that class is destroyed. It
has no return type and has the same name as that of the class preceded by tild (~) character. Unlike
constructors, destructors cannot take arguments.

Syntax
~ class_name ()

// Destructor body

Example: Constructors and destructors

Code:
class counter
{
private:
int count;
public:
counter()
{
count=0;
cout<<"I am a constructor"<<endl;
}
~counter()
{
cout<<"I am a destructor"<<endl;
}
};
int main( )
{
counter c;
}

Data Structures and Algorithms (CSC211) Lab Manual

 IN-LAB TASKS
Task# 1 Write a program that declares a structure to store id, pages and price of a book. It defines
an array of structures to store the record of five books. It inputs the records of the five books and
displays the record of the most costly book.

Task# 2 Create a class named Cylinder. Write the necessary variables and functions to calculate
area (curved surface area) and volume of a cylinder. Create functions outside of the class using
scope resolution operator.

POST-LAB TASKS
Task# 1 Create a class named Time, the data members are hours, minutes and seconds. Write a
function to read the data members supplied by the user, write a function to display the data
members in standard (24) hour and also in (12) hour format.

Data Structures and Algorithms (CSC211) Lab Manual

LAB#8

Array implementation of Stack

Objectives:
At the end of the lab, students are expected to be able to do the following:

• Understand the various operations on stacks in C++

• Learn to write functions to insert, display, change values in stack

Introduction:
Stacks are the most important in data structures. The notation of a stack in computer science is the
same as the notion of the Stack to which you are accustomed in everyday life. For example, a
recursion program on which function call itself, but what happen when a function which is calling
itself call another function. Such as a function ‘A’ call function ‘B’ as a recursion. So the firstly
function ‘B’ is call in ‘A’ and then function ‘A’ is work. So this is a Stack. This is a Stack is First
In Last Out data structure.

LIFO Principle of Stack

In programming terms, putting an item on top of the stack is called push and removing an item is
called pop.

Data Structures and Algorithms (CSC211) Lab Manual

Insertions in Stack

In Stacks, we know the array work, sometimes we need to modified it or add some element in it.
For that purpose we use insertion scheme. By the use of this scheme we insert any element in
Stacks using array. In Stack we maintain only one node which is called TOP. And Push
terminology is used as insertions.

Inserting values in Stack

Code:
void push(int val)
{
if(isFull())
{
cout<<"Stack overflow"<<endl;
}
else
{
top++;
arr[top]=val;
}
}

Display of Stack

In displaying section, the elements of Stacks are been display by using loops and variables as a
reverse order. Such that, last element is display at on first and first element enters display at on
last.

Displaying values of Stack

Code:
void display()
{
cout<<"All value in the Stack are "<<endl;
for(int i=5; i>=0; i--)
{
cout<<arr[i]<<endl;
}
}

Data Structures and Algorithms (CSC211) Lab Manual

Deletion in Stack

In the deletion process, the element of the Stack is deleted on the same node which is called TOP.
In stacks, it’s just deleting the index of the TOP element which is added at last. In Stacks Pop
terminology is used as deletion.

Displaying values of Stack

Code:
int pop()
{
if(isEmpty())
{
cout<<"Stack underflow"<<endl;
return 0;
}
else
{
int popvalue=arr[top];
arr[top]=0;
top--;
return popvalue;
}
}

Stack operations (Complete code)

Code:
#include<iostream>
using namespace std;

class Stack
{
private:
int top;
int arr[6];

public:

Stack()
{
top=-1;
for(int i=0; i<6; i++)
{
arr[i]=0;
}
}

bool isEmpty()
{
if(top==-1)

Data Structures and Algorithms (CSC211) Lab Manual

 return true;
else
return false;
}

bool isFull()
{
if(top==5)
return true;
else
return false;
}

void push(int val)

{
if(isFull())
{
cout<<"Stack overflow"<<endl;
}
else
{
top++;
arr[top]=val;
}
}

int pop()
{
if(isEmpty())
{
cout<<"Stack underflow"<<endl;
return 0;
}
else
{
int popvalue=arr[top];
arr[top]=0;
top--;
return popvalue;
}
}

int count()
{
return(top+1);
}

int peek(int pos)

{
if(isEmpty())
{
cout<<"Stack underflow"<<endl;
return 0;
}
else
{
return arr[pos];

Data Structures and Algorithms (CSC211) Lab Manual

 }
}

void change(int pos, int val)

{
arr[pos]=val;
cout<<"Value changed at location "<<pos<<endl;
}

void display()
{
cout<<"All value in the Stack are "<<endl;
for(int i=5; i>=0; i--)
{
cout<<arr[i]<<endl;
}
}

};

int main()
{
Stack s1;
int option,position,value;

do
{
cout<<"What operation do you want to perform? Select option
number accordingly. Enter 0 to exit. "<<endl;
cout<<"1. Push"<<endl;
cout<<"2. Pop"<<endl;
cout<<"3. isEmpty()"<<endl;
cout<<"4. isFull()"<<endl;
cout<<"5. peek()"<<endl;
cout<<"6. count()"<<endl;
cout<<"7. change()"<<endl;
cout<<"8. display()"<<endl;
//cout<<"9. Clear Screen"<<endl<<endl;

cin>>option;
switch(option)
{
case 1:
cout<<"Enter an item to push in the stack"<<endl;
cin>>value;
s1.push(value);
break;

case 2:
cout<<"Pop Function called - poped value:
"<<s1.pop()<<endl;
break;

case 3:
if(s1.isEmpty())
cout<<"Stack is Empty"<<endl;

Data Structures and Algorithms (CSC211) Lab Manual

 else
cout<<"Stack is not Empty"<<endl;
break;

case 4:
if(s1.isFull())
cout<<"Stack is Full"<<endl;
else
cout<<"Stack is not Full"<<endl;
break;

case 5:
cout<<"Enter position of item you want to peek:
"<<endl;
cin>>position;
cout<<"Peek function called - Value at position
"<<position<<"is "<<s1.peek(position)<<endl;
break;

case 6:
cout<<"Count Function called - Number of items in
the Stack are: "<<s1.count()<<endl;
break;

case 7:
cout<<"Change function called - "<<endl;
cout<<"Enter position of item you want to change :
";
cin>>position;
cout<<endl;
cout<<"Enter value of item you want to change : ";
cin>>value;
s1.change(position,value);
break;

case 8:
cout<<"Display Function Called - "<<endl;
s1.display();
break;

case 9:
system("cls");
break;

default:
cout<<"Enter proper option number "<<endl;

}while(option!=0);

Data Structures and Algorithms (CSC211) Lab Manual

 Output:
What operation do you want to perform? Select option number accordingly. Enter
0 to exit.

1. Push

2. Pop

3. isEmpty()

4. isFull()

5. peek()

6. count()

7. change()

8. display()

Applications of Stack Data Structure

Although stack is a simple data structure to implement, it is very powerful. The most common uses
of a stack are:

• To reverse a word - Put all the letters in a stack and pop them out. Because of the LIFO
order of stack, you will get the letters in reverse order.

• In compilers - Compilers use the stack to calculate the value of expressions like 2 + 4 / 5
* (7 - 9) by converting the expression to prefix or postfix form.

• In browsers - The back button in a browser saves all the URLs you have visited previously
in a stack. Each time you visit a new page, it is added on top of the stack. When you press
the back button, the current URL is removed from the stack, and the previous URL is
accessed.

Data Structures and Algorithms (CSC211) Lab Manual

 IN-LAB TASKS
Task# 1 Define and explain Stack. Write a function to create a stack of size 7. Initialize it with
zero values. Write functions for entering and deleting a value from the top of stack using push()
and pull() functions.

POST-LAB TASKS
Task# 1 Implement all the functions related to stack (createStack(), push(), pull(), isEmpty(),
isFull(), stackTop()) in compiler. Make a menu to be displayed in console window so the user
can select the operations he wants to perform on stack.

Data Structures and Algorithms (CSC211) Lab Manual

LAB#9

Array implementation of Queue

Objectives:
At the end of the lab, students are expected to be able to do the following:

• Understand the concept of linear queue and circular queue in C++

• Learn to apply different operations such as enqueue, dequeue etc., on queue

Introduction:
Queues using Arrays

This manual discusses an important data structure, called a queue. The notion of a queue in
computer science is the same as the notion of the queues to which you are accustomed in everyday
life. There are queues of customers in a bank or in a grocery store and queues of cars waiting to
pass through a tollbooth. Similarly, because a computer can send a print request faster than a printer
can print, a queue of documents is often waiting to be printed at a printer. The general rule to
process elements in a queue is that the customer at the front of the queue is served next and that
when a new customer arrives, he or she stands at the end of the queue. That is, a queue is a First
In First Out data structure.

A queue is a set of elements of the same type in which the elements are added at one end, called
the back or rear, and deleted from the other end, called the front. For example, consider a line of
customers in a bank, wherein the customers are waiting to withdraw/deposit money or to conduct
some other business. Each new customer gets in the line at the rear. Whenever a teller is ready for
a new customer, the customer at the front of the line is served.

The rear of the queue is accessed whenever a new element is added to the queue, and the front of
the queue is accessed whenever an element is deleted from the queue. As in a stack, the middle
elements of the queue are inaccessible, even if the queue elements are stored in an array.

Queue: A data structure in which the elements are added at one end, called the rear, and deleted
from the other end, called the front; a First In First Out (FIFO) data structure.

Queues may be represented in the computer in various ways, usually by means at one way list or
linear arrays. Unless otherwise stated or implied each of our queues will be maintained by a linear
array QUEUE and two pointer variable FRONT containing the location of the front element of the
queue and REAR containing the location of the rear element of the queue. The condition FRONT
= NULL will indicate that the queue is empty.

Data Structures and Algorithms (CSC211) Lab Manual

Queues can be implemented dynamically or statically.

Queue follows the First In First Out (FIFO) rule - the item that goes in first is the item that
comes out first.

Basic Operations of Queue

A queue is an object (an abstract data structure - ADT) that allows the following operations:

• Enqueue: Add an element to the end of the queue

• Dequeue: Remove an element from the front of the queue

• IsEmpty: Check if the queue is empty

• IsFull: Check if the queue is full

• Peek: Get the value of the front of the queue without removing it

Working of Queue

Queue operations work as follows:

• two pointers FRONT and REAR

• FRONT track the first element of the queue

• REAR track the last element of the queue

• initially, set value of FRONT and REAR to -1

Enqueue Operation

• check if the queue is full

• for the first element, set the value of FRONT to 0

• increase the REAR index by 1

• add the new element in the position pointed to by REAR

Data Structures and Algorithms (CSC211) Lab Manual

 Code:
void enQueue(int value)
{
if(isFull())
{
cout<<"Queueu is full"<<endl;
return;
}
else if(isEmpty())
{
rear=front=0;
array[rear]=value;
}
else
{
rear++;
array[rear]=value;
}
}

Dequeue Operation

• check if the queue is empty

• return the value pointed by FRONT

• increase the FRONT index by 1

• for the last element, reset the values of FRONT and REAR to -1

Code:
int deQueue()
{
int x;
if(isEmpty())
{
cout<<"Queue is empty"<<endl;
return 0;
}
else if(front==rear)
{
x=array[front];
array[front]=0;
rear=front=-1;
return x;
}
else
{
x=array[front];

Data Structures and Algorithms (CSC211) Lab Manual

 array[front]=0;
front++;
return x;
}
}

Working of Queue:

Data Structures and Algorithms (CSC211) Lab Manual

Applications of Queue

• CPU scheduling, Disk Scheduling

• When data is transferred asynchronously between two processes. The queue is used for
synchronization. For example: IO Buffers, pipes, file IO, etc.

• Handling of interrupts in real-time systems.

• Call Center phone systems use Queues to hold people calling them in order.

Circular Queue

A circular queue is the extended version of a regular queue where the last element is connected
to the first element. Thus, forming a circle-like structure.

The circular queue solves the major limitation of the normal queue. In a normal queue, after a bit
of insertion and deletion, there will be non-usable empty space.

Here, indexes 0 and 1 can only be used after resetting the queue (deletion of all elements). This
reduces the actual size of the queue.

How Circular Queue Works

Circular Queue works by the process of circular increment i.e., when we try to increment the
pointer and we reach the end of the queue, we start from the beginning of the queue.

Data Structures and Algorithms (CSC211) Lab Manual

IN-LAB TASKS:
Task# 1 Define and explain Queue. Write a function to create a Queue of size 7. Initialize it with
zero values. Write functions for entering and deleting a value from the Queue using enQueue()
and deQueue() functions.

POST-LAB TASKS:
Task# 1 Write a function to create a circular Queue of size 5. Initialize it with zero values. Write
functions for entering and deleting a value from the Queue using enQueue() and deQueue()
functions. With the help of dry run, justify how circular Queue overcomes the issues related to
simple Queue.

Data Structures and Algorithms (CSC211) Lab Manual

LAB#10

Linked-list Implementation
Objectives:
At the end of the lab, students are expected to be able to do the following:

• Understand the concept of linked-list in C++

• Learn to apply different operations such as insertion, deletion, traversal etc., on linked-list

Introduction:
A linked list is a collection of components, called nodes. Every node (except the last node) contains
the address of the next node. Thus, every node in a linked list has two components: one to store
the relevant information (that is, data) and one to store the address, called the link, of the next node
in the list. The address of the first node in the list is stored in a separate location, called the head
or first. Figure 1 is a pictorial representation of a node.

Each node in the linked list contains:

1. One or more members that represent data (e.g. inventory records, customer names, addresses,
telephone numbers, etc).

2. A pointer, that can point to another node.

A linked list is a linear data structure that includes a series of connected nodes. Here, each node
stores the data and the address of the next node. For example,

You have to start somewhere, so we give the address of the first node a special name called HEAD.
Also, the last node in the linked list can be identified because its next portion points to NULL.

Linked lists can be of multiple types: singly, doubly, and circular linked list. In this article, we
will focus on the singly linked list.

Representation of Linked List

Let's see how each node of the linked list is represented. Each node consists:

• A data item

Data Structures and Algorithms (CSC211) Lab Manual

 • An address of another node

We wrap both the data item and the next node reference in a class as:

Linked-list class:

Code:
class Node
{
public:
double data; // data
Node* next; // pointer to next node
};

Understanding the class of a linked list node is the key to having a grasp on it.

Each class node has a data item and a pointer to another class node. The following code explains
it clearly.

Code:
class List
{

private:
Node* head;
int length;

public:
// constructor
List()
{
head = NULL;
length =0;
}

bool IsEmpty()
{
return head == NULL;
}

Node* InsertNode(double x);

int FindNode(double x);
void DeleteNode(double x);
void DisplayList(void);

~List();
};

Data Structures and Algorithms (CSC211) Lab Manual

There are various linked list operations that allow us to perform different actions on linked lists.
For example, the insertion operation adds a new element to the linked list.

Here's a list of basic linked list operations

• Traversal - access each element of the linked list

• Insertion - adds a new element to the linked list

• Deletion - removes the existing elements

• Search - find a node in the linked list

• Sort - sort the nodes of the linked list

Traverse a Linked List

Displaying the contents of a linked list is very simple. We keep moving the currNode to the next
one and display its contents.

When currNode is NULL, we know that we have reached the end of the linked list so we get out
of the while loop.

Linked-list traversal:

Code:
void List::DisplayList()
{
int num = 0;
Node* currNode = head;
while (currNode != NULL)
{
cout << currNode->data << endl;
currNode = currNode->next;
num++;
}
cout<<"Number of nodes in the list: " << num << endl;
}

Insert a Node

• Allocate memory for new node

• Store data

• Change next of new node to point to head

• Change head to point to recently created node

Data Structures and Algorithms (CSC211) Lab Manual

Node Insertion in linked-list

Code:
Node* List::InsertNode(double x)
{
Node* currNode = head;
Node* prevNode = NULL;
// while (currNode!=NULL && x > currNode->data)
// {
// prevNode = currNode;
// currNode = currNode->next;
// }
Node* newNode = new Node;
newNode->data = x;

if (prevNode == NULL)
{
newNode->next = head;
head = newNode;
}
else
{
newNode->next = prevNode->next;
prevNode->next = newNode;
}
length++;
return newNode;
}

Delete a Node:

• Traverse to element before the element to be deleted

• Change next pointers to exclude the node from the chain

Node deletion in linked-list

Code:
void List::DeleteNode(double x)
{
Node* prevNode = NULL;
Node* currNode = head;
int currIndex = 1;

while (currNode && currNode->data != x)

{
prevNode = currNode;
currNode = currNode->next;
currIndex++;

Data Structures and Algorithms (CSC211) Lab Manual

 }
if (currNode)
{
if (prevNode)
{
prevNode->next = currNode->next;
delete currNode;
}
else
{
head = currNode->next;
delete currNode;
}
cout << "Node "<< x << "is deleted";
length--;
}
cout << "Node " << x << "is not in list.";
}

Search an Element on a Linked List

You can search an element on a linked list using a loop using the following steps. We are
finding item on a linked list.

• Make head as the current node.

• Run a loop until the current node is NULL because the last element points to NULL.

• In each iteration, check if the key of the node is equal to item. If it the key matches the
item, return true otherwise return false.

Finding Node in linked-list

Code:
int List::FindNode(double x)
{
Node* currNode = head;
int currIndex = 1;
while (currNode!=NULL && currNode->data != x)
{
currNode = currNode->next;
currIndex++;
}
if (currNode!=NULL)
return currIndex;
else
return 0;
}

Data Structures and Algorithms (CSC211) Lab Manual

Linked List Applications

• Dynamic memory allocation

• Implemented in stack and queue

• In undo functionality of softwares

• Hash tables, Graphs

Data Structures and Algorithms (CSC211) Lab Manual

 IN-LAB TASKS
Task# 1 Write a function to create a linked-list. Write functions to enter a new node and delete
any node from the linked-list. Dry run your code for deleting second-last node from the linked-
list having 5 nodes.

POST-LAB TASKS
Task# 1 Implement enQueue and deQueue functions of Queue data structure using linked-list.

Data Structures and Algorithms (CSC211) Lab Manual

LAB#11

Binary Search Tree Implementation

Objectives:
At the end of the lab, students are expected to be able to do the following:

• Understand the concept of tree, binary tree and binary search tree in C++
• Learn to apply different operations such as insertion, deletion of a Node etc., on Binary
Search Tree

Introduction:
A tree is a nonlinear hierarchical data structure that consists of nodes connected by edges.

Why Tree Data Structure?

Other data structures such as arrays, linked list, stack, and queue are linear data structures that
store data sequentially. In order to perform any operation in a linear data structure, the time
complexity increases with the increase in the data size. But, it is not acceptable in today's
computational world.

Different tree data structures allow quicker and easier access to the data as it is a non-linear data
structure.

Tree Terminologies

Node

A node is an entity that contains a key or value and pointers to its child nodes.

The last nodes of each path are called leaf nodes or external nodes that do not contain a
link/pointer to child nodes.

Data Structures and Algorithms (CSC211) Lab Manual

The node having at least a child node is called an internal node.

Edge

It is the link between any two nodes.

Root

It is the topmost node of a tree.

Height of a Node

The height of a node is the number of edges from the node to the deepest leaf (ie. the longest
path from the node to a leaf node).

Depth of a Node

The depth of a node is the number of edges from the root to the node.

Height of a Tree

The height of a Tree is the height of the root node or the depth of the deepest node.

The depth of a node is the number of edges from the root to the node.

Height of a Tree

The height of a Tree is the height of the root node or the depth of the deepest node.

Data Structures and Algorithms (CSC211) Lab Manual

Binary Tree

A binary tree is a tree data structure in which each parent node can have at most two children.
Each node of a binary tree consists of three items:

• data item

• address of left child

• address of right child

Binary Tree Representation

A node of a binary tree is represented by a structure containing a data part and two pointers to
other structures of the same type.

Binary search tree is a data structure that quickly allows us to maintain a sorted list of numbers.

• It is called a binary tree because each tree node has a maximum of two children.

• It is called a search tree because it can be used to search for the presence of a number
in O(log(n)) time.

The properties that separate a binary search tree from a regular binary tree is

1. All nodes of left subtree are less than the root node

Data Structures and Algorithms (CSC211) Lab Manual

 2. All nodes of right subtree are more than the root node

3. Both subtrees of each node are also BSTs i.e., they have the above two properties

The binary tree on the right isn't a binary search tree because the right subtree of the node "3"
contains a value smaller than it.

TreeNode class

Code:
class TreeNode
{
public:
int value;
TreeNode *left;
TreeNode *right;

TreeNode()
{
value=0;
right=NULL;
left =NULL;
}

TreeNode(int v)
{
value=v;
right=NULL;
left =NULL;
}

};

Data Structures and Algorithms (CSC211) Lab Manual

Insert Operation

Inserting a value in the correct position is similar to searching because we try to maintain the rule
that the left subtree is lesser than root and the right subtree is larger than root.

Node Insertion

Code:
void insertNode(TreeNode * new_node)
{
if (root == NULL)
{
root = new_node;
cout << "Value Inserted as root node!" << endl;
}
else
{
TreeNode * temp = root;
while (temp != NULL) {
if (new_node -> value == temp -> value)
{
cout << "Value Already exist," <<
"Insert another value!" << endl;
return;
}
else if ((new_node -> value < temp -> value) && (temp ->
left == NULL))
{
temp -> left = new_node;
cout << "Value Inserted to the left!" << endl;
break;
}
else if (new_node -> value < temp -> value)
{
temp = temp -> left;
}
else if ((new_node -> value > temp -> value) && (temp ->
right == NULL))
{
temp -> right = new_node;
cout << "Value Inserted to the right!" << endl;
break;
}
else
{
temp = temp -> right;
}
}
}
}

Data Structures and Algorithms (CSC211) Lab Manual

Deletion Operation

There are three cases for deleting a node from a binary search tree.

Case I

In the first case, the node to be deleted is the leaf node. In such a case, simply delete the node
from the tree.

Case II

In the second case, the node to be deleted lies has a single child node. In such a case follow the
steps below:

1. Replace that node with its child node.

2. Remove the child node from its original position.

Case III

In the third case, the node to be deleted has two children. In such a case follow the steps below:

• Get the inorder successor of that node.

• Replace the node with the inorder successor.
• Remove the inorder successor from its original position.

Node Deletion

Code:
void insertNode(TreeNode * new_node)
{
if (root == NULL)
{
root = new_node;
cout << "Value Inserted as root node!" << endl;
}
else
{
TreeNode * temp = root;
while (temp != NULL) {
if (new_node -> value == temp -> value)
{
cout << "Value Already exist," <<
"Insert another value!" << endl;
return;
}
else if ((new_node -> value < temp -> value) && (temp ->
left == NULL))

Data Structures and Algorithms (CSC211) Lab Manual

 {
temp -> left = new_node;
cout << "Value Inserted to the left!" << endl;
break;
}
else if (new_node -> value < temp -> value)
{
temp = temp -> left;
}
else if ((new_node -> value > temp -> value) && (temp ->
right == NULL))
{
temp -> right = new_node;
cout << "Value Inserted to the right!" << endl;
break;
}
else
{
temp = temp -> right;
}
}
}
}

Binary Search Tree Applications

1. In multilevel indexing in the database

2. For dynamic sorting

3. For managing virtual memory areas in Unix kernel

Data Structures and Algorithms (CSC211) Lab Manual

 IN-LAB TASKS
Task# 1 Write a function to create a Binary Search Tree (BST). Write functions to enter a new
node and delete any node from the BST.

POST-LAB TASKS
Task# 1 Create a binary search tree by entering values in given order as [8, 9, 12, 6]. Your Binary
Search Tree should look like this.

Now dry run your code for inserting 8 first, then inserting 9 and after that inserting 12.

Data Structures and Algorithms (CSC211) Lab Manual

LAB#12

Graphs
Objectives:
At the end of the lab, students are expected to be able to do the following:

• Understand the concept of graph data structure in C++

• Learn to apply different operations such as graph traversal, adding vertices and edges,
finding adjacency list for graphs

Introduction:
A graph data structure is a collection of nodes that have data and are connected to other nodes.

Graphs are used to solve many real-life problems. Graphs are used to represent networks. The
networks may include paths in a city or telephone network or circuit network. Graphs are also used
in social networks like linkedIn, Facebook. On facebook, everything is a node. That includes User,
Photo, Album, Event, Group, Page, Comment, Story, Video, Link, Note, anything that has data is
a node.

Every relationship is an edge from one node to another. Whether you post a photo, join a group,
like a page, etc., a new edge is created for that relationship.

All of facebook is then a collection of these nodes and edges. This is because facebook uses a
graph data structure to store its data.

More precisely, a graph is a data structure (V, E) that consists of

• A collection of vertices V

Data Structures and Algorithms (CSC211) Lab Manual

 • A collection of edges E, represented as ordered pairs of vertices (u,v)

In the above Graph, the set of vertices V = {0,1,2,3,4} and the set of edges E = {01, 12, 23, 34,
04, 14, 13}.

Graph Terminology

• Adjacency: A vertex is said to be adjacent to another vertex if there is an edge connecting

them. Vertices 2 and 3 are not adjacent because there is no edge between them.

• Path: A sequence of edges that allows you to go from vertex A to vertex B is called a path.
0-1, 1-2 and 0-2 are paths from vertex 0 to vertex 2.

• Directed Graph: A graph in which an edge (u,v) doesn't necessarily mean that there is an
edge (v, u) as well. The edges in such a graph are represented by arrows to show the
direction of the edge.

Graph Representation

Graphs are commonly represented in two ways:

1. Adjacency Matrix

An adjacency matrix is a 2D array of V x V vertices. Each row and column represent a vertex.

If the value of any element a[i][j] is 1, it represents that there is an edge connecting vertex i and
vertex j.

The adjacency matrix for the graph created above is

Data Structures and Algorithms (CSC211) Lab Manual

Since it is an undirected graph, for edge (0,2), we also need to mark edge (2,0); making the
adjacency matrix symmetric about the diagonal.

Edge lookup (checking if an edge exists between vertex A and vertex B) is extremely fast in
adjacency matrix representation but we have to reserve space for every possible link between all
vertices (V x V), so it requires more space.

2. Adjacency List

An adjacency list represents a graph as an array of linked lists.

The index of the array represents a vertex and each element in its linked list represents the other
vertices that form an edge with the vertex.

The adjacency list for the graph made in the first example is as follows:

An adjacency list is efficient in terms of storage because we only need to store the values for the
edges. For a graph with millions of vertices, this can mean a lot of saved space.

Data Structures and Algorithms (CSC211) Lab Manual

Graph Operations

The most common graph operations are:

• Check if the element is present in the graph

• Graph Traversal

• Add elements (vertex, edges) to graph

• Finding the path from one vertex to another

Graph Implementation:

Code:
#include <iostream>
using namespace std;
// stores adjacency list items
struct adjNode {
int val, cost;
adjNode* next;
};
// structure to store edges
struct graphEdge {
int start_ver, end_ver, weight;
};
class DiaGraph{
// insert new nodes into adjacency list from given graph
adjNode* getAdjListNode(int value, int weight, adjNode* head) {
adjNode* newNode = new adjNode;
newNode->val = value;
newNode->cost = weight;

newNode->next = head; // point new node to current head

return newNode;
}
int N; // number of nodes in the graph
public:
adjNode **head; //adjacency list as array of pointers
// Constructor
DiaGraph(graphEdge edges[], int n, int N) {
// allocate new node
head = new adjNode*[N]();
this->N = N;
// initialize head pointer for all vertices
for (int i = 0; i < N; ++i)
head[i] = nullptr;
// construct directed graph by adding edges to it
for (unsigned i = 0; i < n; i++) {
int start_ver = edges[i].start_ver;
int end_ver = edges[i].end_ver;

Data Structures and Algorithms (CSC211) Lab Manual

 int weight = edges[i].weight;
// insert in the beginning
adjNode* newNode = getAdjListNode(end_ver, weight,
head[start_ver]);

// point head pointer to new node

head[start_ver] = newNode;
}
}
// Destructor
~DiaGraph() {
for (int i = 0; i < N; i++)
delete[] head[i];
delete[] head;
}
};
// print all adjacent vertices of given vertex
void display_AdjList(adjNode* ptr, int i)
{
while (ptr != nullptr) {
cout << "(" << i << ", " << ptr->val
<< ", " << ptr->cost << ") ";
ptr = ptr->next;
}
cout << endl;
}
// graph implementation
int main()
{
// graph edges array.
graphEdge edges[] = {
// (x, y, w) -> edge from x to y with weight w
{0,1,2},{0,2,4},{1,4,3},{2,3,2},{3,1,4},{4,3,3}
};
int N = 6; // Number of vertices in the graph
// calculate number of edges
int n = sizeof(edges)/sizeof(edges[0]);
// construct graph
DiaGraph diagraph(edges, n, N);
// print adjacency list representation of graph
cout<<"Graph adjacency list "<<endl<<"(start_vertex, end_vertex,
weight):"<<endl;
for (int i = 0; i < N; i++)
{
// display adjacent vertices of vertex i
display_AdjList(diagraph.head[i], i);
}
return 0;
}

Data Structures and Algorithms (CSC211) Lab Manual

Applications Of Graphs

• Graphs are used extensively in computer science to depict network graphs, or semantic
graphs or even to depict the flow of computation.

• Graphs are widely used in Compilers to depict allocation of resources to processes or to

indicate data flow analysis, etc.

• Graphs are also used for query optimization in database languages in some specialized
compilers.

• In social networking sites, graphs are main the structures to depict the network of people.

• Graphs are extensively used to build the transportation system especially the road network.
A popular example is Google maps that extensively uses graphs to indicate directions all
over the world.

Data Structures and Algorithms (CSC211) Lab Manual

 IN-LAB TASKS
Task# 1 Write a function to create a graph. Take a value from the user and write a function to
traverse the graph to find that value. Also write functions to add vertex and edge to the graph.

POST-LAB TASKS
Task# 1 Write a program for the following graph and write a function to find its adjacency matrix.

Data Structures and Algorithms (CSC211) Lab Manual