Jaipur National University

Paper Code BTEICDS102T25

Paper Title Introduction to Computer Science and Artificial Intelligence
Unit-I Introduction to Computers: Digital and Analog Computers; Characteristics of computer; Evaluation
of Computers; Generations of Computer; Classification of Computer, Input and Output devices.
Evaluation of the components of a Programming System, Evolution of Operating Systems, Machine
Structure, Machine Language and Assembly Language.
Unit-II Computer Memory: Introduction, Memory Representation, Memory Hierarchy, CPU Registers,
Impact of Cache Memory on System Performance, Programming Language and Program
Development. Computer Software: Introduction, Types of Software, System Software, Application
Software, Operating System (Introduction, Objectives of Operating System, Types of OS, Function of
OS, Protection and Security, User Interface, Examples of Operating Systems.
Unit-III Data Representation: Introduction, Number System, Conversion from Decimal to Binary, Octal,
Hexadecimal, Conversion of Binary Octal, Hexadecimal to Decimal, Conversion of Binary to Octal,
Hexadecimal, Conversion of Octal, Hexadecimal to Binary, Boolean Logic, Logic Gates.
Unit-IV Assemblers: Design of Assembler, Table Processing: Searching and Sorting, Macro Language and the
Macro Processor: Macro Instructions, Features of Macro facility, Implementation. Linkers and
Loaders: Concept of Linking, case study of Linker inx86 machines, various loading schemes, Design
of an absolute loader, Design of a direct-linking Loader Compilers: Statement of Problem, Phases of
the compiler Debuggers: Introduction to various debugging techniques, case study:- Debugging in
Turbo C++ IDE.
Unit-V Introduction to AI: What is AI, Foundation of AI and its history, Agents and Environment, AI Tools
for Daily work:- Grammarly : AI-Powered grammar and spell –check tool for improving writing,
Google Assistant: Virtual assistant for voice- controlled tasks, Microsoft Power BI: AI-driven data
visualization and business analytics tool, Canvas: AI-based graphic design tool for creating
presentations, Social media posts, etc., Trello: AI-Powered task management and productivity tool,
Zapier: AI automation tool to connect apps and automate workflows.
Course Upon Successful Completion of the Course, Students would be able to Learn:
Outcome
CO1 Basics of Computer
CO2 Data Representation
CO3 Assembles, Linkers, Loaders and Debugging in Turbo C++ IDE
CO4 Solving Simple Problems Using Python Programs
CO5 Using Python ADTs and functions to solve more complex problems
CO6 Tools of Artificial Intelligence
Reference 1. “Systems Programming” Donovan John J., Publisher New York, Tata Mc-Graw Hill.
Books 2. “Introduction to System Software”, Author Dhamdhere, D.M., Publisher Tata Mc-Graw Hill.
3. “Principles of Compiler Design” Author Aho A.V. and J.D. Ullman Publisher Addison Wesley/
Narosa.
4. “System Software ” An Introduction to System Programming” Author L.L. Beck Publisher
Addition Wesley.
5. “Computer System: A programmer’s Perspective” Author Randal Bryant, David O’ Hallaron
Publisher Pearson.
6. “Computer Fundamentals and Programming in C” Author Reema Thareja Publisher Oxford
University Press.
7. “Fundamentals of Computers” Author E Balagurusamy Publisher McGraw Hill Education.
 Jaipur National University
Paper Code BTECSCO302T24 LTP: 3 0 0 Credit: 3
Paper Title Data Structure and Algorithms, through ‘C’
Unit-I Introduction: Dynamic aspects of operations on data, Characteristics of data structures,
Creation and manipulation of data structures, Operations on data structures, Types of data
structures – linear and nonlinear. Introduction to algorithm: Asymptotic notations, Analysis of
algorithms: Time and Space complexity.
Unit-II Arrays: Dynamic memory allocation, one-dimensional arrays, multidimensional arrays,
operations on arrays, storage – Row major order, Column major order. Linked lists: types of
linked lists – singly, doubly and circularly linked lists, operations on linked lists.
Unit-III Stacks: Implementation of stacks– array and linked list, operations on stacks, Applications of
Stacks, Notations – infix, prefix and postfix, Conversion and evaluation of arithmetic
expressions using Stacks.
Queues: Implementation of queues– array and linked list, operations on queues, Types of
queues –queue, double ended queue and priority queue.
Unit-IV Trees: Binary tree, Binary search tree, Threaded binary tree, Height balanced trees, Tries,
Heaps, Hash tables.
Graph traversals: Breadth First Search, Depth First Search, Shortest path: Depth first search
in directed and undirected graphs. Union-find data structure and applications. Directed acyclic
graphs; topological sort.
Unit-V Searching: Linear search, Binary search and Hashing. Algorithms and data structures for
sorting: Insertion Sort, Bubble sort, Selection Sort, Merge sort, Quick Sort, Heap sort, Radix
sort, Bucket sort. Algorithm design techniques: Divide and conquer, Greedy approach, dynamic
programming
Course Upon Successful Completion of the Course, Students would be able to Learn:
Outcome
CO1 Understand and remember algorithms and its analysis procedure.
CO2 Introduce the concept of data structures through ADT including List, Stack, Queues.
CO3 To design and implement various data structure algorithms.
CO4 To analyze various techniques for representation of the data in the real world.
CO5 To develop application using data structure algorithms.
CO6 To compute the complexity of various algorithms.
Reference 1. Schaum's Outline of Theory and Problems of Data Structures: Seymour Lipschutz;
Books McGraw Hill
2. “Fundamentals of Data Structures and Program Design in C: R. Kruse etal; Pearson
Education Asia
3. Data Structures using C & C++: A. M. Tenenbaum; Prentice-Hall
4. Mastering Algorithms with C: K Loudon; Shroff Publisher & Distributors Pvt. Ltd.
5. Data Structure and Algorithm Using C: R. S. Salaria; Khanna Book Publisher.

Data Structure and Algorithms, through ‘C’ Lab

 BTECSCO302P24 L:0 T:0 P:2 Credits: 1 Marks: 100

S. No Experiment Name
1. Simple Array and Pointer Implementation
2. Sorting: linear sort, bubble sort, insertion sort, selection sort.
3. Link list: singly link list implementation, doubly link list implementation and operation
like; insert node, delete node, update node, free list node, traversal, searching, and
printing.
4. Addition, Multiplication and Transpose of sparse matrices represented in linked list form.
5. Polynomial expression evaluation: addition, multiplication (8th degree polynomials).
6. Stack: implementation using array and link list and operations like push and pop.
7. Queue: implementation using link list and operations like; insert node, delete node,
update node, free list node, traversal, searching, and printing.
8. Implementation of circular queue using linked list
9. Implementation of dequeue using linked list.
10. Infix to postfix/prefix conversion.
11. Binary tree implementation, operation like insert, update, delete, traversal.
12. Searching and sorting revisited: Quick sort, Merge sort, Bucket sort, and searching
algorithms; linear search, binary search
13. Implementation of minimum spanning trees for a given graph using Breath first search
and Depth first search algorithms.
14. Symbol table organization (Hash Table).

Experiment No: 1-Implementation of Simple Arrays and Pointers

Objective

 To understand the concept of arrays and pointers in C.

 To implement one-dimensional and two-dimensional arrays.
 To understand and use pointer arithmetic.
 To demonstrate how arrays and pointers are related in C.

Prerequisites

 Basic knowledge of C programming.

 Understanding of variables, loops, and functions.
 Familiarity with memory addressing and pointer concepts.

Theory

Array in C

 An array is a collection of elements of the same data type stored in contiguous memory locations.

Syntax:

data_type array_name[size];

Pointer in C

 A pointer is a variable that stores the address of another variable.

Syntax:

data_type *pointer_name;

Pointer and Array Relationship

 The name of the array acts as a pointer to its first element.

array[i] is equivalent to *(array + i).

Experiment 1(a) : One-Dimensional Array using Pointers

Code:
#include <stdio.h>

int main() {
int arr[5], i;
int *ptr;

printf("Enter 5 elements:\n");
for(i = 0; i < 5; i++) {
scanf("%d", &arr[i]);
}
 ptr = arr; // or ptr = &arr[0];

printf("Elements using pointer:\n");

for(i = 0; i < 5; i++) {
printf("%d ", *(ptr + i));
}

return 0;
}
Sample Output:

Enter 5 elements:
12345
Elements using pointer:
12345

Experiment 1 (b): Two-Dimensional Array using Pointers

Code:
#include <stdio.h>

int main() {
int arr[2][2], i, j;

printf("Enter 4 elements:\n");
for(i = 0; i < 2; i++) {
for(j = 0; j < 2; j++) {
scanf("%d", &arr[i][j]);
}
}

printf("Array elements using pointer arithmetic:\n");

for(i = 0; i < 2; i++) {
for(j = 0; j < 2; j++) {
printf("%d ", *(*(arr + i) + j));
}
printf("\n");
}

return 0;
}
Sample Output:
Enter 4 elements:
1234
Array elements using pointer arithmetic:
12
34

Observations
  Arrays are stored in contiguous memory.
 Pointers can be used to access and manipulate array elements.
 Understanding the array-pointer relationship simplifies dynamic memory manipulation.

Viva Questions

1. What is the difference between an array name and a pointer?

2. How are arrays stored in memory?
3. What does *(arr + i) represent?
4. How can you dynamically allocate an array using pointers?
5. Can a pointer point to multiple arrays?
6. What is the use of malloc() and free()?
7. How does pointer arithmetic work in C?

Conclusion

In this experiment, the student has implemented arrays and accessed their elements using
pointers. The exercise demonstrated how arrays and pointers are closely related and how
pointer arithmetic can be used to simplify access to elements.

Experiment No: 2

“Sorting – Linear Sort, Bubble Sort, Insertion Sort, Selection Sort”

Objective

 To understand the basic sorting techniques.

 To implement and analyze:
o Linear Sort (also called Counting Sort or simplified version)
o Bubble Sort
o Insertion Sort
o Selection Sort

Prerequisites

 Basic knowledge of C programming.

 Understanding of arrays and functions.
 Familiarity with loops and conditional statements.

Theory

Sorting: Sorting is the process of arranging elements in a particular order (ascending or descending).

1- Linear Sort (Simple Counting Based)

 Concept: Count the occurrences of each number assuming all elements are within a
known range.
  Time Complexity: O(n + k), where k is the range of input.

2- Bubble Sort

 Concept: Repeatedly swap adjacent elements if they are in the wrong order.
 Time Complexity: O(n²)

3- Insertion Sort

 Concept: Insert elements into their correct position in a sorted sublist.

 Time Complexity: O(n²)

4- Selection Sort

 Concept: Repeatedly find the minimum and move it to the beginning.

 Time Complexity: O(n²)

Experiment Programs:

Linear Sort (Assuming small range of integers like 0–9)

#include <stdio.h>

int main() {
int arr[10], count[10] = {0}, i;

printf("Enter 10 elements (0 to 9):\n");

for(i = 0; i < 10; i++) {
scanf("%d", &arr[i]);
count[arr[i]]++;
}

printf("Sorted elements:\n");
for(i = 0; i < 10; i++) {
while(count[i] > 0) {
printf("%d ", i);
count[i]--;
}
}

return 0;
}

Bubble Sort:

#include <stdio.h>

int main() {
int arr[5], i, j, temp;

printf("Enter 5 elements:\n");
for(i = 0; i < 5; i++)
scanf("%d", &arr[i]);
 for(i = 0; i < 4; i++) {
for(j = 0; j < 4 - i; j++) {
if(arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}

printf("Sorted array:\n");
for(i = 0; i < 5; i++)
printf("%d ", arr[i]);

return 0;
}

Insertion Sort:

#include <stdio.h>

int main() {
int arr[5], i, j, key;

printf("Enter 5 elements:\n");
for(i = 0; i < 5; i++)
scanf("%d", &arr[i]);

for(i = 1; i < 5; i++) {

key = arr[i];
j = i - 1;

while(j >= 0 && arr[j] > key) {

arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}

printf("Sorted array:\n");
for(i = 0; i < 5; i++)
printf("%d ", arr[i]);

return 0;
}

Selection Sort:

#include <stdio.h>

int main() {
int arr[5], i, j, min, temp;

printf("Enter 5 elements:\n");
for(i = 0; i < 5; i++)
 scanf("%d", &arr[i]);

for(i = 0; i < 4; i++) {

min = i;
for(j = i + 1; j < 5; j++) {
if(arr[j] < arr[min])
min = j;
}

if(min != i) {
temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}

printf("Sorted array:\n");
for(i = 0; i < 5; i++)
printf("%d ", arr[i]);

return 0;
}

Sample Output

Input:

Enter 5 elements:
45 12 67 33 5

Output (Bubble/Insertion/Selection):

Sorted array:
5 12 33 45 67

Observations

 Bubble Sort makes multiple passes and is inefficient for large arrays.
 Insertion Sort is efficient for small or nearly sorted arrays.
 Selection Sort performs fewer swaps than Bubble Sort.
 Linear Sort is fastest but only applicable for small ranges.

Viva Questions

1. What is the best-case and worst-case complexity of Bubble Sort?

2. Which sorting algorithm is best suited for small data sets?
3. How does Insertion Sort differ from Bubble Sort?
4. Why is Selection Sort inefficient?
5. Can Linear Sort be used for sorting negative numbers?
 6. Which sorting algorithm is stable?
7. What is the difference between in-place and out-of-place sorting?

Conclusion

In this experiment, students implemented and compared four sorting algorithms. Understanding
these fundamental sorting techniques builds a strong base for advanced data structures and
algorithms.

Experiment No: 3

“Linked List Implementation and Operations”

Objective

 To understand and implement linked list structures in C.

 To perform operations such as:
o Insertion
o Deletion
o Update
o Traversal
o Searching
o Freeing the list
o Printing nodes

Prerequisites

 Basic understanding of structures and pointers in C.

 Knowledge of dynamic memory allocation (malloc, free).
 Familiarity with function writing and pointer manipulation.

Theory

1- Linked List

A linked list is a linear dynamic data structure, where each element (node) contains:

 Data
 Pointer to the next node (and to the previous node in doubly linked lists).

2- Types

 Singly Linked List: Each node points to the next.

 Doubly Linked List: Each node points to both next and previous nodes.

Singly Linked List Implementation

Structure:

struct Node {

int data;

struct Node* next;

};

Basic Operations

1-Insert at Beginning:

struct Node* insertBeginning(struct Node* head, int value) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

newNode->data = value;

newNode->next = head;

return newNode;

2- Delete a Node:

struct Node* deleteNode(struct Node* head, int key) {

struct Node *temp = head, *prev = NULL;

if (temp != NULL && temp->data == key) {

head = temp->next;
free(temp);
return head;
}

while (temp != NULL && temp->data != key) {

prev = temp;
temp = temp->next;
}

if (temp == NULL) return head;

prev->next = temp->next;
free(temp);
return head;
}
3- Update a Node:

void updateNode(struct Node* head, int oldVal, int newVal) {

struct Node* current = head;
while (current != NULL) {
if (current->data == oldVal) {
 current->data = newVal;
return;
}
current = current->next;
}
}
4- Traverse and Print:
void traverse(struct Node* head) {
while (head != NULL) {
printf("%d -> ", head->data);
head = head->next;
}
printf("NULL\n");
}
5- Search for a Node:
int search(struct Node* head, int key) {
while (head != NULL) {
if (head->data == key)
return 1;
head = head->next;
}
return 0;
}
6 Free Entire List:

void freeList(struct Node* head) {

struct Node* temp;
while (head != NULL) {
temp = head;
head = head->next;
free(temp);
}
}

Doubly Linked List Implementation

Structure:
struct DNode {
int data;
struct DNode* prev;
struct DNode* next;
};
1- Insert at Beginning:
struct DNode* insertBegin(struct DNode* head, int value) {
struct DNode* newNode = (struct DNode*)malloc(sizeof(struct DNode));
newNode->data = value;
newNode->prev = NULL;
newNode->next = head;

if (head != NULL)
head->prev = newNode;

return newNode;
}
2 - Delete a Node:
struct DNode* deleteNode(struct DNode* head, int key) {
struct DNode* temp = head;

while (temp != NULL && temp->data != key)

temp = temp->next;

if (temp == NULL) return head;

if (temp->prev != NULL)
temp->prev->next = temp->next;
else
head = temp->next;

if (temp->next != NULL)
temp->next->prev = temp->prev;

free(temp);
return head;
}
3 -Traverse Forward:
void traverseForward(struct DNode* head) {
while (head != NULL) {
printf("%d <-> ", head->data);
head = head->next;
}
printf("NULL\n");
}

4-Traverse Backward:

void traverseBackward(struct DNode* tail) {

while (tail != NULL) {
printf("%d <-> ", tail->data);
tail = tail->prev;
}
printf("NULL\n");
}

Sample Output:
Insert: 10 20 30
List: 30 -> 20 -> 10 -> NULL
Delete: 20
List: 30 -> 10 -> NULL
Update 10 to 99
List: 30 -> 99 -> NULL
Search 30: Found
Freeing List...

Viva Questions
 1. What is the difference between singly and doubly linked lists?
2. How is memory allocated in linked lists?
3. What are the advantages of linked lists over arrays?
4. When would you prefer a doubly linked list?
5. How do you detect a loop in a linked list?
6. What is the time complexity of search, insert, and delete in linked lists?
7. What happens if you forget to free a node?

Conclusion

In this lab, you implemented linked lists using structures and pointers in C. You performed
common operations such as insertion, deletion, searching, updating, and freeing the list, gaining
foundational knowledge essential for dynamic data structures.

Experiment No: 4

“Sparse Matrix Operations using Linked List”

Objective

 To represent a sparse matrix using a linked list.

 To implement operations:
o Addition of sparse matrices.
o Multiplication of sparse matrices.
o Transpose of a sparse matrix.

Prerequisites

 Understanding of matrix representation and operations.

 Proficiency with structures and pointers in C.
 Familiarity with dynamic memory allocation and linked list traversal.

Theory

Sparse Matrix

 A sparse matrix is a matrix in which most elements are zero.

 Efficient storage and operations can be achieved by storing only non-zero elements.

Linked List Representation

Each node represents a non-zero element and stores:

 Row index
 Column index
 Value
 Pointer to the next node
Code:
struct Node {
int row, col, value;
struct Node* next;
};

Implementation

1 Create a Sparse Matrix:

struct Node* createNode(int row, int col, int value) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->row = row;
newNode->col = col;
newNode->value = value;
newNode->next = NULL;
return newNode;
}

void insertNode(struct Node** head, int row, int col, int value) {
if (value == 0) return;
struct Node* newNode = createNode(row, col, value);
newNode->next = *head;
*head = newNode;
}
2 Displays Sparse Matrix:
void display(struct Node* head) {
printf("Row Col Value\n");
while (head != NULL) {
printf("%3d %3d %5d\n", head->row, head->col, head->value);
head = head->next;
}
}

3 Additions of Two Sparse Matrices:

struct Node* add(struct Node* a, struct Node* b) {
struct Node* result = NULL;

while (a != NULL && b != NULL) {

if (a->row == b->row && a->col == b->col) {
insertNode(&result, a->row, a->col, a->value + b->value);
a = a->next;
b = b->next;
}
else if ((a->row < b->row) || (a->row == b->row && a->col < b-
>col)) {
insertNode(&result, a->row, a->col, a->value);
a = a->next;
}
else {
insertNode(&result, b->row, b->col, b->value);
b = b->next;
}
}
 while (a != NULL) {
insertNode(&result, a->row, a->col, a->value);
a = a->next;
}

while (b != NULL) {
insertNode(&result, b->row, b->col, b->value);
b = b->next;
}

return result;
}

4 Transpose of Sparse Matrix:

struct Node* transpose(struct Node* head) {

struct Node* result = NULL;
while (head != NULL) {
insertNode(&result, head->col, head->row, head->value);
head = head->next;
}
return result;
}

5 Multiplication (Simplified version)

Note: Proper multiplication requires row-wise and column-wise access. This is a basic
illustration assuming very sparse matrices:

struct Node* multiply(struct Node* a, struct Node* b) {

struct Node* result = NULL;
struct Node *tempA = a, *tempB = NULL;

while (tempA != NULL) {

tempB = b;
while (tempB != NULL) {
if (tempA->col == tempB->row) {
insertNode(&result, tempA->row, tempB->col,
tempA->value * tempB->value); // No merge logic for
duplicate positions
}
tempB = tempB->next;
}
tempA = tempA->next;
}

return result;
}

5. Sample Output

Matrix A:

Row Col Value

 0 1 5
1 0 3
2 2 9

Matrix B:

Row Col Value

0 0 7
1 1 1
2 2 2

A + B:

Row Col Value

0 1 6
1 0 10
2 2 11

Transpose of A:

Row Col Value

1 0 5
0 1 3
2 2 9

A × B (simplified output):

Row Col Value

0 1 5
1 0 21
2 2 18

Viva Questions

1. What is a sparse matrix?

2. Why use linked list representation for sparse matrices?
3. What is the time complexity of transpose operation?
4. How do you handle duplicate row-column entries during addition or multiplication?
5. What is the memory benefit of sparse matrix linked representation?
6. How is a sparse matrix stored in array vs. linked list?
7. Can a sparse matrix have all zero values?

Conclusion

This lab focuses on efficient representation and manipulation of sparse matrices using linked
lists. Students learn to implement key operations and understand the trade-offs of linked list
representation versus array storage in terms of space and performance.
 Experiment No: 5

“Polynomial expression evaluation: addition, multiplication (8th degree polynomials)”

Objective

 To understand polynomial representation using linked lists.

 To implement:
o Polynomial addition
o Polynomial multiplication
 To handle polynomials up to the 8th degree using dynamic data structures.

Prerequisites

 Knowledge of C structures and pointers.

 Understanding of linked lists and dynamic memory allocation.
 Familiarity with polynomial math operations.

Theory

Polynomial Representation

A polynomial can be expressed as:

P(x) = a₀x⁰ + a₁x¹ + a₂x² + ... + aₙxⁿ

Each term of the polynomial has:

 Coefficient
 Exponent

Linked List Representation

Each node stores:

 Coefficient
 Exponent
 Pointer to the next node

Code:

struct PolyNode {
int coeff;
int expo;
struct PolyNode* next;
};
Polynomial Operations

1 Create and Insert Term in Descending Order

struct PolyNode* createNode(int coeff, int expo) {
struct PolyNode* newNode = (struct PolyNode*)malloc(sizeof(struct
PolyNode));
newNode->coeff = coeff;
newNode->expo = expo;
newNode->next = NULL;
return newNode;
}

void insertTerm(struct PolyNode** head, int coeff, int expo) {

struct PolyNode* newNode = createNode(coeff, expo);
if (*head == NULL || expo > (*head)->expo) {
newNode->next = *head;
*head = newNode;
} else {
struct PolyNode* temp = *head;
while (temp->next != NULL && temp->next->expo >= expo)
temp = temp->next;

if (temp->expo == expo) {
temp->coeff += coeff;
free(newNode);
} else {
newNode->next = temp->next;
temp->next = newNode;
}
}
}
2- Display Polynomial:
void displayPoly(struct PolyNode* poly) {
while (poly != NULL) {
printf("%dx^%d", poly->coeff, poly->expo);
if (poly->next != NULL)
printf(" + ");
poly = poly->next;
}
printf("\n");
}
3- Addition of Two Polynomials:
struct PolyNode* addPoly(struct PolyNode* p1, struct PolyNode* p2) {
struct PolyNode* result = NULL;

while (p1 && p2) {

if (p1->expo == p2->expo) {
insertTerm(&result, p1->coeff + p2->coeff, p1->expo);
p1 = p1->next;
p2 = p2->next;
} else if (p1->expo > p2->expo) {
insertTerm(&result, p1->coeff, p1->expo);
p1 = p1->next;
} else {
 insertTerm(&result, p2->coeff, p2->expo);
p2 = p2->next;
}
}

while (p1) {
insertTerm(&result, p1->coeff, p1->expo);
p1 = p1->next;
}
while (p2) {
insertTerm(&result, p2->coeff, p2->expo);
p2 = p2->next;
}

return result;
}

4 Multiplications of Two Polynomials:

struct PolyNode* multiplyPoly(struct PolyNode* p1, struct PolyNode*

p2) {
struct PolyNode* result = NULL;
struct PolyNode* temp1 = p1;
struct PolyNode* temp2;

while (temp1 != NULL) {

temp2 = p2;
while (temp2 != NULL) {
int coeff = temp1->coeff * temp2->coeff;
int expo = temp1->expo + temp2->expo;
insertTerm(&result, coeff, expo);
temp2 = temp2->next;
}
temp1 = temp1->next;
}

return result;
}

Sample I/O

Input Polynomial 1:
5x^8 + 4x^5 + 2x^0

Input Polynomial 2:
3x^5 + 2x^1 + 1x^0

Addition Output:
5x^8 + 7x^5 + 2x^1 + 3x^0
Multiplication Output:
15x^13 + 10x^9 + 5x^8 + 12x^6 + 8x^5 + 3x^5 + 4x^1 + 2x^0
(Combined: 15x^13 + 10x^9 + 5x^8 + 12x^6 + 11x^5 + 4x^1 + 2x^0)

Viva Questions

1. How are polynomials stored using linked lists?

2. What is the advantage of using linked list over arrays in polynomial operations?
3. How do you handle duplicate exponents in addition/multiplication?
4. What is the time complexity of polynomial multiplication using linked lists?
5. Can we perform polynomial division using linked lists? How?
6. What is the maximum number of terms in the multiplication of two 8th-degree
polynomials?
7. How would you evaluate a polynomial at a given value of x?

Conclusion

This lab helped students to understand polynomial expressions and how to represent them
efficiently using linked lists. Implementation of addition and multiplication provides insight into
data structure traversal and dynamic memory operations.

Experiment No: 6

“Stack: implementation using array and link list and operations like push and pop”

Objective

 To understand the concept of stack data structure.

 To implement stack using:
o Array
o Linked list
 To perform Push and Pop operations.

Prerequisites

 Knowledge of C programming.
 Understanding of arrays, pointers, and dynamic memory.
 Familiarity with structure and basic I/O.

Theory

1 Stack

 A Stack is a linear data structure that follows the LIFO (Last In, First Out) principle.
 Two main operations:
o Push: Insert an element into the stack.
o Pop: Remove the top element from the stack.
2 Stack Using Array

 Fixed size stack.

 Easy to implement but limited by array size.

3 Stack Using Linked List

 Dynamic size.
 Flexible; no size limitation unless memory is exhausted.

Stack Using Array

Code:
#include <stdio.h>
#define SIZE 100

int stack[SIZE];
int top = -1;

void push(int value) {

if (top == SIZE - 1) {
printf("Stack Overflow\n");
} else {
stack[++top] = value;
printf("%d pushed to stack\n", value);
}
}

void pop() {
if (top == -1) {
printf("Stack Underflow\n");
} else {
printf("%d popped from stack\n", stack[top--]);
}
}

void display() {
if (top == -1) {
printf("Stack is empty\n");
} else {
printf("Stack elements:\n");
for (int i = top; i >= 0; i--) {
printf("%d\n", stack[i]);
}
}
}

int main() {
push(10);
push(20);
pop();
display();
return 0;
}
Stack Using Linked List
1 Structure:

#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* next;
};

struct Node* top = NULL;

void push(int value) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (!newNode) {
printf("Heap Overflow\n");
return;
}
newNode->data = value;
newNode->next = top;
top = newNode;
printf("%d pushed to stack\n", value);
}

void pop() {
if (top == NULL) {
printf("Stack Underflow\n");
} else {
struct Node* temp = top;
printf("%d popped from stack\n", top->data);
top = top->next;
free(temp);
}
}

void display() {
struct Node* temp = top;
if (temp == NULL) {
printf("Stack is empty\n");
return;
}
printf("Stack elements:\n");
while (temp != NULL) {
printf("%d\n", temp->data);
temp = temp->next;
}
}

int main() {
push(50);
push(100);
pop();
display();
return 0;
}
Sample Output

Using Array:

10 pushed to stack
20 pushed to stack
20 popped from stack
Stack elements:
10
Using Linked List:

50 pushed to stack
100 pushed to stack
100 popped from stack
Stack elements:
50

Viva Questions

1. What is a stack and how does it work?

2. What is the difference between stack and queue?
3. What is the advantage of using a linked list for stack implementation?
4. What are the time complexities of push and pop operations?
5. How do you handle stack overflow and underflow?
6. What is the maximum size of a stack using array?
7. Can a stack be implemented using two queues?

Conclusion

This lab demonstrated how to implement the stack data structure using both arrays and linked
lists. Students practiced the fundamental stack operations and understood the trade-offs
between static and dynamic memory allocation.
 Experiment No: 7

“Queue: implementation using link list and operations like; insert node, delete node,
update node, free list node, traversal, searching, and printing.”

Objective: To implement queue operations using a linked list such as:

 Insert Node (Enqueue)

 Delete Node (Dequeue)
 Update Node
 Free List Node
 Traversal
 Searching
 Printing

Learning Outcomes

By the end of this lab, students will be able to:

 Understand dynamic memory allocation in linked structures.

 Implement a queue using singly linked lists.
 Perform all queue operations using pointers.
 Practice memory management (malloc/free).
 Develop modular code using user-defined functions.

Tools Required

 Language: C
 IDE: Code::Blocks / Turbo C / GCC
 OS: Windows / Linux

Queue using Linked List - Concept

A queue is a linear data structure that follows FIFO (First In First Out). In a linked list
implementation of a queue:

 Each node contains data and a pointer to the next node.

 A front pointer points to the front node of the queue.
 A rear pointer points to the last node.

Structure Definition:

#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* next;
};

struct Queue {
struct Node *front, *rear;
};

Operations and Functions

1. Initialize Queue
void initQueue(struct Queue* q) {
q->front = q->rear = NULL;
}

2. Insert Node (Enqueue):

void enqueue(struct Queue* q, int value) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;

if (q->rear == NULL) {
q->front = q->rear = newNode;
return;
}

q->rear->next = newNode;
q->rear = newNode;
}
3. Delete Node (Dequeue):

void dequeue(struct Queue* q) {

if (q->front == NULL) {
printf("Queue is empty.\n");
return;
}

struct Node* temp = q->front;

q->front = q->front->next;

if (q->front == NULL)
q->rear = NULL;

printf("Deleted: %d\n", temp->data);

free(temp);
}
4. Update Node:
void updateNode(struct Queue* q, int oldVal, int newVal) {
struct Node* temp = q->front;
 while (temp != NULL) {
if (temp->data == oldVal) {
temp->data = newVal;
printf("Updated %d to %d\n", oldVal, newVal);
return;
}
temp = temp->next;
}
printf("Value %d not found.\n", oldVal);
}
5. Traversal and Print:
void traverse(struct Queue* q) {
struct Node* temp = q->front;
if (temp == NULL) {
printf("Queue is empty.\n");
return;
}
printf("Queue Elements: ");
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
6. Search Node:
void search(struct Queue* q, int value) {
struct Node* temp = q->front;
int position = 0;
while (temp != NULL) {
if (temp->data == value) {
printf("Value %d found at position %d\n", value, position);
return;
}
temp = temp->next;
position++;
}
printf("Value %d not found in queue.\n", value);
}
7. Free List:
void freeList(struct Queue* q) {
struct Node* temp;
while (q->front != NULL) {
temp = q->front;
q->front = q->front->next;
free(temp);
}
q->rear = NULL;
printf("Queue memory freed.\n");
}
Sample main() Function:

int main() {
struct Queue q;
initQueue(&q);

enqueue(&q, 10);
enqueue(&q, 20);
enqueue(&q, 30);

traverse(&q);

dequeue(&q);

traverse(&q);

updateNode(&q, 20, 99);

traverse(&q);

search(&q, 99);
search(&q, 100);

freeList(&q);
return 0;
}

Observation Table:

Operation Input Output Remarks

Enqueue 10, 20, 30 Inserted Working
Dequeue - 10 deleted FIFO property
Update 20 → 99 Value updated Verified
Search 99 / 100 Found / Not found Correct result
Traversal - 99 -> 30 Accurate
Free List - Memory Freed No Leak

Conclusion:
This lab helps understand dynamic memory usage and the real-world application of queues using linked
lists. All basic operations like insert, delete, update, and traversal are efficiently implemented using
pointer manipulation.

Experiment No: 8
 “Implementation of circular queue using linked list.”

Objective:
To implement a circular queue using a linked list with the following operations:

 Insert (Enqueue)
 Delete (Dequeue)
 Traverse
 Search
 Update
 Free List

Learning Outcomes

After performing this lab, students will be able to:

 Understand the concept of circular queues and their advantages.

 Implement a circular queue using dynamic memory allocation and linked structures.
 Perform key queue operations using pointer-based logic.
 Apply traversal and searching techniques in circular queues.

Prerequisites

 Concepts of linked list and queue.

 Basic knowledge of pointers in C.
 Familiarity with dynamic memory functions (malloc, free).

Data Structure Definition

#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* next;
};

struct CircularQueue {
struct Node *rear;
};

In a circular queue:

 The last node (rear) points to the front node.

 Insertion happens at rear, and deletion at front (which is rear->next).
Queue Operations

1. Initialize Queue:
void initQueue(struct CircularQueue* q) {
q->rear = NULL;
}

2. Insert (Enqueue):
void enqueue(struct CircularQueue* q, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;

if (q->rear == NULL) {
newNode->next = newNode; // Circular reference
q->rear = newNode;
} else {
newNode->next = q->rear->next;
q->rear->next = newNode;
q->rear = newNode;
}
printf("%d inserted into queue.\n", value);
}

3. Delete (Dequeue):
void dequeue(struct CircularQueue* q) {
if (q->rear == NULL) {
printf("Queue is empty.\n");
return;
}

struct Node* temp = q->rear->next; // front node

if (q->rear == temp) { // Single node case

q->rear = NULL;
} else {
q->rear->next = temp->next;
}

printf("Deleted: %d\n", temp->data);

 free(temp);
}
4. Traverse:
void traverse(struct CircularQueue* q) {
if (q->rear == NULL) {
printf("Queue is empty.\n");
return;
}

struct Node* temp = q->rear->next;

printf("Queue Elements: ");
do {
printf("%d -> ", temp->data);
temp = temp->next;
} while (temp != q->rear->next);
printf("(back to front)\n");
}
5. Search:
void search(struct CircularQueue* q, int value) {
if (q->rear == NULL) {
printf("Queue is empty.\n");
return;
}

struct Node* temp = q->rear->next;

int pos = 0;
do {
if (temp->data == value) {
printf("Value %d found at position %d\n", value, pos);
return;
}
temp = temp->next;
pos++;
} while (temp != q->rear->next);
 printf("Value %d not found in queue.\n", value);
}
6. Update:
void update(struct CircularQueue* q, int oldVal, int newVal) {
if (q->rear == NULL) {
printf("Queue is empty.\n");
return;
}

struct Node* temp = q->rear->next;

do {
if (temp->data == oldVal) {
temp->data = newVal;
printf("Updated %d to %d\n", oldVal, newVal);
return;
}
temp = temp->next;
} while (temp != q->rear->next);

printf("Value %d not found.\n", oldVal);

}
7. Free the List:
void freeQueue(struct CircularQueue* q) {
if (q->rear == NULL) return;

struct Node* front = q->rear->next;

struct Node* temp;
do {
temp = front;
front = front->next;
free(temp);
} while (front != q->rear->next);

q->rear = NULL;
printf("Queue memory freed.\n");
 }
Sample main() Function:

int main() {
struct CircularQueue q;
initQueue(&q);

enqueue(&q, 10);
enqueue(&q, 20);
enqueue(&q, 30);

traverse(&q);

dequeue(&q);

traverse(&q);

update(&q, 20, 99);

traverse(&q);

search(&q, 99);
search(&q, 100);

freeQueue(&q);
return 0;
}
Observation Table:
Operation Input Output Remarks
Enqueue 10, 20, 30 Inserted Rear updated
Dequeue - 10 deleted Front moved
Traverse - 20 -> 30 Circular view
Update 20 to 99 Value updated Verified
Search 99, 100 Found / Not found Correct
Free - Memory freed No leak

Conclusion

This lab provided hands-on experience with:

 Implementing a circular queue using linked list.

 Managing pointers and circular references.
 Performing queue operations with proper memory handling.

Experiment No: 10

“Infix to Postfix and Prefix Expression Conversion.”

Objective:
To convert a given infix expression to:

 Postfix (Reverse Polish Notation)

 Prefix (Polish Notation)
using a stack-based implementation in C.

Learning Outcomes

After performing this lab, students will be able to:

 Understand expression notation formats: infix, postfix, prefix.

 Apply stack data structure for expression conversion.
 Evaluate operator precedence and associativity.
 Implement infix to postfix and prefix conversions in C.

Prerequisites

 Stack data structure

 Operator precedence
 Associativity rules
 String manipulation in C

Theory Overview
Notation Description Example (A, B, C are operands)
Infix Operators between operands A + B * C

Postfix Operators after operands A B C * +

Prefix Operators before operands + A * B C

Operator Precedence:

1. ^ (Right to Left)
2. *, /, % (Left to Right)
3. +, - (Left to Right)
Stack Implementation:

#define SIZE 100

char stack[SIZE];
int top = -1;

void push(char c) {
stack[++top] = c;
}

char pop() {
 if (top == -1) return -1;
return stack[top--];
}

char peek() {
return stack[top];
}

int isEmpty() {
return top == -1;
}
Utility Functions:
int isOperand(char c) {
return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' &&
c <= '9');
}

int precedence(char op) {

switch(op) {
case '^': return 3;
case '*':
case '/':
case '%': return 2;
case '+':
case '-': return 1;
default: return 0;
}
}

int isRightAssociative(char op) {

return op == '^';
}

Infix to Postfix Conversion

void infixToPostfix(char* infix, char* postfix) {
int i = 0, k = 0;
char c;

while ((c = infix[i++]) != '\0') {

if (isOperand(c)) {
postfix[k++] = c;
} else if (c == '(') {
push(c);
} else if (c == ')') {
while (!isEmpty() && peek() != '(')
postfix[k++] = pop();
pop(); // Remove '('
} else {
while (!isEmpty() && precedence(peek()) >= precedence(c) && !
isRightAssociative(c))
postfix[k++] = pop();
push(c);
}
}
 while (!isEmpty())
postfix[k++] = pop();

postfix[k] = '\0';
}
Infix to Prefix Conversion:

 Reverse the infix expression.

 Replace '(' with ')' and vice versa.

 Apply infix to postfix logic.

 Reverse the result to get prefix.

#include <string.h>

void reverse(char* str) {

int len = strlen(str);
for (int i = 0; i < len / 2; ++i) {
char temp = str[i];
str[i] = str[len - i - 1];
str[len - i - 1] = temp;
}
}

void replaceParentheses(char* expr) {

for (int i = 0; expr[i] != '\0'; i++) {
if (expr[i] == '(') expr[i] = ')';
else if (expr[i] == ')') expr[i] = '(';
}
}

void infixToPrefix(char* infix, char* prefix) {

reverse(infix);
replaceParentheses(infix);

char postfix[SIZE];
infixToPostfix(infix, postfix);

reverse(postfix);
strcpy(prefix, postfix);
}

Sample main() Function

int main() {
char infix[SIZE], postfix[SIZE], prefix[SIZE];

printf("Enter infix expression: ");

scanf("%s", infix);

infixToPostfix(infix, postfix);
printf("Postfix: %s\n", postfix);
 infixToPrefix(infix, prefix);
printf("Prefix: %s\n", prefix);

return 0;
}

Observation Table:

Input (Infix) Postfix Prefix

A+B*C ABC*+ +A*BC
(A+B)*C AB+C* *+ABC
A+B-C AB+C- -+ABC
A*(B+C)/D ABC+*D/ /\*A+BCD

Conclusion

This lab demonstrates how to:

 Convert infix expressions to postfix and prefix using stack.

 Apply operator precedence and associativity rules.
 Implement and reuse stack operations for expression evaluation tasks.

Experiment No: 11

“Binary tree implementation, operation like insert, update, delete, traversal”

Objective:
To implement a binary tree in C and perform the following operations:

 Insert a node
 Delete a node
 Update a node
 Traverse the tree (Inorder, Preorder, Postorder)

Learning Outcomes

After performing this experiment, students will be able to:

 Implement binary trees using pointers and structures.

 Perform recursive insertions, deletions, and updates in a binary tree.
 Understand and apply different tree traversal techniques.
 Solve real-world hierarchical data problems using binary trees.
Prerequisites

 Understanding of tree data structures.

 Recursive functions in C.
 Pointer-based dynamic memory management.

Structure Definition
#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* left;
struct Node* right;
};
Binary Tree Operations
1. Create New Node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
2. Insert Node (Binary Search Tree Property)
struct Node* insert(struct Node* root, int data) {
if (root == NULL)
return createNode(data);

if (data < root->data)

root->left = insert(root->left, data);
else if (data > root->data)
root->right = insert(root->right, data);

return root;
}
3. Search and Update Node:
int update(struct Node* root, int oldVal, int newVal) {
if (root == NULL) return 0;

if (root->data == oldVal) {
root->data = newVal;
return 1;
}

if (oldVal < root->data)

return update(root->left, oldVal, newVal);
else
return update(root->right, oldVal, newVal);
}
4. Find Minimum Node (For Deletion):
struct Node* findMin(struct Node* node) {
while (node && node->left != NULL)
 node = node->left;
return node;
}
5. Delete Node:
struct Node* deleteNode(struct Node* root, int key) {
if (root == NULL) return root;

if (key < root->data)

root->left = deleteNode(root->left, key);
else if (key > root->data)
root->right = deleteNode(root->right, key);
else {
// Node with one child or no child
if (root->left == NULL) {
struct Node* temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL) {
struct Node* temp = root->left;
free(root);
return temp;
}

// Node with two children

struct Node* temp = findMin(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}

return root;
}
6. Tree Traversals:
void inorder(struct Node* root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}

void preorder(struct Node* root) {

if (root != NULL) {
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}
}

void postorder(struct Node* root) {

if (root != NULL) {
postorder(root->left);
postorder(root->right);
printf("%d ", root->data);
 }
}

Sample main() Function:

int main() {
struct Node* root = NULL;

root = insert(root, 50);

insert(root, 30);
insert(root, 70);
insert(root, 20);
insert(root, 40);
insert(root, 60);
insert(root, 80);

printf("Inorder traversal: ");

inorder(root); printf("\n");

printf("Preorder traversal: ");

preorder(root); printf("\n");

printf("Postorder traversal: ");

postorder(root); printf("\n");

update(root, 60, 65);

printf("Inorder after update: ");
inorder(root); printf("\n");

root = deleteNode(root, 70);

printf("Inorder after deletion: ");
inorder(root); printf("\n");

return 0;
}
Observation Table:

Operation Input Output Remarks

Insert 50, 30...80 Tree built Working
Traversal - Inorder/Pre/Post shown Correct order
Update 60 → 65 Tree updated Verified
Delete 70 Deleted, BST restructured Confirmed

Conclusion

This lab session covers:

 Binary Tree creation and recursive insertion.

 Deletion using in-order successor logic.
 Updating nodes by search.
 Traversals using recursion.
  Memory management using malloc and free.

Experiment No: 12

“Implementation of Sorting and Searching Algorithms”

Learning Objectives

 Understand and implement efficient sorting algorithms: Quick Sort, Merge Sort, and
Bucket Sort.
 Understand and implement searching algorithms: Linear Search and Binary Search.
 Analyze the time and space complexity of each algorithm.
 Compare the performance of different sorting and searching techniques.

Quick Sort Implementation

Algorithm:

 Choose a pivot element.

 Partition the array around the pivot such that elements less than pivot go to left, greater
to right.
 Recursively apply the above steps.

C Code:

#include <stdio.h>

void quickSort(int arr[], int low, int high);

int partition(int arr[], int low, int high);

int main() {
int arr[] = {34, 7, 23, 32, 5, 62};
int n = sizeof(arr)/sizeof(arr[0]);

quickSort(arr, 0, n-1);

printf("Sorted array: ");

for(int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}

void quickSort(int arr[], int low, int high) {

if (low < high) {
int pi = partition(arr, low, high);

quickSort(arr, low, pi - 1);

quickSort(arr, pi + 1, high);
}
}

int partition(int arr[], int low, int high) {

 int pivot = arr[high];
int i = low - 1;

for(int j = low; j < high; j++) {

if (arr[j] < pivot) {
i++;
int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
}
}
int temp = arr[i+1]; arr[i+1] = arr[high]; arr[high] = temp;
return i + 1;
}

Merge Sort Implementation

Algorithm:

 Divide the array into halves.

 Recursively sort each half.
 Merge the sorted halves.

C Code:

#include <stdio.h>

void merge(int arr[], int l, int m, int r);

void mergeSort(int arr[], int l, int r);

int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr)/sizeof(arr[0]);

mergeSort(arr, 0, n - 1);

printf("Sorted array: ");

for(int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}

void merge(int arr[], int l, int m, int r) {

int n1 = m - l + 1, n2 = r - m;
int L[n1], R[n2];

for(int i = 0; i < n1; i++) L[i] = arr[l + i];

for(int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];

int i = 0, j = 0, k = l;
while(i < n1 && j < n2)
arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
while(i < n1) arr[k++] = L[i++];
while(j < n2) arr[k++] = R[j++];
}

void mergeSort(int arr[], int l, int r) {

 if(l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}

Bucket Sort Implementation

Algorithm:

 Divide the array into a number of buckets.

 Sort each bucket individually.
 Concatenate all buckets.

C Code (For integers between 0 and 99):

#include <stdio.h>
#define SIZE 10

void insertionSort(int arr[], int n) {

for(int i = 1; i < n; i++) {
int key = arr[i], j = i - 1;
while(j >= 0 && arr[j] > key)
arr[j + 1] = arr[j--];
arr[j + 1] = key;
}
}

void bucketSort(int arr[], int n) {

int buckets[SIZE][SIZE], count[SIZE] = {0};

for(int i = 0; i < n; i++) {

int index = arr[i] / 10;
buckets[index][count[index]++] = arr[i];
}

for(int i = 0; i < SIZE; i++)

insertionSort(buckets[i], count[i]);

int k = 0;
for(int i = 0; i < SIZE; i++)
for(int j = 0; j < count[i]; j++)
arr[k++] = buckets[i][j];
}

int main() {
int arr[] = {29, 25, 3, 49, 9, 37, 21, 43};
int n = sizeof(arr)/sizeof(arr[0]);

bucketSort(arr, n);

printf("Sorted array: ");

for(int i = 0; i < n; i++)
 printf("%d ", arr[i]);
return 0;
}

Searching Algorithms

Linear Search
int linearSearch(int arr[], int n, int key) {
for(int i = 0; i < n; i++)
if(arr[i] == key)
return i;
return -1;
}

Binary Search (Requires sorted array):

int binarySearch(int arr[], int low, int high, int key) {

while(low <= high) {
int mid = (low + high) / 2;
if(arr[mid] == key) return mid;
else if(arr[mid] < key) low = mid + 1;
else high = mid - 1;
}

return -1;

Time Complexities:

Algorithm Best Average Worst

Quick Sort O(n log n) O(n log n) O(n²)
Merge Sort O(n log n) O(n log n) O(n log n)
Bucket Sort O(n + k) O(n + k) O(n²)
Linear Search O(1) O(n) O(n)
Binary Search O(1) O(log n) O(log n)

Experiment No: 13

“Implementation of Minimum Spanning Tree (MST) for a Given Graph using BFS and DFS
Algorithms”

Learning Objectives

 Understand the concept of Minimum Spanning Tree (MST).

  Learn how BFS (Breadth First Search) and DFS (Depth First Search) work in graph
traversal.
 Apply BFS/DFS traversal strategies to generate MST-like trees (note: BFS and DFS
themselves do not directly generate MSTs, but can be used to explore spanning trees).
 Build foundational understanding leading to Kruskal's and Prim's algorithms.

Theory Overview

 Spanning Tree: A subgraph that includes all the vertices of a graph and is a tree (no
cycles).
 Minimum Spanning Tree (MST): A spanning tree with the minimum possible total
edge weight.
 BFS and DFS: Graph traversal methods that can be used to construct spanning trees,
although not necessarily the minimum one.

Note: To compute true MSTs, use Prim’s or Kruskal’s algorithm. However, this lab focuses on
spanning trees using BFS and DFS logic.

Graph Representation

Use Adjacency List or Adjacency Matrix for graph representation.

Implementation: BFS-Based Spanning Tree

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

int adj[MAX][MAX];
int visited[MAX];
int n; // Number of vertices

void bfs(int start) {

int queue[MAX], front = 0, rear = 0;
visited[start] = 1;
queue[rear++] = start;

printf("BFS Spanning Tree:\n");

while (front < rear) {

int u = queue[front++];
for (int v = 0; v < n; v++) {
if (adj[u][v] && !visited[v]) {
visited[v] = 1;
queue[rear++] = v;
printf("%d - %d\n", u, v); // Edge in spanning tree
}
}
}
}

int main() {
int edges, u, v;
printf("Enter number of vertices: ");
scanf("%d", &n);
printf("Enter number of edges: ");
scanf("%d", &edges);

for (int i = 0; i < edges; i++) {

printf("Enter edge (u v): ");
scanf("%d %d", &u, &v);
adj[u][v] = adj[v][u] = 1;
}

for (int i = 0; i < n; i++) visited[i] = 0;

int start;
printf("Enter start vertex: ");
scanf("%d", &start);

bfs(start);

return 0;
}
Implementation: DFS-Based Spanning Tree:-
#include <stdio.h>
#include <stdlib.h>

#define MAX 100

int adj[MAX][MAX];
int visited[MAX];
int n;

void dfs(int u) {
visited[u] = 1;
for (int v = 0; v < n; v++) {
if (adj[u][v] && !visited[v]) {
printf("%d - %d\n", u, v); // Edge in spanning tree
dfs(v);
}
}
}

int main() {
int edges, u, v;
printf("Enter number of vertices: ");
scanf("%d", &n);
printf("Enter number of edges: ");
scanf("%d", &edges);

for (int i = 0; i < edges; i++) {

 printf("Enter edge (u v): ");
scanf("%d %d", &u, &v);
adj[u][v] = adj[v][u] = 1;
}

for (int i = 0; i < n; i++) visited[i] = 0;

int start;
printf("Enter start vertex: ");
scanf("%d", &start);

printf("DFS Spanning Tree:\n");

dfs(start);

return 0;
}

Important Notes

 BFS and DFS construct spanning trees starting from a root, but do not guarantee
minimal total weight.
 Prim's and Kruskal's algorithms are required for MST with weights.
 In unweighted graphs, the DFS/BFS spanning tree can be used as an approximation or
to study basic tree structures.

Complexity Analysis
Algorithm Time Complexity Space Complexity

BFS O(V + E) O(V)

DFS O(V + E) O(V)

Viva Questions

1. What is a spanning tree?

2. Can BFS/DFS guarantee minimum weight in MST?
3. What’s the difference between BFS and DFS spanning trees?
4. What is the time complexity of BFS and DFS?
5. How do BFS and DFS behave on disconnected graphs?

Experiment No: 14

“Implementation of Symbol Table using Hash Table”

Learning Objectives

 Understand the concept and role of a symbol table in compilers and interpreters.
 Implement a hash table to manage symbol information efficiently.
  Perform basic operations on the symbol table: insert, search, update, and delete.
 Explore collision handling techniques such as chaining and open addressing.

Theory Overview

What is a Symbol Table?

A symbol table is a data structure used by a compiler to keep track of identifiers (like variable
names, function names) and their associated information (such as type, scope, address, etc.).

Why Hash Table?

 Fast lookup, insertion, and deletion (average-case O(1) time).

 Efficient for storing large numbers of symbols.

Basic Operations:

1. Insert: Add a new identifier.

2. Search: Find details of an identifier.
3. Update: Modify existing entry.
4. Delete: Remove an identifier.

Structure of a Symbol Entry

typedef struct Symbol {
char name[20]; // Identifier name
char type[10]; // Data type (int, float, etc.)
int scope; // Scope level
struct Symbol* next; // For chaining in case of collision
} Symbol;

Implementation using Chaining (Separate Chaining for Collision Handling)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZE 10

typedef struct Symbol {

char name[20];
char type[10];
int scope;
struct Symbol* next;
} Symbol;

Symbol* table[SIZE];

// Hash Function
int hash(char *name) {
int sum = 0;
for (int i = 0; name[i] != '\0'; i++)
sum += name[i];
return sum % SIZE;
}

// Insert a symbol
void insert(char *name, char *type, int scope) {
int index = hash(name);
Symbol* newSymbol = (Symbol*)malloc(sizeof(Symbol));
strcpy(newSymbol->name, name);
strcpy(newSymbol->type, type);
newSymbol->scope = scope;
newSymbol->next = table[index];
table[index] = newSymbol;
printf("Inserted: %s (%s), scope: %d\n", name, type, scope);
}

// Search for a symbol

Symbol* search(char *name) {
int index = hash(name);
Symbol* temp = table[index];
while (temp) {
if (strcmp(temp->name, name) == 0)
return temp;
temp = temp->next;
}
return NULL;
}

// Delete a symbol
void delete(char *name) {
int index = hash(name);
Symbol *temp = table[index], *prev = NULL;
while (temp) {
if (strcmp(temp->name, name) == 0) {
if (prev) prev->next = temp->next;
else table[index] = temp->next;
free(temp);
printf("Deleted: %s\n", name);
return;
}
prev = temp;
temp = temp->next;
}
printf("Symbol not found: %s\n", name);
}

// Display symbol table

void display() {
printf("\nSymbol Table:\n");
for (int i = 0; i < SIZE; i++) {
Symbol* temp = table[i];
if (temp) {
printf("Index %d -> ", i);
while (temp) {
printf("[%s | %s | %d] -> ", temp->name, temp->type, temp->scope);
temp = temp->next;
}
printf("NULL\n");
}
}
}

Main Function to Drive the Program:

int main() {
int choice, scope;
 char name[20], type[10];

while (1) {
printf("\n1. Insert\n2. Search\n3. Delete\n4. Display\n5. Exit\
nEnter choice: ");
scanf("%d", &choice);

switch (choice) {
case 1:
printf("Enter name, type, and scope: ");
scanf("%s %s %d", name, type, &scope);
insert(name, type, scope);
break;
case 2:
printf("Enter name to search: ");
scanf("%s", name);
Symbol* sym = search(name);
if (sym)
printf("Found: %s (%s), scope: %d\n", sym->name, sym-
>type, sym->scope);
else
printf("Symbol not found\n");
break;
case 3:
printf("Enter name to delete: ");
scanf("%s", name);
delete(name);
break;
case 4:
display();
break;
case 5:
exit(0);
}
}
return 0;
}

Time and Space Complexity:

Operation Average Case Worst Case (with collisions)

Insert O(1) O(n)
Search O(1) O(n)
Delete O(1) O(n)
Viva Questions

1. What is a symbol table and where is it used?

2. Why do we use a hash table for symbol table implementation?
3. What are the common collision resolution techniques?
4. What is the difference between open addressing and chaining?
5. What is the significance of scope in a symbol table?