Data Structures Lab PCCSL 307 KTU BTech 2024 Scheme - Experiments and Reference

 

Expt. No.	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 doublyl inked 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 land mine 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 2litres 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.
12	Given an array of sorted items,implement an efficient algorithm to search for specific item in the array.
13	Implement Bubblesort,Insertion Sort,Radixsort,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.

Text Books
Sl.No	Title of the Book	Name of the Author/s	Nameofthe Publisher	Edition andYear
1	Fundamentals of Data Structures in C	Ellis Horowitz,Sartaj Sahni and Susan Anderson-Freed,	Universities Press,	2/e,2007
2	Introduction to Algorithms	Thomas H Cormen, Charles Leisesrson,Ronald L Rivest,Clifford Stein	PHI	3/e,2009

Reference Books
Sl. No	Title of the Book	Name of the Author/s	Name of the Publisher	Edition and Year
1	Classic Data Structures	Samanta D.	Prentice Hall India.	2/e,2018
2	Data Structures and Algorithms	AhoA.V.,J.E.Hopcroft and J. D. Ullman	Pearson Publication.	1/e,2003
3	Introduction to DataStructures with Applications	TremblayJ.P.,P.G. Sorenson	Tata McGrawHill.	2/e,2017
4	Theory and Problems of Data Structures	LipschutzS.	Schaum’s Series	2/e,2014