1) Algorithm for Stack Operations:
1. Push Operation:
Step 1: Check if the stack is full. If it is, print an error message (stack overflow).
Step 2: If the stack is not full, increment the top pointer and insert the new element at the top of the stack.
If top == MAX - 1
Print "Stack Overflow"
Else
top = top + 1
stack[top] = x
2. Pop Operation:
Step 1: Check if the stack is empty. If it is, print an error message (stack underflow).
Step 2: If the stack is not empty, pop the top element and decrement the top pointer.
If top == -1
Print "Stack Underflow"
Else
item = stack[top]
top = top - 1
Return item
3. Peek/Top Operation:
Step 1: Check if the stack is empty. If it is, print an error message (stack is empty).
Step 2: If the stack is not empty, return the element at the top of the stack.
If top == -1
Print "Stack is Empty"
Else
Return stack[top]
4. IsEmpty Operation:
Step 1: Check if the stack's top pointer is -1 (indicating no elements in the stack). If it is, return true (stack is
empty).
Step 2: If the stack is not empty, return false.
Return (top == -1)
5. IsFull Operation:
Step 1: Check if the top pointer is at the last index of the stack (i.e., top == MAX - 1). If true, return true
(stack is full).
Step 2: If the stack is not full, return false.
Return (top == MAX - 1)
C Code Implementation
#include <stdio.h>
#define MAX 100
int stack[MAX];
int top = -1;
// a) Push operation
void push(int value) {
if (top == MAX - 1) {
printf("Stack Overflow! Cannot push %d\n", value);
} else {
top++;
stack[top] = value;
printf("Pushed %d to stack\n", value);
}
}
// b) Pop operation
int pop() {
if (top == -1) {
printf("Stack Underflow! Cannot pop\n");
return -1;
} else {
int value = stack[top];
top--;
printf("Popped %d from stack\n", value);
return value;
}
}
// c) Peek / Top operation
int peek() {
if (top == -1) {
printf("Stack is Empty!\n");
return -1;
} else {
return stack[top];
}
}
// d) IsEmpty operation
int isEmpty() {
return top == -1;
}
// e) IsFull operation
int isFull() {
return top == MAX - 1;
}
// Main function to demonstrate stack operations
int main() {
push(10);
push(20);
push(30);
printf("Top element is: %d\n", peek());
pop();
printf("Top element after pop: %d\n", peek());
printf("Is stack empty? %s\n", isEmpty() ? "Yes" : "No");
printf("Is stack full? %s\n", isFull() ? "Yes" : "No");
return 0;
}
Output:
Pushed 10 to stack
Pushed 20 to stack
Pushed 30 to stack
Top element is: 30
Popped 30 from stack
Top element after pop: 20
Is stack empty? No
Is stack full? No
2) Implement Linear Search and Binary Search Algorithm and code.
Linear Search
Algorithm Steps:
1. Start
2. Read array size n
3. Read array elements arr[0...n-1]
4. Read the key to be searched
5. Set i = 0
6. Repeat steps 7 to 9 while i < n:
7. If arr[i] == key then:
8. Return i (element found at index i)
9. Increment i by 1
7. If loop ends and key is not found, return -1
8. Stop
Example:
• Array: arr[] = {5, 3, 9, 7, 2}
• Key to search: 7
• It will check:
o 5 ≠ 7,
o 3 ≠ 7,
o 9 ≠ 7,
o 7 == 7 → Found at index 3
Code: Linear Search
#include <stdio.h>
int linearSearch(int arr[], int n, int key) {
for (int i = 0; i < n; i++) {
if (arr[i] == key)
return i; // Return index
}
return -1; // Not found
}
int main() {
int arr[] = {5, 3, 8, 4, 2};
int key = 4;
int n = sizeof(arr) / sizeof(arr[0]);
int result = linearSearch(arr, n, key);
if (result != -1)
printf("Element %d found at index %d\n", key, result);
else
printf("Element %d not found\n", key);
return 0;
}
Output:
Element 4 found at index 3
Binary Search
Problem:
Search for a given element (key) in a sorted array using Binary Search
Algorithm Steps:
1. Start
2. Read array size n
3. Read the sorted array elements arr[0...n-1]
4. Read the key to be searched
5. Initialize low = 0, high = n - 1
6. Repeat steps 7 to 12 while low <= high:
7. Calculate mid = (low + high) / 2
8. If arr[mid] == key then:
9. Return mid (element found)
10. Else if arr[mid] < key then:
11. Set low = mid + 1
12. Else:
13. Set high = mid - 1
7. If loop ends and key is not found, return -1
8. Stop
Example:
• Array: arr[] = {2, 4, 6, 8, 10}
• Key to search: 8
• Iterations:
o low = 0, high = 4, mid = 2 → arr[2] = 6 < 8 → search right half
o low = 3, high = 4, mid = 3 → arr[3] = 8 == 8 → Found at index 3
Code: Binary Search
#include <stdio.h>
int binarySearch(int arr[], int n, int key) {
int low = 0, high = n - 1;
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; // Not found
}
int main() {
int arr[] = {2, 4, 6, 8, 10}; // Must be sorted
int key = 8;
int n = sizeof(arr) / sizeof(arr[0]);
int result = binarySearch(arr, n, key);
if (result != -1)
printf("Element %d found at index %d\n", key, result);
else
printf("Element %d not found\n", key);
return 0;
}
Output:
Element 8 found at index 3
3) Implement Bubble Sort and SelecƟon Sort Algorithm and Code.
BUBBLE SORT
Algorithm Steps:
1. Start
2. Read the number of elements n
3. Read the array arr[0...n-1]
4. Repeat step 5 to 8 for i = 0 to n-2
5. Repeat step 6 to 7 for j = 0 to n-i-2
6. If arr[j] > arr[j+1], then:
7. Swap arr[j] and arr[j+1]
8. End inner loop
9. End outer loop
10. Print sorted array
11. Stop
Example: Bubble Sort
Given Array:
arr[] = {5, 1, 4, 2, 8}
Pass 1:
• Compare 5 and 1 → swap → {1, 5, 4, 2, 8}
• Compare 5 and 4 → swap → {1, 4, 5, 2, 8}
• Compare 5 and 2 → swap → {1, 4, 2, 5, 8}
• Compare 5 and 8 → no swap → {1, 4, 2, 5, 8}
Pass 2:
• Compare 1 and 4 → no swap
• Compare 4 and 2 → swap → {1, 2, 4, 5, 8}
• Compare 4 and 5 → no swap
Pass 3:
• Compare 1 and 2 → no swap
• Compare 2 and 4 → no swap
Pass 4:
• Already sorted
Final Sorted Array: {1, 2, 4, 5, 8}
C Code: Bubble Sort
#include <stdio.h>
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap arr[j] and arr[j+1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr)/sizeof(arr[0]);
bubbleSort(arr, n);
printf("Sorted array using Bubble Sort:\n");
printArray(arr, n);
return 0;
}
2. SELECTION SORT
Algorithm Steps:
1. Start
2. Read the number of elements n
3. Read the array arr[0...n-1]
4. Repeat step 5 to 9 for i = 0 to n-2
5. Set min_index = i
6. Repeat step 7 for j = i+1 to n-1
7. If arr[j] < arr[min_index], then:
8. min_index = j
9. Swap arr[i] and arr[min_index]
10. End loop
11. Print sorted array
12. Stop
Example: Selection Sort
Given Array:
arr[] = {29, 10, 14, 37, 13}
Pass 1:
• Minimum in {29, 10, 14, 37, 13} → 10
• Swap 29 with 10 → {10, 29, 14, 37, 13}
Pass 2:
• Minimum in {29, 14, 37, 13} → 13
• Swap 29 with 13 → {10, 13, 14, 37, 29}
Pass 3:
• Minimum in {14, 37, 29} → 14
• No swap needed
Pass 4:
• Minimum in {37, 29} → 29
• Swap 37 with 29 → {10, 13, 14, 29, 37}
Final Sorted Array: {10, 13, 14, 29, 37}
C Code: Selection Sort
#include <stdio.h>
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int min_index = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_index])
min_index = j;
}
// Swap arr[i] and arr[min_index]
int temp = arr[i];
arr[i] = arr[min_index];
arr[min_index] = temp;
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {29, 10, 14, 37, 13};
int n = sizeof(arr)/sizeof(arr[0]);
selectionSort(arr, n);
printf("Sorted array using Selection Sort:\n");
printArray(arr, n);
return 0;
}