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	DS-MT-QP-2024, DS-MT-QP-Sol-2024
3	Continuous Assessment	20 Marks
	a. MCQ	10 Marks	10th Oct 2024 MCQ with Solution
	b. Mini-Project	10 Marks	Mini Project Report Format
	c. Programming Test on HackerRank	10 Marks	19th Sept 2024
	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
  • RBT_Deletion
  • Red Black Tree - IIIT Hyderabad
  • Red-Block Tree
  • B Tree
  • B+ Tree
  • Heap Data Structure
• 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
  • Red Block tree Visualization 1
  • Red Black Tree Visualization 2
• Quiz :
  • Quiz - B Tree
  • Quiz - B+Trees
  • Quiz - AVL Trees
  • Quiz - Red Black Trees
  • Quiz - Heaps

Module - 6 : Sorting & Searching

• Linear Search, Binary Search, Tries, Hashing, Collision resolution Techniques,
• Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort, Heap Sort, Bucket Sort
• Theory :
  • Searching PPT
  • Hashing PPT
  • Collision Resolution Techniques
  • Demonstrations on Hashing
  • Tries
• Online Materials:
  • Hashing Visualization from ACM
  • Open Hashing
  • Closed Hashing
  • 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
  • Bucket Sort
  • Heap Sort
  • quick sort
• Quiz :
  • Quiz - 1
  • Quiz - 2
  • Quiz - 3
  • Quiz - Sorting
  • Quiz - Searching
  • Quiz - Tries

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