Course : Data Structures Theory & Lab (NADPC32)

• Faculty Incharge : Lifna C S
• Lab and Theory - Syllabus Link

Data Structures Lab Instructions

Evaluation Scheme

No	Rubrics	Marks	Document / Schedule
1	End Semester Exam	60 Marks
2	Internal Assessment	20 Marks
3	Continuous Assessment	20 Marks
	a. MCQ - 1	5 Marks
	b. MCQ - 2	5 Marks
	c. GATE based Tutorial - 1	10 Marks
	d. GATE based Tutorial - 2	10 Marks
	Total Marks	100 Marks

Note :

Continuous Assessment best out 2 of 3 will be considered

Module - 1 : Introduction

Introduction to Data Structures, Concept of ADT, Types of Data Structures- Linear and Nonlinear, Operations on Data Structures.

• Theory-PPT
• Useful Links :
  • Real Life Applications of Data Structures - 1,
  • Real Life Applications of Data Structures - 2
  • What is a Graph ?,
  • Example Scenario for Linked List
  • Tree Structure
  • Comparison between Array & Linked List
  • Comparison between Structure & Union
• Quiz : Module - 1 Quiz

Module - 2: Stacks & Queues

Introduction, ADT of Stack, Operations on Stack, Array Implementation of Stack, Applications of Stack-Well form-ness of Parenthesis, Infix to Postfix Conversion and Postfix Evaluation, Recursion. Introduction, ADT of Queue, Operations on Queue, Array Implementation of Queue, Types of Queue-Circular Queue, Priority Queue, Introduction of Double Ended Queue, Applications of Queue.

• Theory : Stack, Queues
• SE Project - Visualization of Data Structures
• Extras : Pointers - PPT_1, Pointers - PPT_2
• Demos : Stack Applications
• Useful study materials : Postfix to Infix conversion
• Useful Videos : Circular Queue
• Quiz : Module - 2 Quiz
  • Online Test - 1
  • Online Test - 2
  • Online Test - 3

Module - 3 : Linked List

Introduction, Representation of Linked List, Linked List v/s Array, Types of Linked List - Singly Linked List, Circular Linked List, Doubly Linked List, Operations on Singly Linked List and Doubly Linked List, Stack and Queue using Singly Linked List, Singly Linked List Application-Polynomial Representation and Addition.

• Theory
  • LinkedList & Applications - Notes
  • LinkedList - PPT
  • LinkedList - Virtual Lab
  • Stack implementation using LL
  • Queues implementation using LL
• Demos
  • Visualization for Stack & Queues : using Linked List
  • LinkedList Demonstrations in Excel Sheet
  • Linked List Demo in Jamboard
  • Adding 2 Polynomials
  • Adding + Subtracting Polynomials
  • Polynomial Addition using Linked List (PPT)
  • Implementation of Polynomial Addition
  • Multiplication of Polynomials using Linked List
  • Fibonacci Tree Recursion
• Visualization for Stack & Queues
  • Visualization of Stacks & Queues using Linked List
  • Singly Linked List
  • Circular Singly Linked List
• Videos
  • Inserting a node in the Beginning of the Linked List
  • Implementation of Linked List
  • Searching a node Singly Linked List
  • Deleting a node in a Linked List
  • Reversing a List
  • Inserting after a specific node in Doubly Linked List
• Quiz :
  • Quiz - 1
  • Quiz - 2
  • Quiz 3

Module - 4 : Trees

Introduction, Tree Terminologies, Binary Tree, Binary Tree Representation, Types of Binary Tree, Binary Tree Traversals, Binary Search Tree, Operations on Binary Search Tree, Applications of Binary Tree-Expression Tree, Huffman Encoding.

• Theory
  • Trees - PPT
  • BST - PPT
  • Tree - Text Book extract from Prof. Samantha
• Online Resources :
  • Full Vs Complete Binary Tree
  • Huffman
• Construct Tree using Traversals
  • Inorder & Preorder
  • Inorder & Postorder
  • Preorder & Postorder
• Visualization Tools :
  • Binary Search Tree Visualization
  • Huffman Tree
• Quiz :
  • Quiz 1
  • Quiz 2
  • Quiz 3

Module - 5 : Types of Tree

Search Trees-AVL Tree, Red Black Tree, B Tree, B+ Tree and n-ary tree Introduction to Heaps, Heap representation using array, heap creation and deletion, Heap operations

• Theory
  • AVL Tree - PPT
• Online Resources :
  • Difference between B Tree & B+ Tree - 1
  • B Tree Vs B+Tree
  • AVL Tree - PPT
• Visualization Tools :
  • AVL Tree - Visualization
  • B Tree Visualization
  • B+Tree Visualization
• Quiz :

Module - 6 : Sorting & Searching

Linear Search, Binary Search, Tries, Hashing, Collision resolution Technique Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort, Heap Sort, Bucket Sort

• Useful Links:
  • Comparison on Sorting Techniques - 1
  • Comparison on Sorting Techniques - 2
  • Visualization of Sorting Techniques : ComparisonSort - Prof. Galles

Online Resources

1. https://cse01-iiith.vlabs.ac.in/List%20of%20experiments.html
2. https://ds1-iiith.vlabs.ac.in/List%20of%20experiments.html
3. https://nptel.ac.in/courses/106/102/106102064/
4. https://www.coursera.org/specializations/data- structures-algorithms
5. https://www.edx.org/course/data-structures-fundamentals
6. https://cse01-iiith.vlabs.ac.in/List%20of%20experiments.html
7. https://www.gyata.ai/data-structure/articles/
8. https://www.geeksforgeeks.org/real-time-application-of-data-structures/

Text Books :

1. Aaron M Tenenbaum, Yedidyah Langsam, Moshe J Augenstein, “Data Structures Using C”, Pearson Publication.
2. Reema Thareja, “Data Structures using C”, Oxford Press.
3. Richard F. Gilberg and Behrouz A. Forouzan, “Data Structures: A Pseudocode Approach With C”, 2 Edition, CENGAGE Learning.
4. Jean Paul Tremblay, P. G. Sorenson, “Introduction to Data Structure and Its Applications”, McGraw-Hill Higher Education
5. Data Structures Using C, ISRD Group, 2 Edition, Tata McGraw-Hill.

Refernces :

1. Prof. P. S. Deshpande, Prof. O. G. Kakde, “C and Data Structures”, DreamTech press.
2. E. Balagurusamy, “Data Structure Using C”, Tata McGraw-Hill Education India.
3. Rajesh K Shukla, “Data Structures using C and C++”, Wiley-India
4. GAV PAI, “Data Structures”, Schaum’s Outlines.
5. Robert Kruse, C. L. Tondo, Bruce Leung, “Data Structures and Program Design in C”, Pearson Edition

Acknowledgemnts

• This material was prepared as a part of Course - Data Structures offered by the University of Mumbai to the Second Year Students of Artifical Intelligence & Data Science Engineering Branch during the Academic Year 2024-25