0% found this document useful (0 votes)
40 views104 pagesDsu
Uploaded by
Rajbeer Jagdev 36Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
0% found this document useful (0 votes)
40 views104 pagesDsu
Uploaded by
Rajbeer Jagdev 36Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
/ 104
COMPUTER GROUP | SEMESTER - Il|| DIPLOMA IN ENGINEERING AND TECHNOLOGY
A LABORATORY MANUAL
FOR
DATA STRUCTURE
USING °C’
(22317)
fi DS REV SaaS e R
e (Autonomous) (ISO 9001 : 2015) (ISO / IEC 27001 : 2013) ‘To ensure that the Diploma level Technical Education constantly matches the latest requirements
of technology and industry and includes the all-round personal development of students
including social concems and to become globally competitive, technology led organization.
To provide high quality technical and managerial manpower, information and consultancy
services to the industry and community to enable the industry and community to face the
changing technological and environmental challenges,
Winds
We, at MSBTE are committed to offer the best in class academic services to the students
and institutes to enhance the delight of industry and sociely. This will be achieved through
continual improvement in management practices adopted in the process of curriculum design,
development, implementation, evaluation and monitoring system along with adequate faculty
development programmes.
Ceaene easy
MSBTE believes in the followings:
‘+ Education industry produces live products.
+ Market requirements do not wait for curriculum changes.
+ Question paper is the reflector of academic standards of educational organization.
+ Well designed curriculum needs effective implementation too.
+ Competency based curriculum is the backbone of need based program.
+ Technical skills do need support of life skills.
+ Best teachers are the national assets.
+ Effective teaching learning process is impossible without learning resources. A Laboratory Manual
for
Data Structures
Using ‘C’
(22317)
Semester-III
(CO/CM/CW/IF)
Maharashtra State
Board of Technical Education, Mumbai
(Autonomous) (ISO:9001:2015) (ISO/IEC 27001:2013) Maharashtra State Board of Technical Education,
(Autonomous) (ISO:9001 : 2015 ) (ISO/IEC 27001 : 2013)
4th Floor, Government Polytechnic Building, 49, Kherwadi,
Bandra ( East }, Mumbai - 400051
(Printed on June, 2018 ) MAHARASHTRA STATE
BOARD OF TECHNICAL EDUCATION
Certificate
This is to certify that Mr. / Ms.
Roll No. wiccececeeeeeeeeees Of Third Semester of Diploma in
of Institute,
(Code: ...............) has completed the term work sat
sfactorily in course
Data Structures Using ‘C’ (22317) for the academic year 20........ to 20.0.0...
as prescribed in the curriculum.
Enrollment No:
Exam. Seat No:
Subject Teacher Head of the Department Principal
Seal of
Institution Data Structures Using °C’ (22317)
Preface
The primary focus of any engineering laboratory! field work in the technical education
system is to develop the much needed industry relevant competencies and skills. With this in
view, MSBTE embarked on this innovative ‘I’ Scheme curricula for engineering diploma
programmes with outcome-base education as the focus and accordingly, relatively large
amount of time is allotted for the practical work. This displays the great importance of
laboratory work making each teacher; instructor and student to realize that every minute of
the laboratory time need to be effectively utilized to develop these outcomes, rather than
doing other mundane activities. Therefore, for the successful implementation of this
outcome-based curriculum, every practical has been designed to serve as a ‘vehicle’ to
develop this industry identified competency in every student. The practical skills are difficult
to develop through ‘chalk and duster’ activity in the classroom situation. Accordingly, the ‘I’
scheme laboratory manual development team designed the practicals to focus on the
outcomes, rather than the traditional age old practice of conducting practicals to ‘verify the
theory’ (which may become a byproduct along the way).
This laboratory manual is designed to help all stakeholders, especially the students, teachers
and instructors to develop in the student the pre-determined outcomes. It is expected from
each student that at least a day in advance, they have to thoroughly read through the
concerned practical procedure that they will do the next day and understand the minimum
theoretical background associated with the practical. Every practical in this manual begins by
identifying the competency, industry relevant skills, course outcomes and practical outcomes
which serve as a key focal point for doing the practical. The students will then become aware
about the skills they will achieve through procedure shown there and necessary precautions to
be taken, which will help them to apply in solving real-world problems in their professional
life.
This manual also provides guidelines to teachers and instructors to effectively facilitate
student-centered lab activities through each practical exercise by arranging and managing
necessary resources in order that the students follow the procedures and precautions
systematically ensuring the achievement of outcomes in the students.
Data structure is an important aspect for Computer Engineering and Information Technology
Diploma graduates. Data structure is a logical & mathematical model of storing & organizing
data in a particular way in a computer. The methods and techniques of Data Structures are
widely used in industries. After going through these learning experience students will be able
to identify the problem, analyze different algorithms and use them to solve the problem.
Although best possible care has been taken to check for errors (if any) in this laboratory
manual, perfection may elude us as this is the first edition of this manual. Any errors and
suggestions for improvement are solicited and highly welcome
“Maharashira State Board of Technical Education 7 Data Structures Using °C’ (22317)
Programme Outcomes (POs) to be achieved through Practical of this
Course:
POL. Basic knowledge: Apply knowledge of basic mathematics, sciences and basic
engineering to solve the broad-based Computer engineering problem.
PO2. Discipline knowledge: Apply Information Technology knowledge to solve broad-
based Information Technology related problems.
POS. Experiments and practice: Plan to perform experiments, practices and to use the
results to solve Information Technology related problems.
PO4. Engineering tools: Apply appropriate Information Technology related techniques!
tools with an understanding of the limitations.
PO7. Ethies: Apply ethical principles for commitment to professional ethics, responsibilities
and norms of the practice also in the field of Computer engineering.
POS, Individual and team work: Function effectively as a leader and team member in
diverse/ multidisciplinary teams.
PO9. Communication:. Communicate effectively in oral and written form.
PO10. Life-long learning: Engage in independent and life-long learning activities in the
context of technological changes in the Computer engineering field and allied
industry.
“Maharashira State Board of Technical Education i Data Structures Using °C’ (22317)
Practical- Course Outcome matrix
Course Outcomes (COs)
Perform basic operations on arrays.
Apply different searching and sorting techniques.
Implement basic operations on stack and queue using array representation,
Implement basic operations on Linked List
Implement program to create and traverse tree to solve problems
ees
Practical Outcome €0 | Co | Co | Co | Co
a |b |e fa |e
1. | Program to perform operations on array vf-]-]-]-
2. | Search a data using linear search -|v]J-}f-]-
Search a data using binary search -|v]-}-]-
4, | Program to sort an array using bubble sort -|v]-]-]-
Program to sort an array using selection sort -|v]-]-]-
6. | Program to sort an array using insertion sort -|v]-]-]-
7. | Perform push and pop operations on stack - - Vv - -
g, | Perform insert and delete operations onlinear | [| y |. |.
queue using array
9, _| Perform insert and delete operations on ~|.tvl-f.
circular queue using array
10. | Perform operation on singly linked list -|-]-]vd]-
11, | Perform operation on circular singly linked list | - | - | - | Vv | -
12, | Perform traversing on binary search tree -|-]-]-]¥
“Maharashira State Board of Technical Education i Data Structures Using °C’ (22317)
List of Industry Relevant Skills
The following industry relevant skills of the competency ‘Implement relevant algorithms
using Data Structures’ are expected to be developed in you by undertaking the practical’s of
is laboratory manual.
1, Organize data in efficient manner
2, Use given data structure,
3. Apply sorting techniques on databases.
“Maharashira State Board of Technical Education Data Structures Using °C’ (22317)
Guidelines to Teachers
There will be two sheets of blank pages after every practical for the student to report
other matters(if any), which is not mentioned in the printed practicals.
For difficult practicals if required, teacher could provide the demonstration of the
practical emphasizing of the skills which the student should achieve.
Teachers should give opportunity to students for hands-on after the demonstration.
Assess the skill achievement of the students and COs of each unit.
‘One or two questions ought to be added in each practical for different batches. For this
teachers can maintain various practical related question bank for each course.
For effective implementation and attainment of practical outcomes, teacher ought to
ensure that in the beginning itself of each practical, students must read through the
complete write-up of that practical sheet.
During practical, ensure that each student gets chance and takes active part in taking
observations/ readings and performing practical.
Teacher ought to assess the performance of students continuously according to the
MSBTE guidelines.
Instructions for Students
For incidental writing on the day of each practical session every student should
maintain a dated log book for the whole semester, apart from this laboratory manual
which s/he has to submit for assessment to the teacher in the next practical session.
For effective implementation and attainment of practical outcomes, in the beginning
itself of each practical, students need to read through the complete write-up including
the practical related questions and assessment scheme of that practical sheet.
Student ought to refer the reference books, lab manuals, etc. Student should not
hesitate to ask any difficulties they face during the conduct of practicals.
“Maharashira State Board of Technical Education v Data Structures Using °C’ (22317)
Content Page
List of Practical’s and Progressive Assessment Sheet
Date ] Date Rem
se Practical Outcome ase | ot | otf ment sigs or | 2
Ne No | perfor | submi |yarks25)| teacher | (i,
1. | Program to perform operations on array 1
2. | Search a data using linear search 8
3, | Search a data using binary search 16
4, | Program to sort an array using bubble sort 24
5, | Program to sort an array using selection sort | 32
6. | Program to sort an array using insertion sort | 39
7, | Perform push and pop operations on stack 46
g, | Perform insert and delete operations on linear | 4
queue using array
g, | Perform insert and delete operations on a
circular queue using array
10. | Perform operation on singly linked list 1
1, | Perform operation on circular singly linked |
list
12, | Perform traversing on binary search tree 84
Total
‘© To be transferred to Proforma of CIAAN-2017.
“Maharashira State Board of Technical Education Data Structures Using °C’ (22317)
1.
im.
Iv.
VI.
Practical No. 1: Program to Perform Operations on Array
Practical Significance:
Arrays are used to implement other data structures, such as list, queues, stacks, strings,
hash, ete. By using Array student should be able to create, insert, delete and display the
contents from array.
Relevant Program Outeomes (POs)
‘+ Basic knowledge: Apply knowledge of basic mathematics, sciences and basic
engineering to solve the computer group related problems.
* Discipline knowledge: Apply Information Technology knowledge to solve broad-
based Information Technology related problems.
«Experiments and practice: Plan to perform experiments and practices to use the
results to solve the computer group related problems.
+ Engineering tools: Apply relevant Computer programming / technologies and
tools with an understanding of the limitations.
© Communication: Communicate effectively in oral and written form.
Competency and Practical skills
This practical expects to develop the following skills in the student.
Develop 'C' programs to solve computer group related problems.
1. Write algorithm and draw flow chart for Array
2. Write/Compile/Debug and Save C program for operations on array.
Relevant Course Outcome(s)
«Perform basic operations on array.
Practical Outcome (PrOs)
‘* Implement a ‘C’ program to perform following operations on Array
Creation, Insertion, Deletion, Display.
Relevant Affective domain related Outcome(s)
1. Follow safety measures.
2. Follow ethical practices.
“Maharashira State Board of Technical Education T Data Structures Using °C’ (22317)
VII. Minimum Theoretical Background
Array:
C Arrays
An array is a collection of data that holds fixed number of values of same type. For
example: if you want to store marks of 5 students, you can create an array for it.
Declaration of an array in C:
Syntax: data_type array_name [array_size];
Ex, : int mark[S];
Array elements are accessed by indices,
Suppose an array mark [5] declared as above. ‘The first element is mark [0], second
element is mark [1] and so on.
mark[0] mark{1] mark{2] mark(3] mark{4]
+ Arrays have 0 as the first index not I. In this example, mark/O)
+ Ifthe size of an array is n, then to access the last element, (nel) index is used. In
this example, mark[4]
+ Suppose the starting address of mark [0] is 2120. Then, the next address, mark [1],
will be 2122, address of mark [2] will be 2124 and so on. It's because the size of a
int is 2 bytes.
“Maharashira State Board of Technical Education Data Structures Using °C’ (22317)
VIL. Algorithm:
IX. Flowchart:
“Maharashira State Board of Technical Education Data Structures Using °C’ (22317)
X. C Program Code:
XI. Resources required
Sr. Name of fieath anti '
Ne Resource Specification Quantity Remarks
Hardware: ‘Computer (i3-i5 preferable),
1 | Computer RAM minimum 2 GB and
System onwards
Operating system | Windows 7 or Later As per batch
2 Version/LINUX version 5.0 sve
or Later Version
3 | Software Turbo C/C++ Version 3.0 or
Later Version
XII. Precautions
1, Amay should be declared and accessed properly.
2. Save the program in specific directory / folder.
3, Follow safety practices,
“Maharashira State Board of Technical Education Data Structures Using °C’ (22317)
XIIL. Resources used
'S. No] Name of Resource Specification
T_ | Computer System
with broad specifications
2 | Software
3 | Any other resource used
XIV. Results (Output of the Program)
XV. Conclusion(s)
XVI. Practical Related Questions
Note: Below given are few sample questions for reference. Teacher must design
‘more such questions so as to ensure the achievement of identified CO.
1. Consider array size as 10, There are 8 elements in the array. The value (say 100) is
to be inserted at index 9. What will be the output?
2. Consider array size as 10, There are 6 elements in the array. The value at index 7 is
to be deleted. What will happen?
(Space for answers)
“Maharashira State Board of Technical Education 3 Data Structures Using °C’ (22317)
“Maharashira State Board of Technical Education Data Structures Using °C’ (22317)
XVII. Exercise
1
Perform the given operations on the following array and show diagrammatic
presentation of each operation given below:
1 2 3 4 5 6 7 8 9 10
10 [20 730 [40 [50 |60 |70 ]80 |90
a) Delete element at index 8
b) Add element at index 4 with value 999
¢) Delete element at index 0
2. Insert Array? at index 2 of Array!
Arrayl:
0 1 2 3 4 5 6 7 8 9 WW
10 [20 30 [40 [50
(Space for answers)
“Maharashira State Board of Technical Education 7 Data Structures Using °C’ (22317)
XVI
References / Suggestions for further Reading
1. https://hvww.tutorialspoint.com/eprogramming/c_arrays.htm (as on 17/01/2018)
2. https://youtube (as on 17/01/2018)
XIX. Assessment Scheme
Performance indicators Weightage
Process related(10 Marks) 30%
1. | Debugging ability 20%
2. | Follow ethical practices, 10%
Product related (15 Marks) 0%
3. | Correctness of algorithm 15%
4. | Correctness of Program codes 25%
5, | Quality of inputfoutput messaging and output 20%
formatting
6. | Timely Submission of report 5%
7. | Answer to sample questions 5%
Total (25 Marks) 100%
List of Students /Team Members
1
Dated signature
Marks Obtained ‘of Teacher
Process | Product
Related(10) | Related(1s) | _T?**l@5)
“Maharashira State Board of Technical Education Data Structures Using °C’ (22317)
ML.
I.
Vv.
Vi.
vu.
Practical No. 2: Search a Data Using Linear Search
Practical Significance
In order to perform some operation on specific data element, the data has to be
searched in data collection, and the system requires following a searching method.
One of the most commonly used method is linear search for searching data from the
given list.
Relevant Program Outcomes (POs)
«Basic knowledge: Apply knowledge of basic mathematies, sciences and basic
engineering to solve the broad-based Computer engineering problem.
Discipline knowledge: Apply Information Technology knowledge to solve broad-
based Information Technology related problems.
«Experiments and practice: Plan to perform experiments, practices and to use the
results to solve Information Technology related problems.
‘+ Engineering tools: Apply appropriate Computer Engineering / Information
Technology related techniques/ tools with an understanding of the limitations.
© Communi : Communicate effectively in oral and written form.
Competency and Practical skills
This practical is expect to develop the following skills in you
Develop 'C' programs to solve broad-based computer group related problems.
1. Write algorithm and draw Flow Chart for Linear Search.
2. Write/Compile/Debug and Save C program for function to search using Linear
Search.
Relevant Course Outcome(s)
‘* Apply different searching and sorting techniques.
Practical Outcome (PrOs)
Implement a ‘C” program to search a particular data from the given Array using
Linear Search,
Relevant Affective domain related Outcome(s)
1. Follow safety measures
2. Follow ethical practices
Mi
imum Theoretical Background
Searching: Searching is just finding out the data item among given list. Two cases
are possible that either item is found or item not present in the list
Linear search: Linear Search is a very simple search algorithm. In this sequential
search is done by searching items one by one. Each item is checked and if a match is
found then that particular item is returned, otherwise the search is continues till end of
“Maharashira State Board of Technical Education 9 Data Structures Using °C’ (22317)
the list of items. If item which is to be searched is not present in list then the search is
called as unsuccessful search.
Start End
05 16 02 26 28 04 29
ltemneedto search
VII. Algorithm
“Maharashira State Board of Technical Education 10 Data Structures Using °C’ (22317)
1X. Flow Chart
X. ‘C’ Program Code
“Maharashira State Board of Technical Education Data Structures Using °C’ (22317)
XI. Resources required
name of Specification Quantity | Remarks
Computer (3-15 preferable),
1 Hardware: RAM minimum 2 GB
Computer System “onwards
Windows 7 or Later Asperbatch | For all
2 | Operating system | VersiowLINUX version 5.0 | S#° Experiments
or Later Version
3 | Software | Turbo C/C+t Version 3.0 oF
Later Version
XII Precautions
1. Save the program in specific directory / folder.
2. Follow safety practices
XIII Resources used
No] Name of Resource Specification
T_| Computer System
with broad
3__| Any other resource used
XIV Result (Output of the Program)
XV Conelusion(s)
XVI__ Practical Related Questions
Note: Below given are few sample questions for reference. Teacher must design
‘more such questions so as to ensure the achievement of identified CO.
“Maharashira State Board of Technical Education 2 Data Structures Using °C’ (22317)
1. Linear Search is most suitable for which kind of data list?
2. What is the output if list of item having same data item which is to be searched?
(Space for answers)
XVII Exercise
1. Consider following list to perform Linear Search.
56, 36, 89, 56, 01,00,67,59
i, Search the item 01 from above list and write the item is found or not with
procedure.
ii, Search the item 55 from above list. Write the item is found or not with
procedure.
2. State the limitations of Linear Search in terms of Time Complexity.
(Space for answers)
“Maharashira State Board of Technical Education 3 Data Structures Using °C’ (22317)
“Maharashira State Board of Technical Education 4 Data Structures Using °C’ (22317)
XVIII References / Suggestions for further Reading
1._ https://www.tutorialspoint.comv/data_structures_algorithms/linear_search_algori
thm. htm (as on 17/1/2018)
2. _https://www. youtube.com/watch?v=hi-lwIRQI-s
3. https://www.youtube.com/watch?v=iwo5WAIdDks
XIX Assessment Scheme
Performance indicators Weightage
Process related(10 Marks) 30%
1 | Debugging ability 20%
2 | Follow ethical practices. 10%
Product related (15 Marks) 70%
Correctness of algorithm 135%
4 | Correctness of Program codes 25%
5 _| Quality of input/output messaging and 20%
output formatting
6 | Timely Submission of report 5%
7 | Answer to sample questions 5%
Total (25 Marks) 100%
List of Students /Team Members
Dated signature
Marks Obtained
of
Process | Product
Related(10) | Retateacts) | _Ttl@5)
“Maharashira State Board of Technical Education Data Structures Using °C’ (22317)
I.
m1.
Iv.
VL.
vil.
Practical No. 3: Search a data using binary search
Practical Significance
In order to perform some operation on specific data element, the data has to be
searched in data collection, and the system requires following a searching method
One of the most commonly used methods is Binary search for searching data from the
given list, Binary Search is suitable of large scale of data.
Relevant Program Outeomes (POs)
* Basic knowledge: Apply knowledge of basic mathematics, sciences and basic
engineering to solve the broad-based Computer engineering problem,
* Discipline knowledge: Apply Information Technology knowledge to solve
broad- based Information Technology related problems.
+ Experiments and practice: Plan to perform experiments, practices and to use
the results to solve Information Technology related problems
+ Engineering tools: Apply appropriate Computer Engineering / Information
‘Technology related techniques’ tools with an understanding of the limitations.
* Communication: Communicate effectively in oral and written form.
Competency and Practical skills
This practical is expect to develop the following skills in student.
Develop 'C' programs to solve broad-based computer group related problems.
1. Write algorithm and draw Flow Chart for Binary Search,
2. Write/Compile/Debug and Save C program for function to search using
Binary Search.
Relevant Course Outeome(s)
«Apply different searching and sorting techniques.
Practical Outcome (POs)
Implement a ‘C’ program to search a particular data from the given Array using
Binary Search
Relevant Affective domain related Outcome(s)
1, Follow safety measures
2. Follow ethical practices.
Minimum Theoretical Background
Searching: Searching is, finding out the data item among list given. Two cases are
possible that either item is found or item not present in the list.
Binary Search: Binary Search is a useful and fast search algorithm. This searching
method uses divide and conquer principal. Binary search uses sorted list to search an
item
“Maharashira State Board of Technical Education 16 Data Structures Using °C’ (22317)
Binary Search looks for a particular item by comparing the middle most item of
the collection. If match occurs then the index of item is returned. If middle item is
greater than the item, the item is searched in the sub-array to the left of the middle
item, Otherwise, the item is searched for in the sub-array to the right array as well
until the size of the sub-array reduces to zero.
Fig 1.: Sorted array for searching an item
First determine half of the array by using this formula-
Mid=low + (high-low) /2
Here it is, 0+ (6-0)/
3. So, 3 is the Mid of the array.
low mid High
os 2 2 a» (|) « 67
Hem needto search
Fig 2.: Finding out the mid
‘Now we compare the value stored at location 3, with the value being searched, i.¢.45.
We find that the value at location 3 is 34, which is not a match. As the value is than
greater 34 and we have a sorted array, so we also know that the target value must be
in the upper portion of the array.
“Maharashira State Board of Technical Education 7 Data Structures Using °C’ (22317)
Fig 3. Upper portion of the array
We change our low to mid1 and find the new mid value again
Low=mid+1
Mi
low + (high-low) /2
Do above given procedure till the item is found if present in the list.
VIL. Algorithm
“Maharashira State Board of Technical Education Data Structures Using °C’ (22317)
1X. Flow Chart
X. — ‘C? Program Code
“Maharashira State Board of Technical Education Data Structures Using °C’ (22317)
XI. Resources required
Ne Resource Specification Quantity Remarks
Hardware: | Computer (3-15 preferable),
1 Computer RAM minimum 2 GB and
System onwards
Windows 7 or Later As per batch For all
2. | Operating system | Version/LINUX version 5.0 size Experiments
or Later Version
3 Software| Turbo C/C++ Version 3.0 oF
Later Version
XII Precautions
1. Save the program in specific directory / folder.
2. Follow safety practices.
XII Resources used
'S. No] Name of Resource Specification
1 | Computer System
with broad specifications
2 | Software
3 | Any other resource used
XIV. Result (Output of the Program)
XV Conelusion(s)
XVI_ Practical Related Questions
Note: Below given are few sample questions for reference. Teacher must design
more such questions so as to ensure the achievement of identified CO.
1.Binary Search is most suitable for what kind of data list.
2. If mid=4.5 then what should be the value of mid?
“Maharashira State Board of Technical Education 20 Data Structures Using °C’ (22317)
(Space for answers)
XVII Exercise
1. State the benefits and limitations of Binary Search in terms of Time Complexity.
2. Consider a following list and write down the steps to perform Binary Search to
search following numbers.
i, 12
ii, 67
iii, 100
“Maharashira State Board of Technical Education 2 Data Structures Using °C’ (22317)
(Space for answers)
“Maharashira State Board of Technical Education 2B Data Structures Using °C’ (22317)
XVIII References / Suggestions for further Reading
1. https://www-tutorialspoint.com/data_structures_algorithms/linear_search_alg
orithm.htm
2. https://www. youtube.com/watch?v=P3YID7iBug
3. https://www.youtube.com/watch?v-UcUyTbtFxQQ
XIX Assessment Scheme
Performance indicators Weightage
Process related(10 Marks) 30%
1 | Debugging ability 20%
2 | Follow ethical practices 10%
Product related (15 Marks) 70%
3 | Correctness of algorithm 15%
4 | Correctness of Program codes 25%
5 | Quality of inpuvoutput messaging and output 20%
formatting
6 imely Submission of report 5%
7 | Answer to sample questions 5%
tal (25 Marks) 100%
List of Students /Team Members
1
Es
Dated signature
Marks Obtained ‘of Teacher
Process Product
Related(10) | Relateacts) | T°t#!(25)
“Maharashira State Board of Technical Education Data Structures Using °C’ (22317)
.
1.
Vv.
Vi.
VIL.
Practical No. 4: Program to Sort an Array Using Bubble Sort
Practical Significance:
In order to perform some operation on specific data element, the data has to be sorted
in data collection, and the system requires following a Sorting method. One of the
most commonly used methods is Bubble Sort for sorting data from the given list.
Relevant Program Outcomes (POs)
‘© Basic knowledge: Apply knowledge of basic mathematics, sciences and basic
engineering to solve the computer group related problems.
«Discipline knowledge: Apply Information Technology knowledge to solve broad-
based Information Technology related problems.
+ Experiments and practice: Plan to perform experiments and practices to use the
results to solve the computer group related problems.
Engineering tools: Apply relevant Computer programming / technologies and
tools with an understanding of the limitations.
+ Communication: Communicate effectively in oral and written form.
Competency and Practical skills
This practical expects to develop the following skills in the student.
Develop 'C' programs to solve computer group related problems.
1. Write algorithm and draw flow chart for Bubble sort.
2. Write / Compile / Debug and execute *C” program for Bubble sort,
Relevant Course Outcome(s)
‘* Apply different searching and sorting techniques.
Practical Outcome (PrOs)
+ Implement a ‘C’ program to sort an array using Bubble Sort method.
Relevant Affective domain related Outcome(s)
1. Follow safety measures.
2. Follow ethical practices.
Minimum Theoretical Background
In Bubble Sort method the list is rearranged by exchanging the two adjacent elements
if they are not in order (order may be ascending or descending)
Bubble sort algorithm starts by comparing the first two elements of an array and
swapping if necessary, i.e., if you want to sort the elements of array in ascending
order and if the first element is greater than second then, the elements are swapped
but, ifthe first element is smaller than second, elements are not swapped. Then, again
second and third elements are compared and swapped if it is necessary and this
process continues until last and second last element are compared and swapped. This
completes the first iteration of bubble sort.
“Maharashira State Board of Technical Education ery Data Structures Using °C’ (22317)
In general it may be required to go through maximum passes as (N-1) for every pass
the number of comparisons are (N-1), (N-2), (N-3)... 1. The maximum number of
comparisons are N(N-1) / 2
Bubble Sorting
Second Pass
cress
VIII. Algorithm:
“Maharashira State Board of Technical Education 3 Data Structures Using °C’ (22317)
1X. Flowchart:
C Program Code:
“Maharashira State Board of Technical Education Data Structures Using °C’ (22317)
XI. Resources required
Windows 7 or Later
xe Ram of Specification Quantity Remarks
Hardware | Computer (3-15 preferable),
1 Computer RAM minimum 2 GB and
System onwards
As per batch Forall
2 | Operating system | Version/LINUX version 5.0 size Experiments
or Later Version
3 Software Turbo C/C+ Version 3.0 or
Later Version
XII. Precautions
1. Save the program in specific directory / folder.
2. Follow safety practices.
XIIL Resources used
S.No] Name of Resource Specification
1 | Computer System
with broad specifications
2 | Software
3 | Any other resource used
XIV. Results (Output of the Program)
XV. Conelusion(s)
“Maharashira State Board of Technical Education Data Structures Using °C’ (22317)
XVL
Practical Related Questions
Note: Below given are few sample questions for reference. Teacher must design
‘more such questions so as to ensure the achievement of identified CO.
1, What is the output of following code?
foti=O5iapip
tepals
Galil
age
,
}
(Space for answers)
“Maharashira State Board of Technical Education cy Data Structures Using °C’ (22317)
XVII. Exercise
1, Find the number of comparisons required in Bubble Sort of the following list
having 5 numbers.
0 1 2 3 4
10 [20 730 140 150
2, Sort the given array in ascending order using Bubble Sort method and show
diagrammatic representation of every iteration of for loop.
0 1 2 3 4
1000 [-20 ]300 |140 [so
3, Sort the given array in ascending order using Bubble Sort method and show
diagrammatic representation of every iteration of while loop.
0 1 2 3 4
500 | 120 [2000 ]-210 |89
“Maharashira State Board of Technical Education 7 Data Structures Using °C’ (22317)
(Space for answers)
“Maharashira State Board of Technical Education 30 Data Structures Using °C’ (22317)
XVIIL References / Suggestions for further Reading
1._ https:/Awww.w3resource.com/c-programming-exercises/searching-and-
sorting/e- search-and-sorting-exercise-3.php (as on 17/01/2018).
Ben
on 17/01/2018).
XIX. Assessment Scheme
hitps://Wwww.sitesbay.com/data-structure/e-bubble-sort (as on 17/01/2018).
hitps://vww.programiz.com/dsa/bubble-sort (as on 17/01/2018).
https://www.codingbot.net/2013/01/bubble-sort-algorithm-and-c-code. html (as
https://www.youtube.com/watch?v=y_Nuui4Qfk (as on 19/01/2018)
Performance indicators Weightage
Process related(10 Marks) 30%
7 | Debugging ability
2 | Follow ethical practices.
Product related (15 Marks) 10%
3 | Correctness of algorithm 15%
4 | Correctness of Program codes 25%
| Quality of inpuvJoutput messaging and output 25%
formatting
6 | Timely Submission of report 3%
7 | Answer to sample questions 5%
Total (25 Marks) 100%
List of Students /Team Members
1
Ps
Marks Obtained
Dated signature
of Teacher
Process | Product
Related(10) | Relateats) | T'S)
“Maharashira State Board of Technical Education Data Structures Using °C’ (22317)
I.
i.
Vv.
Vi
vu.
Practical No. 5: Program to sort an array using selection sort
Practical Significance:
In order to perform some operation on specific data element, the data has to be sorted
in data collection, and the system requires following a Sorting method. One of the
most commonly used methods is Selection Sort for sorting data from the given list.
Relevant Program Outcomes (POs)
‘© Basic knowledge: Apply knowledge of basic mathematics, sciences and basic
engineering to solve the computer group related problems.
* Discipline knowledge: Apply Information Technology knowledge to solve broad-
based Information Technology related problems.
Experiments and practice: Plan to perform experiments and practices to use the
results to solve the computer group related problems.
Engineering tools: Apply relevant Computer programming / technologies and
tools with an understanding of the limitations.
* Communication: Communicate effectively in oral and written form.
Competency and Practical skills
This practical expects to develop the following skills in the student.
Develop 'C' programs to solve computer group related problems.
1. Write algorithm and draw flow chart for selection sort.
2. Write / Compile / Debug and execute ‘C’ program for Selection sort.
Relevant Course Outcome(s)
«Apply different searching and sorting techniques.
Practical Outcome (PrOs)
* Implement a ‘C’ program to sort an array using Selection Sort method.
Relevant Affective domain related Outcome(s)
1, Follow safety measures.
2. Follow ethical practices.
Minimum Theoretical Background
Selection sort is similar to the hand picking where we take the smallest element and
put it in the first position and the second smallest at the second position and so on.
We follow the following steps to perform selection sort:
1. Start fiom the first element in the array and search for the smallest element in the
array.
2. Swap it with the value in the first position
3. Repeat the steps above for the remainder of the list (starting at the second position
and Advancing each time)
“Maharashira State Board of Technical Education 32 Data Structures Using °C’ (22317)
‘Selection Sort.
(a=sc se 7] ie)
L 3 s- 7
Sorted List.
comparisons
(0-1) esret smariest
(n-2) second smallest
(n-3) thiza emarlest
Zz
Eacimas Total comparisons = n(n - 1)/2
Exchange.
VIII. Algorithi
~o(n?)
“Maharashira State Board of Technical Education Data Structures Using °C’ (22317)
1X. Flowchart:
X. C Program Code:
“Maharashira State Board of Technical Education Data Structures Using °C’ (22317)
XI. Resources required
Sr. | Name of seal anti ;
xe | Rameot Specification Quantity Remarks
Hardware: | Computer (3-15 preferable),
1 Computer RAM minimum 2 GB and
System onwards
Windows 7 or Later As per batch For all
2 | Operating system | Version/LINUX version 5.0 size Experiments
of Later Version
7 Software) Turbo C/CH Version 3.0 or
Later Version
XII. Precautions
1. Save the program in specific directory / folder.
2. Follow safety practices
XIIL Resources used
S.No] Name of Resource Specification
1 | Computer System
with broad specifications
2 | Software
3 | Any other resource used
XIV. Results (Output of the Program)
XV. Conclusion(s)
“Maharashira State Board of Technical Education Data Structures Using °C’ (22317)
XVI Practical Related Questions
Note: Below given are few sample questions for reference. Teacher must design
more such questions as to ensure the achievement of identified CO.
Choose the right option from the following
1.A Selection Sort compares adjacent elements, and swaps them if they are in wrong,
order.
a, True b, False c, Depends on Elements d. None of these
Ans :
2. For each i from 1 to n-1, there are exchanges for Selection Sort:
a. 1 b.ml en d. None of these
Ans :
3. What is the output of selection sort after the 2nd iteration given the following
sequence of numbers: 20 12. 10 15 2
a 2 1S 12 10 20
b. 2 101 12 1s 20
cc 2 12, 10 15s 20
d. None of the above
Ans
XVII. Exercise
1. Find the number of comparisons required in Selection Sort of the following
given list having 5 numbers.
0 1 2 3 4
10 20 30 40 30
yg
‘ort the given array in ascending order using Selection Sort method and show
liagrammatic representation of every iteration of for loop.
o 1 2
1000 [-20 ]300 ]140 [50
4
3. Sort the given array in ascending order using Selection Sort method and show
diagrammatic representation of every iteration of while loop.
0 1 2 3 4
500-7120 [2000 ]-210 ]89
“Maharashira State Board of Technical Education 36 Data Structures Using °C’ (22317)
(Space for answers)
“Maharashira State Board of Technical Education 7 Data Structures Using °C’ (22317)
XVI
References / Suggestions for further Reading
1._https://www.youtube.com/watch?v=Aq2E47uU2a0 (as on 19/01/2018)
2. https://www.codesdope.com/blog/article/sorting-an-array-using-selection-
sort-in-c/ (as on 18/01/2018)
3. https://stackoverflow.com (as on 18/01/2018)
XIX. Assessment Scheme
Performance indicators Weightage
Process related(10 Marks) 30%
1 | Debugging ability 20%
2 | Follow ethical practices. 10%
Product related (15 Marks)
3 | Correctness of algorithm
4 | Correctness of Program codes
5 _ | Quality of inpuvfoutput messaging and output B%
formatting
6 | Timely Submission of report 5%
7 | Answer to sample questions 5%
Total (25 Marks) 100%
List of Students /Team Members
Dated signature
Marks Obtained ‘of Teacher
Process | Product
Related(10) | Related(1s) | _T?**l@5)
“Maharashira State Board of Technical Education Data Structures Using °C’ (22317)
.
1.
Vv.
VI.
vil.
Practical No.
Program to sort an array using insertion sort
Practical Significance:
In order to perform some operation on specific data element, the data has to be sorted
in data collection, and the system requires following a Sorting method. One of the
most commonly used methods is Insertion Sort for sorting data from the given list.
Relevant Program Outcomes (POs)
‘© Basic knowledge: Apply knowledge of basic mathematics, sciences and basic
engineering to solve the computer group related problems.
«Discipline knowledge: Apply Information Technology knowledge to solve broad-
based Information Technology related problems.
+ Experiments and practice: Plan to perform experiments and practices to use the
results to solve the computer group related problems.
* Engineering tools: Apply relevant Computer programming / technologies and
tools with an understanding of the limitations.
+ Communication: Communicate effectively in oral and written form.
Competency and Practical skills
This practical expects to develop the following skills in the student.
Develop 'C' programs to solve computer group related problems.
1. Write algorithm and draw flow chart for Insertion sort.
2. Write / Compile / Debug and execute *C’ program for Insertion sort.
Relevant Course Outcome(s)
«Apply different searching and sorting techniques.
Practical Outcome (PrOs)
* Implement a ‘C’ program to sort an array using Insertion Sort method.
Relevant Affective domain related Outcome(s)
1, Follow safety measures.
2. Follow ethical practices
imum Theoretical Background
Insertion Sort is a simplest data Sorting algorithm which sorts the array elements by
shifting elements one by one and inserting each element into its proper position
Consider we sort playing cards in our hands,
“Maharashira State Board of Technical Education 39 Data Structures Using °C’ (22317)
Insertion Sort Execution Example
15
10
15
10
15
10
15
10
10
10
10
15
VILL. Algorithm:
“Maharashira State Board of Technical Education
0 Data Structures Using °C’ (22317)
1X. Flowchart:
X. C Program Code:
“Maharashira State Board of Technical Education
a Data Structures Using °C’ (22317)
XI. Resources required
xe Ram of Specification Quantity Remarks
Hardware: ‘Computer (i3-i5 preferable),
1 Computer RAM minimum 2 GB and
System onwards
‘Operating system | Windows 7 or Later As per batch For all
2 Version/LINUX version 5.0 size Experiments:
or Later Version
5 | Sofware Turbo C/C++ Version 3.0 oF
Later Version
XII. Precautions
1. Save the program in specific directory / folder.
2. Follow safety practices.
XIII. Resources used
S.No) _ Name of Resource Specification
Computer System
with broad specifications
2 | Software
‘Any other resource used
XIV. Results (Output of the Program)
XV. Conclusion(s)
XVI. Practical Related Questions
Note: Below given are few sample questions for reference. Teacher must design
‘more such questions so as to ensure the achievement of identified CO.
1. Define insertion sort?
“Maharashira State Board of Technical Education ry Data Structures Using °C’ (22317)
2. Differentiate between bubble sort & insertion sort?
Choose the right option from the following:
3. Insertion sort is 1 in-place 2.out-place 3.stable 4.non-stable
a.l and 3 b.1 and 4 c.2 and 3 d.2 and 4
Ans:
4, Sorting of playing cards is an example of
a. Bubble sort b. Insertion sort c. Selection sort d. Quick sort
Ans:
“Maharashira State Board of Technical Education w Data Structures Using °C’ (22317)
5. Total number of comparisons for insertion sort is,
anin-1)/2
be n(n+1)/2
cn
din*n
Ans:
XVII. Exercise
1 Find the number of comparisons required in Insertion Sort of the following given
list having 5 numbers.
0 1 2 3 4
10 [20 730 140 150
2.Sort the given array in ascending order using Insertion Sort method and show
diagrammatic representation of every iteration of for loop.
0 1 2 3 4
1000 [-20 7300 140 150
3.What is the output of insertion sort after the 2nd iteration given the following
sequence of numbers: 73519846
(Space for answers)
“Maharashira State Board of Technical Education 4 Data Structures Using °C’ (22317)
References / Suggestions for further Reading
1. https://www.youtube.com/watch?v=OxN2Iqb8S9s (as on 19/01/2018)
https://stackoverflow.com (as on 18/01/2018)
https://www.sitesbay.com/data-structure/c-insertion-sort (as on
18/01/2018)
4, hitps://www.geeksforgecks.org/insertion-sort
XIX. Assessment Scheme
Performance indicators
Process related(10 Marks) 30%
1 | Debugging ability 20%
2 | Follow ethical practices 10%
Product related (15 Marks) 70%
3 | Correctness of algorithm 15%
4 | Correctness of Program codes 25%
5 | Quality of inpuvJoutput messaging and output 25%
formatting
6 | Timely Submission of report 5%
7 | Answer to sample questions 5%
‘Total (25 Marks) 100%
List of Students /Team Members
Es
Dated signature
Marks Obtained
of Teacher
Process Product
Related(10) | Relatea(1s) | _T°t*l@5)
“Maharashira State Board of Technical Education Data Structures Using °C’ (22317)
u.
mm.
IV.
Vi.
vu.
Practical No. 7: Perform push and pop operations on stack
Practical Significance:
In order to perform insertion and deletion of data items from given data list based on
Last in First out (LIFO) suitable data structure is required. So Stack is a data structure
that follows the LIFO order and performs these operations from one end.
Relevant Program Outcomes (POs)
‘© Basic knowledge: Apply knowledge of basic mathematics, sciences and basic
engincering to solve the computer group related problems.
* Discipline knowledge: Apply Information Technology knowledge to solve broad-
based Information Technology related problems.
«Experiments and practice: Plan to perform experiments and practices to use the
results to solve the computer group related problems.
«Engineering tools: Apply relevant Computer programming / technologies and
tools with an understanding of the limitations.
+ Communication: Communicate effectively in oral and written form.
Competency and Practical skills
This practical expects to develop the following skills in the student.
Develop 'C’ programs to sol
1. Write algorithm and draw flow chart of stack for push and pop operations.
2. Compile/Debug/Save the ‘C’ program.
computer group related problems.
Relevant Course Outcome(s)
‘© Implement basic operations on stack and queue using array representation.
Practical Outcome (POs)
+ Write “C’ program to perform PUSH and POP operations on stack array.
Relevant Affective domain related Outcome(s)
1. Follow ethical practices.
imum Theoretical Background
A stack is a container of data items that are inserted and removed according to the
last-in first-out (LIFO) principle. A stack has a restriction that insertion and deletion
of element can only be done from only one end of stack and we call that position
as top. The element at top position is called top of the stack. Insertion of element is,
called PUSH and deletion is called POP.
“Maharashira State Board of Technical Education 6 Data Structures Using °C’ (22317)
E >, Push Operation
° top —-| 3
« °
|
Stack “Stack
Overflow Condition: Happens when there is no more space left to store a data
item that is pushed.
Underflow Condition: Happens when the stack is empty and the user executed a
POP operation.
Push(2)i1
pop()
top 89
78
9
top
Stack Overflow Stack Underflow
“Maharashira State Board of Technical Education a Data Structures Using °C’ (22317)
VIL. Algorithm
IX. Flowchart
“Maharashira State Board of Technical Education
we Data Structures Using °C” (2231
X. _ C Program Code
XI. Resources required
7)
2 | Operating system
Version/LINUX version 5.0
or Later Version
3 Software
Turbo C/C++ Version 3.0, or
later , gee compiler
size
Ne. Resource Specification Quantity Remarks
Hardware: ‘Computer (i3-i5 preferable),
1 Computer RAM minimum 2 GB and
System ‘onwards
Windows 7 or Later As per batch Forall
Experiments
“Maharashira State Board of Technical Education
rr) Data Structures Using °C’ (22317)
XIL Precautions
1. Give proper max-size for stack
2. Programs should be saved in desired folders.
XII. Resources used
'S. No] Name of Resource Specification
T_ | Computer System
with broad specifications
2 | Software
3 | Any other resource used
XIV. Result (Output of the Program)
XV. Conelusion(s)
XVI. Practical Related Questions
Note: Below given are few sample questions for reference. Teacher must design
‘more such questions so as to ensure the achievement of identified CO.
(Note: Programming exercise use blank pages provided or attach more pages if
needed.)
1) Draw stack after POP operation using given below diagram.
pop() Ans:
“Maharashira State Board of Technical Education 30 Data Structures Using °C’ (22317)
2) Draw stack after PUSH operation using given stack
PUSH(S) Ans
3) Write a TOP value after PUSH operation,
PUSH(S) Ans
XVII. Exercise
(Note: Programming exercise use blank pages provided or attach more pages if
needed.)
1) Perform following operation on stack of size 5
PUSH(30)
PUSH(12)
PUSH(10)
POPO
PUSH(45)
POP(70)
2) Implement a “C” program to stack size-8 for push(10), push(20), pop, push(10),
push(20), pop. pop, pop, push(20), pop and draw final output
3) Perform following operation on stack of size 5.
PUSH(100)
PUSH(120)
PUSH(50)
POPO
POPO)
POP(70)
“Maharashira State Board of Technical Education 3 Data Structures Using °C’ (22317)
(Space for answers)
“Maharashira State Board of Technical Education 2 Data Structures Using °C’ (22317)
XVIIL References / Suggestions for further Reading
1. www.geeksforgeeks.org/implement-two-stacks-in-an-array
(as on 18/01/2018)
2. www programmingunit.comy/2013/01/14/stack-using-array-e-program
(as on 18/01/2018)
XIX. Assessment Scheme
Performance indicators Weightage
Process related(10 Marks) 30%
7 | Debugging ability 20%
2 | Follow ethical practices, 10%
Product related (15 Marks) 70%
Correctness of algorithm 15%
4 | Correctness of Flow chart 15%
5 | Correctness of Program codes 20%
¢ _ | Quality of input/output messaging and output 5%
formatting
7 | Timely Submission of report 5%
8 | Answer to sample questions 0%
Total (25 Marks) 100%
List of Students /Team Members
1
2,
3
Marks Obtained
Dated signature
of Teacher
Process | Product
Related(10) | Related(15)
Total(2s)
“Maharashira State Board of Technical Education Data Structures Using °C’ (22317)
I.
mm.
Vv.
Vi.
vu.
Practical No. 8: Perform insert and delete operations on
linear queue using array
Practical Significance:
In order to perform INSERT and DELETE operations from two ends on given list
based on First in First out (FIFO) order. Linear Queue is collection of elements that
follows the FIFO order which keep track of two indices, front and rear one for Insert
and another for Delete.
Relevant Program Outcomes (POs)
* Basic knowledge: Apply knowledge of basic mathematics, sciences and basic
engineering to solve the computer group related problems.
+ Discipline knowledge: Apply Information Technology knowledge to solve broad-
based Information Technology related problems.
* Experiments and practice: Plan to perform experiments and practices to use the
results to solve the computer group related problems.
« Engineering tools: Apply relevant Computer programming / technologies and
tools with an understanding of the limitations.
© Communication: Communicate effectively in oral and written form.
Competency and Practical skills
This practical expects to develop the following skills in the student.
Develop 'C' programs to solve computer group related problems.
1. Write algorithm and draw flow chart of linear queue for Insert and Delete
operations
2. Compile/Debug/ save the ‘C’ program.
Relevant Course Outeome(s)
‘+ Implement basic operations on stack and queue using array representation.
Practical Outcome (PrOs)
+ Write ‘C’ program to perform INSERT and DELETE operations on linear queue
using Array Part-I and IL
Relevant Affective domain related Outcome(s)
1, Follow ethical practices.
Mi
jum Theoretical Background
‘A queue is a linear list of elements in which deletion of an element can take place
only at one end called the front and insertion can take place on the other end which is
termed as rear. The term front and rear are used frequently while describing queues in
a linked list. In a queue the first item inserted is the first to be removed (First-In-First-
“Maharashira State Board of Technical Education 34 Data Structures Using °C’ 22317)
ut, FIFO), A queue has two pointers front and rear, pointing to the front and rear
elements of the queue, respectively. This is a linear list DATA STRUCTURE used to
represent a linear list and permits deletion to be performed at one end of the list and
the insertion at the other end.
Data Element First In -
Back (Rear)
rn es
Enquese
rst Out
Front
Data Element
Data Element
STEP BY STEP PROCESS IN LINEAR QUEUE:
FRONT REAR FRONT REAR
ye 0123 4 \ x
° 410 123 4
Empty ueve
Av Ae FRONT REAR
\ vo
10 123 4 solraaf
Engueue fist element DeQueve
FRONT REAR me
a if 20304 40123 4%
EnQueve DeQueve last element
“Maharashira State Board of Technical Education 5 Data Structures Using °C’ (22317)
VIL. Algorithm
IX. Flowehart
“Maharashira State Board of Technical Education Data Structures Using °C’ (22317)
X. _ C Program Code
XI. Resources requii
se Name of Specification Quantity Remarks
Hardware: | Computer (3-15 preferable),
1 RAM minimum 2 GB and
onwards
Windows 7 or Later As per batch For all
2 | Operating system | Version/LINUX version 5.0 size Experiments
or Later Version
Turbo C/C++ Version 3.0, or
later , gcc compiler
Software
“Maharashira State Board of Technical Education Data Structures Using °C’ (22317)
XI. Precautions
1. Programs should be save in desired location.
XII. Resources used
S. No. Name of Resource Specification
1 ‘Computer System
with broad specifications
2 Software
3. | Any other resource used
XIV. Result (Output of the Program)
XV. Conclusions)
XVI. Practical Related Questions
Note: Below given are few sample questions for reference. Teacher must design
‘more such questions so as to ensure the achievement of identified CO.
(Note: Programming exercise use blank pages provided or attach more pages if
needed.)
1) Write a front and rear values of linear queue.
Enqueue Dequoue
2) Sketch the front and rear in empty queue.
oo eee sow
“Maharashira State Board of Technical Education Data Structures Using °C’ (22317)
Ans:
3). Sketch the front and rear in this queue.
Oo wae 8 4 8 wl
27 a9) a7| 7
Ans:-
(Space for Answer)
v7
“Maharashira State Board of Technical Education Data Structures Using °C’ (22317)
XVIL Exercise
(Note: Programming exercise use blank pages provided or attach more pages if
needed.)
1) Implement a C program to Linear queue in array size 5 with this operations
INSERT(25), INSERT(55), INSERT(4), DELETE, DELETE, INSERT(40).
2) Implement a C program to Linear queue in array size 10 with this operations
INSERT(10), INSERT(40), DELETE, INSERT(40), INSERT(20), DELETE,
INSERT(40).
3) Write a ‘c’ program for linear queue using array from given data.
— oe
“empeyqumue enqueue Enqueve Degueve a
(Attach separate pages for answers)
“Maharashira State Board of Technical Education 0 Data Structures Using °C’ (22317)
XVIII. References / Suggestions for further Reading
1 www.uobabylon.edu iq/eprints/publication_5_3108_1456.pdftas on 18/01/2018)
2. www.w3schools.in/data-structures-tutorial/queue/ (as on 18/01/2018)
XIX. Assessment Scheme
Performance indicators Weightage
Process related(10 Marks) 30%
1 | Debugging ability 20%
2 _ | Follow ethical practices. 10%
Product related (15 Marks) 70%
3 | Correctness of algorithm 15%
4 | Correctness of Program codes 25%
5 | Quality of inpuvJoutpat messaging and output 20%
formatting
6 | Timely Submission of report 5%
7 | Answer to sample questions 5%
Total (25 Marks) 100%
List of Students /Team Members
Ben
Marks Obtained
Dated signature
of Teacher
Process
Related(10)
Product
Related(15)
‘Total(25)
“Maharashira State Board of Technical Education
or Data Structures Using °C’ (22317)
I.
Vv.
Vi.
vu.
Practical No. 9: Perform insert and delete operations on
circular queue using array
Practical Significance:
In order to perform INSERT and DELETE operations from two ends on given list
based on First in First out (FIFO) order. But in Linear queue deleted item’s location is
wasted because another data item cannot occupy that location. So to overcome this
Circular Queue can be the feasible option
Relevant Program Outcomes (POs)
+ Basic knowledge: Apply knowledge of basic mathematics, sciences and basic
engineering to solve the computer group related problems.
* Discipline knowledge: Apply Information Technology knowledge to solve broad-
based Information Technology related problems.
+ Experiments and practice: Plan to perform experiments and practices to use the
results to solve the computer group related problems.
* Engineering tools: Apply relevant Computer programming / technologies and
tools with an understanding of the limitations.
© Communication: Communicate effectively in oral and written form,
Competency and Practical skills
This practical expects to develop the following skills in the student.
Develop 'C' programs to solve computer group related problems.
1. Write algorithm and draw flow chart of circular queue for Insert and Delete
operations
2. Compile/Debug/ Save the *C’ program.
Relevant Course Outcome(s)
«Implement basic operations on stack and queue using array representation,
Practical Outcome (PrOs)
+ Write ‘C’ program to perform INSERT and DELETE operations on circular queue
using Array Part-I and II.
Relevant Affective domain related Outcomes)
1. Follow ethical practices.
2. Follow Safety practices
Minimum Theoretical Background
Circular queue is a linear data structure. It follows FIFO principle. In circular queue
the last node is connected back to the first node to make a circle, Elements are added
at the rear end and the elements are deleted at front end of the queue. Any position
before front is also after rear. It is also called ‘Ring Buffer’.
“Maharashira State Board of Technical Education 2 Data Structures Using °C’ (22317)
STEP BY STEP PROCESS:
avout) spquevel enqueue( 3 spquevels
| ad
L vif v L
of Yolf Poll
CrOrO
os
it
sequal eousve enquevet9 |
enQueue(20) enQueue( 5 )
+ Front: Get the front item from queue.
* Rear: Get the last item from queue.
* enQueue (value) This function is used to insert an element into the circular
queue. Ina circular queue, the new element is always inserted at Rear position.
* deQueue() This function is used to delete an element from the circular queue. In
a circular queue, the element is always deleted from front position.
“Maharashira State Board of Technical Education o Data Structures Using °C’ (22317)
VIL. Algorithm
“Maharashira State Board of Technical Education
oy Data Structures Using °C’ (22317)
1X. Flowchart
C Program Code
“Maharashira State Board of Technical Education Data Structures Using °C’ (22317)
XI. Resources required
No. |_Reamurce Specification Quantity | Remarks
Hardware: Computer (i3-15 preferable),
1 Computer RAM minimum 2 GB and
System onwards
Windows 7 or later As per batch For all
2 | Operating system | Version/LINUX version 5.0 size Experiments
or later Version
3 Software| Turbo C/C++ Version 3.0, or
later , gee compiler
XI. Precautions
1, Save program in dedicated folder.
XIII. Resources used
S.No] Name of Resource Specification
‘Computer System
1
with broad specifications
Software
3 | Any other resource used
XIV. Result (Output of the Program)
XV. Conelusion(s)
XVI. Practical Related Questions
Note: Below given are few sample questions for reference. Teacher must design
more such questions so as to ensure the achievement of identified CO.
(Note: Programming exercise use blank pages provided or attach more pages if
needed.)
1) Write a front and rear values of
ular queue,
“Maharashira State Board of Technical Education 66 Data Structures Using °C’ (22317)
ya ‘Ans:
4 10
6 / os
/ 20\
30
5 <2
50] 40
a 3
2) Show the front and rear in empty circular queue.
w/\ oO
1
oh
A a
oly
3) Show the circular queue using given values of array (size is 5).
15, 20, 30,10,5
Ans:
(Space for Answer)
“Maharashira State Board of Technical Education
7 Data Structures Using °C’ (22317)
XVII. Exercise
Attempt QI. and teacher shall allot Q. 2/Q.3 from the followin:
(Note: Programming exercise use blank pages provided or attach more pages if
needed.)
1) Implement a C program to circular queue in array size 5 with this operations
INSERT(25), INSERT(55), INSERT(14), DELETE, DELETE, INSERT(40).
2) Implement a C program to circular queue in array size 10 with this operations
INSERT(10), INSERT(40), DELETE, INSERT(40), INSERT(20), DELETE,
INSERT(40).
3) Write a circular queue c program using array from given data.
a a —front
ae
WW A,
a"
Y ga fa
oT
mx
é