Savitribai Phule Pune University
Second Year of Computer Engineering - 2024 Pattern
PCC-204-COM : Data Structures Laboratory
,
Teaching Scheme Credits Examination Scheme
Practical : 04 Hours/Week Term Work : 50 Marks
02
Practical : 25 Marks
Prerequisite Courses : Basics of python programming and Principles of Problem Solving
Companion Course : Data Structures
Course Objectives: The course aims to:
1. Provide hands-on experience with basic and advanced data structures.
2. Understand various data searching and sorting methods with pros and cons.
3. Apply Data Structures for real-world problem solving.
Course Outcomes: Upon successful completion of this course, students will be able to:
• CO1: Analyze basic searching and sorting algorithms to solve problems and evaluate their
efficiency in different scenarios.
• CO2: Make use of stacks and queue concepts to solve the given problem
• CO3: Demonstrate various types of linked lists.
• CO4: Demonstrate basic operations on trees and graphs and determine minimum spanning.
• CO5: Apply a suitable data structure for solving application-based problems.
! #
" Course Contents $
Guidelines for Instructor’s Manual
The instructor’s manual/Lab Manual is to be developed as a hands-on resource and reference.
The instructor’s manual need to include prologue (about University/program/ institute/ depart-
ment/foreword/ preface), curriculum of course, conduction and Assessment guidelines, topics un-
der consideration-concept, objectives, outcomes, set of typical applications/assignments/guidelines,
references.
Guidelines for Student’s Laboratory Journal
The laboratory assignments are to be submitted by student in the form of journal. Journal con-
sists of prologue, Certificate, table of contents, and handwritten write-up of each assignment (Title,
Objectives, Problem Statement, Outcomes, software and Hardware requirements, Date of Comple-
tion, Assessment grade/marks and assessor’s sign, Theory Concept in brief, algorithm, flowchart, test
cases, Test Data Set(if applicable), mathematical model (if applicable), conclusion/analysis. Program
codes with sample output of all performed assignments are to be submitted as softcopy.
As a conscious effort and little contribution towards Green IT and environment awareness, attaching
printed papers as part of write-ups and program listing to journal may be avoided. Students programs
maintained on cloud or college server by Laboratory In-charge is highly encouraged. For reference
one or two journals may be maintained with program prints at Laboratory for accreditation purpose.
Guidelines for Laboratory/Term Work Assessment
Continuous assessment of laboratory work should be done based on overall performance and Labora-
tory assignments performance of student. Each Laboratory assignment assessment should be assigned
22
grade/marks based on parameters with appropriate weightage. Suggested parameters for overall as-
sessment as well as each Laboratory assignment assessment include timely completion performance,
innovation, efficient codes, punctuality and neatness.
Guidelines for Laboratory Conduction
The instructor is expected to conduct TWO assignments from each group (A,B,C,D,E). The instruc-
tor may set multiple sets of assignments and distribute them among batches of students.
Encourage students for appropriate use of Hungarian notation, proper indentation and comments.
Use of open source software is to be encouraged. In addition to these, instructors may assign one real
life application in the form of a mini-project based on the concepts learned.
Suggested Language: Python/C++/C or any open source
Guidelines for Practical Examination
Both internal and external examiners should jointly set problem statements. During practical assess-
ment, the expert evaluator should give the maximum weightage to the satisfactory implementation
of the problem statement. The supplementary and relevant questions may be asked at the time of
evaluation to test the student’s for advanced learning, understanding of the fundamentals, effective
and efficient implementation. So encouraging efforts, transparent evaluation and fair approach of
the evaluator will not create any uncertainty or doubt in the minds of the students. So adhering to
these principles will consummate our team efforts to the promising start of the student’s academics.
Guidelines for Oral Examination
Oral examination gauge students’ knowledge and skills based on the spoken word, typically guided
by questions or small tasks. A pair of examiners must design appropriate questions for each learning
outcome. They should focus on depth rather than breadth. They should include potential follow-
up questions and prompts based on different types of answers. Examiners should standardize the
number of questions, difficulty of questions, and the time allotted. Questions should be based on the
practical assignments performed in the term work and not on the entire syllabus.
Suggested List of Laboratory Experiments/Assignments
Sr. Group A: Arrays and Searching Sorting Algorithms
1 Write a Python program to manage the borrowing records of books in a library. Implement
the following functionalities:
• Compute the average number of books borrowed by all library members.
• Find the book with the highest and lowest number of borrowings in the library.
• Count the number of members who have not borrowed any books (denoted by a
borrow count of 0).
• Display the most frequently borrowed book (i.e., the mode of borrow counts).
After performing, determine the time and Space complexity of each operation
2 In an e-commerce system, customer account IDs are stored in a list, and you are tasked with
writing a program that implements the following:
• Linear Search: Check if a particular customer account ID exists in the list.
• Binary Search: Implement Binary search to find if a customer account ID exists,
improving the search efficiency over the basic linear
23
3 In a company, employee salaries are stored in a list as floating-point numbers. Write a
Python program that sorts the employee salaries in ascending order using the following two
algorithms:
• Selection Sort: Sort the salaries using the selection sort algorithm.
• Bubble Sort: Sort the salaries using the bubble sort algorithm.
After sorting the salaries, the program should display top five highest salaries in the company
Group B Stacks Queues and Linked List
1 Implementing a real-time undo/redo system for a text editing application using a Stack data
structure. The system should support the following operations:
• Make a Change: A new change to the document is made.
• Undo Action: Revert the most recent change and store it for potential redo.
• Redo Action: Reapply the most recently undone action.
• Display Document State: Show the current state of the document after undoing or
redoing an action
2 Implement a real-time event processing system using a Queue data structure. The system
should support the following features:
• Add an Event: When a new event occurs, it should be added to the event queue.
• Process the Next Event: The system should process and remove the event that has
been in the queue the longest.
• Display Pending Events: Show all the events currently waiting to be processed.
• Cancel an Event: An event can be canceled if it has not been processed.
3 A call center receives incoming calls, and each call is assigned a unique customer ID. The
calls are answered in the order they are received. Your task is to simulate the call queue of a
call center using a queue data structure.
• addCall(customerID, callTime): Add a call to the queue with the customer ID and the
call time (in minutes).
• answerCall(): Answer and remove the first call from the queue.
• viewQueue(): View all calls currently in the queue without removing them.
• isQueueEmpty(): Check if the queue is empty.
4 Create a Student Record Management System using linked list
• Use a singly/doubly linked list to store student data (Roll No, Name, Marks).
• Perform operations: Add, Delete, Update, Search, and Sort.
• Display records in ascending/descending order based on marks or roll number.
Group C - Hashing
24
1 Implement a hash table of size 10 and use the division method as a hash function. In case of
a collision, use chaining. Implement the following operations:
• Insert(key): Insert key-value pairs into the hash table.
• Search(key): Search for the value associated with a given key.
• Delete(key): Delete a key-value pair from the hash table
2 Design and implement a hash table of fixed size. Use the division method for the hash
function and resolve collisions using linear probing. Allow the user to perform the following
operations:
• Insert a key
• Search for a key
• Delete a key
• Display the table
3 Implement a hash table with extendible hashing. The hash table should dynamically expand
when the number of keys in a bucket exceeds a certain threshold.
Perform the following operations:
• Insert(key): Insert key-value pairs into the hash table
• Search(key): Search for the value associated with a given key
• Delete(key): Delete a key-value pair from the hash table
Group D: Graphs and Trees
1 Consider a particular area in your city. Note the popular locations A, B, C . . . in that area.
Assume these locations represent nodes of a graph. If there is a route between two locations,
it is represented as connections between nodes. Find out the sequence in which you will
visit these locations, starting from (say A) using (i) BFS and (ii) DFS. Represent a given
graph using an adjacency matrix to perform DFS and an adjacency list to perform BFS.
2 A pizza shop receives multiple orders from several locations. Assume that one pizza boy is
tasked with delivering pizzas in nearby locations, which is represented using a graph. The
time required to reach from one location to another represents node connections. Solve the
problem of delivering a pizza to all customers in the minimum time. Use appropriate data
structures.
3 Implement various operations on a Binary Search Tree, such as insertion, deletion, display,
and search.
4 Construct an expression tree from the given prefix expression, e.g., +--a*bc/def, traverse it
using post-order traversal (non-recursive), and then delete the entire tree.
5 A list stores city names and their populations. Use a Binary Search Tree for implementation.
Provide a facility for adding new cities, deleting a city, and updating population values.
Provide a facility to display all the city names in ascending/descending order. Also, find how
many maximum comparisons are required to search for a particular city.
6 Read the formulas in propositional calculus. Write a function that reads such a formula and
creates its binary tree representation. What is the complexity of your function?
Group E : Mini project
25
Implement any application based mini project. Sample mini projects can
be selected from the list given here [not limited to]
• Implementation of Snake and Ladder [BFS]
• Implementation of Maze generation [DFS]
• Implementation of Flight Reservation System [Searching and Sorting]
• Implementation of Student Database Management system [Hashing]
• Implementation of Job Scheduling [Graphs]
• Implementation of Palindrome checker [Stacks and Queues]
• Implementation of Queue using Two Stacks
• Implementation of Keyword Frequency Counter [Hash Table]
• Implementation of a basic version of a web browser’s back button functionality [Stack]
Learning Resources
! #
"Text Books $
1. Data structures and algorithms in python by Michael T. Goodrich, ISBN-13: 978- 1118290279,
ISBN-10: 1118290275, Publisher: Wiley; 1st edition (March 18, 2013).
2. Problem Solving with Algorithms and Data Structures Using Python by Bradley N Miller and
David L. Ranum. ISBN-13: 978-1590282571, ISBN-10: 1590282574, Publisher: Franklin,
Beedle & Associates; 2nd edition (August 22, 2011).
! #
"Reference Books $
1. Hands-On Data Structures and Algorithms with Python: Write complex and powerful code using
the latest features of Python 3.7, 2nd Edition by Dr. Basant Agarwal, Benjamin Baka. ISBN:
9781788991933, 2018.
2. Core Python Programming -R. Nageswara Rao, ISBN-10: 9789351199427, ISBN-13: 978-
9351199427, Willy; 1st edition (January 1, 2016).
MOOC/NPTEL/SWAYAM Course Links:
1. NPTEL :- Programming, Data Structures and Algorithms using Python By Prof. Madhavan
Mukund, Chennai Mathematical Institute, https://archive.nptel.ac.in/courses/106/106/106106145/
YouTube/Video Links:
1. https://www.youtube.com/playlist?list=PLeo1K3hjS3uu_n_a__MI_KktGTLYopZ12
26
