PCCST 307 DATA STRUCTURE LAB

SEMESTER S3
DATA STRUCTURES LAB
(Common to CS/CA/CM/CD/CR/AI/AM/AD/CB/CN/CC/CU/CI/CG)

Course Code
Teaching Hours/Week
(L: T:P: R)
Credits
Prerequisites (if any)
PCCSL307 CIE Marks 50
0:0:3:0 ESE Marks 50
2 Exam Hours 2 Hrs. 30 Min.
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 .

LIST OF EXPERIMENTS

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.

5. Implement backward and forward navigation of visited web pages in a web browser (i.e. back and forward buttons) using doubly linked list operations.

6. Implement addition and multiplication of polynomials using singly linked lists.

7. Create a binary tree for a given simple arithmetic expression and find the prefix / postfix 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.

10.  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 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 7or 4-litre container. Model this as a graph problem and solve.

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

12. Given an array of sorted items, implement an efficient algorithm to search for specific item in the array.

13. Implement Bubble sort, Insertion Sort, Radix sort, Quick Sort, and Merge Sort and compare the number of steps involved.

14. 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, 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.

15. Implement a spell checker using a hash table to store a dictionary of words for fast 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.

17. 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 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?.

18. Merge K sorted lists into a single sorted list using a heap. Use a min-heap to keep track of 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):

• Attendance                                                                :5
• Continuous Internal Evaluation Marks (CIE)          :25
  (Pre-Lab Work experiments, Viva and Timely
  completion of Lab Record )
• Internal Examination                                                :20
• Total                                                                         :50

End Semester Examination Marks (ESE):

• Procedure/ Preparatory /work/Design /Algorithm                                               :10
• Conduct of experiment/ Execution of work/ troubleshooting/Programming       :15
• Result with valid inference/ Quality of  Output                                                   :10
• Viva voce                                                                                                              :10
• Record                                                                                                                   :5
• Total                                                                                                                      :50

COURSE OUTCOMES (COs)

At the end of the course students should be able to:

• CO1:  Model a real world problem using suitable data structure and implement the solution.
• CO2: Compare efficiency of different data structures in terms of time and space complexity.
• CO3: Evaluate the time complexities of various searching and sorting algorithms.
• CO4: Differentiate static and dynamic data structures in terms of their advantages and application.

TEXT BOOKS

1. Title of the Book: Fundamentals of Data Structures in C.

• Name of the Author/s: Ellis Horowitz, Sartaj Sahni and Susan Anderson-Freed.
• Name of the Publisher: Universities,Press.
• Edition and Year: 2/e, 2007.

2. Title of the Book: Introduction to Algorithms.

• Name of the Author/s: Thomas H Cormen, Charles Leisesrson, Ronald L Rivest, Clifford Stein.
• Name of the Publisher: PHI.
• Edition and Year: 3/e, 2009.

REFERENCE BOOKS

1. Title of the Book: Classic Data Structures.

• Name of the Author/s: Samanta D.
• Name of the Publisher: Prentice Hall India.
• Edition and Year: 2/e, 2018.