💻 Data Structures & Algorithms Lab (DSAL) – SPPU

A structured collection of Data Structures and Algorithms Lab assignments implemented as part of the Second Year Information Technology (2024 Pattern) curriculum at SPPU.

👨‍💻 Student Information

• Name: Aditya Kulkarni
• Class: SE IT
• University: Savitribai Phule Pune University (SPPU)

---

📚 Index

🔹 Part A (C++)

• Assignment 1 – Searching & Sorting
• Assignment 2 – Stack (Infix Conversion)
• Assignment 3 – Circular Queue

---

🔹 Part B (Python)

• Assignment 4 – Binary Search Tree
• Assignment 5 – Graph (MST – Kruskal & Prim)
• Assignment 6 – Heap Sort
• Assignment 7 – Merge Sort
• Assignment 8 – Fractional Knapsack
• Assignment 9 – Naive String Matching
• Assignment 10 – AI Search Algorithm

---

📚 Tech Stack

🔹 C++ (Core Data Structures) 🔹 Python (Advanced Algorithms)

📂 Repository Structure

DSA-Assignments-SPPU/ │ ├── PART-A-CPP/ ├── PART-B-Python/

📌 Problem Statements

---

🔹 PART A (C++)

Assignment 1: Searching and Sorting

Design and implement a student database system using dynamic memory allocation that supports the following operations:

• Store student details (ID, Name, CGPA)

• Dynamically expand the database using memory reallocation

• Perform Linear Search and Binary Search based on student ID

• Implement sorting algorithms (Bubble Sort / Selection Sort / Insertion Sort) to:

  • Sort by Name (Alphabetically)
  • Sort by CGPA (Ascending/Descending)

• Analyze and compare performance of searching before and after sorting

---

Assignment 2: Stack (Linked List Implementation)

Implement a stack as an Abstract Data Type (ADT) using a singly linked list and perform:

• Conversion of Infix expression → Postfix
• Conversion of Infix expression → Prefix

---

Assignment 3: Circular Queue

Implement a circular queue using an array and perform:

• Enqueue (Insertion)
• Dequeue (Deletion)
• Display elements

Note: Handle overflow condition using fixed queue size.

---

🔹 PART B (Python)

Assignment 4: Binary Search Tree

Implement a Binary Search Tree (BST) and perform:

• Insert (with duplicate handling)
• Delete
• Search
• Tree traversals (Inorder, Preorder, Postorder)
• Calculate tree depth
• Generate mirror image
• Create a copy of the tree
• Display parent nodes with children
• Display leaf nodes
• Level-wise traversal

---

Assignment 5: Graph – Minimum Spanning Tree

Represent a graph (e.g., college campus) using adjacency list/matrix and compute the Minimum Spanning Tree using:

• Kruskal’s Algorithm
• Prim’s Algorithm

---

Assignment 6: Heap Sort

Design and implement Heap Sort to sort an array of integers in ascending order, demonstrating:

• Heap construction (Min/Max Heap)
• Efficient time and space usage

---

Assignment 7: Merge Sort (Divide and Conquer)

Sort a list of online orders based on delivery time using Merge Sort to prioritize faster deliveries.

---

Assignment 8: Fractional Knapsack (Greedy Algorithm)

Maximize profit by selecting items (even partially) within a given weight capacity using the Fractional Knapsack approach.

---

Assignment 9: Naïve String Matching

Given a text string and a pattern, implement the Naïve String Matching algorithm to find all occurrences of the pattern in the text.

---

Assignment 10: AI Search Algorithm (Maze Navigation)

Design a maze navigation system that finds the optimal path from a start point to a goal using AI search algorithms:

• Breadth First Search (BFS)
• A* Search The system should support both static and dynamic mazes and visualize the path.

👨‍💻 Author

Aditya Kulkarni Second Year IT Engineering Student

⭐ This repository showcases strong fundamentals of DSA with clean implementations.