SEMESTER S3

DATA STRUCTURES LAB

(Common to CS/CA/CM/CD/CR/AI/AM/AD/CB/CN/CC/CU/CI/CG)

Course Code PCCSL307 CIE Marks 50

Teaching Hours/Week
0:0:3:0 ESE Marks 50
(L: T:P: R)
Credits 2 Exam Hours 2 Hrs. 30 Min.

Prerequisites (if any) GYEST204 Course Type Lab

Course Objectives:

To give practical experience for learners on implementing different linear and non linear data
structures, and algorithms for searching and sorting.

Expt.
Experiments
No.
1 Find the sum of two sparse polynomials using arrays
2 Find the transpose of a sparse matrix and sum of two sparse matrices.
3 Convert infix expression to postfix (or prefix) and then evaluate using stack,

4 Implement Queue, DEQUEUE, and Circular Queue using arrays.

Implement backward and forward navigation of visited web pages in a web browser (i.e.
5
back and forward buttons) using doubly linked list operations.
6 Implement addition and multiplication of polynomials using singly linked lists.
Create a binary tree for a given simple arithmetic expression and find the prefix / postfix
7
equivalent.
8 Implement a dictionary of word-meaning pairs using binary search trees.
9 Find the shortest distance of every cell from a landmine inside a maze.
We have three containers whose sizes are 10 litres, 7 litres, and 4 litres, respectively. The
7-litre and 4-litre containers start out full of water, but the 10-litre container is initially
10 empty. We are allowed one type of operation: pouring the contents of one container into
another, stopping only when the source container is empty or the destination container is
full. We want to know if there is a sequence of pourings that leaves exactly 2 litres in the 7
 or 4-litre container. Model this as a graph problem and solve.

11 Implement the find and replace feature in a text editor.

Given an array of sorted items, implement an efficient algorithm to search for specific
12
item in the array.
Implement Bubble sort, Insertion Sort, Radix sort, Quick Sort, and Merge Sort and
13
compare the number of steps involved.
The General post office wishes to give preferential treatment to its customers. They have
identified the customer categories as Defence personnel, Differently abled, Senior citizen,

14 Ordinary. The customers are to be given preference in the decreasing order - Differently
abled, Senior citizen, Defence personnel, Normal person. Generate the possible sequence
of completion.

Implement a spell checker using a hash table to store a dictionary of words for fast

15 lookup. Implement functions to check if a word is valid and to suggest corrections for
misspelled words.

16 Simulation of a basic memory allocator and garbage collector using doubly linked list

The CSE dept is organizing a tech fest with so many exciting events. By participating

in an event, you can claim for activity points as stipulated by KTU. Each event i gives
17
you A[i] activity points where A is an array. If you are not allowed to participate in more

than k events, what’s the max number of points that you can earn?

Merge K sorted lists into a single sorted list using a heap. Use a min-heap to keep track of
18 the smallest element from each list. Repeatedly extract the smallest element and insert the
next element from the corresponding list into the heap until all lists are merged.

Course Assessment Method

(CIE: 50 marks, ESE: 50 marks)
Continuous Internal Evaluation Marks (CIE):
Preparation/Pre-Lab Work experiments,
Viva and Timely Internal
Attendance Total
completion of Lab Reports / Record Examination
(Continuous Assessment)

5 25 20 50
 Text Books
Name of the Edition
Sl. No Title of the Book Name of the Author/s
Publisher and Year
Universities
Fundamentals of Data Ellis Horowitz, Sartaj Sahni and Susan Press,
1 2/e, 2007
Structures in C Anderson-Freed,

Thomas H Cormen, Charles

Introduction to
2 Leisesrson, Ronald L Rivest, Clifford PHI 3/e, 2009
Algorithms
Stein

Reference Books
Sl. Name of the Edition
Title of the Book Name of the Author/s
No Publisher and Year
1 Classic Data Structures Samanta D. Prentice Hall India. 2/e, 2018

Aho A. V., J. E. Hopcroft

2 Data Structures and Algorithms Pearson Publication. 1/e, 2003
and J. D. Ullman

Introduction to Data Structures with Tremblay J. P., P. G.

3 Tata McGraw Hill. 2/e, 2017
Applications Sorenson

Theory and Problems of Data

4 Lipschutz S. Schaum’s Series 2/e, 2014
Structures

Video Links (NPTEL, SWAYAM…)

No. Link ID

1 https://nptel.ac.in/courses/106102064

2 https://ocw.mit.edu/courses/6-851-advanced-data-structures-spring-2012/
Continuous Assessment (25 Marks)

1. Preparation and Pre-Lab Work (7 Marks)

● Pre-Lab Assignments: Assessment of pre-lab assignments or quizzes that test understanding

of the upcoming experiment.
● Understanding of Theory: Evaluation based on students’ preparation and understanding of the
theoretical background related to the experiments.
2. Conduct of Experiments (7 Marks)

● Procedure and Execution: Adherence to correct procedures, accurate execution of

experiments, and following safety protocols.
● Skill Proficiency: Proficiency in handling equipment, accuracy in observations, and
troubleshooting skills during the experiments.
● Teamwork: Collaboration and participation in group experiments.

3. Lab Reports and Record Keeping (6 Marks)

● Quality of Reports: Clarity, completeness and accuracy of lab reports. Proper documentation
of experiments, data analysis and conclusions.
● Timely Submission: Adhering to deadlines for submitting lab reports/rough record and
maintaining a well-organized fair record.

4. Viva Voce (5 Marks)

● Oral Examination: Ability to explain the experiment, results and underlying principles
during a viva voce session.

Final Marks Averaging: The final marks for preparation, conduct of experiments, viva,
and record are the average of all the specified experiments in the syllabus.

Evaluation Pattern for End Semester Examination (50 Marks)

1. Procedure/Preliminary Work/Design/Algorithm (10 Marks)

● Procedure Understanding and Description: Clarity in explaining the procedure and

understanding each step involved.
● Preliminary Work and Planning: Thoroughness in planning and organizing
materials/equipment.
 ● Algorithm Development: Correctness and efficiency of the algorithm related to the
experiment.
● Creativity and logic in algorithm or experimental design.

2. Conduct of Experiment/Execution of Work/Programming (15 Marks)

● Setup and Execution: Proper setup and accurate execution of the experiment or programming
task.

3. Result with Valid Inference/Quality of Output (10 Marks)

● Accuracy of Results: Precision and correctness of the obtained results.

● Analysis and Interpretation: Validity of inferences drawn from the experiment or quality of
program output.

4. Viva Voce (10 Marks)

● Ability to explain the experiment, procedure results and answer related questions
● Proficiency in answering questions related to theoretical and practical aspects of the subject.

5. Record (5 Marks)

● Completeness, clarity, and accuracy of the lab record submitted