DATA STRUCTURES & ALGORITHMS
(C / C++ Implementation – Lab & Final Examination Material)
1. String Operations and String Processing
Problem Statement
Write a C/C++ program to perform basic string operations. The program should accept a string from the
user and perform the following operations:
(i) find the length of the string,
(ii) convert the string to uppercase,
(iii) convert the string to lowercase, and
(iv) reverse the string.
Display the results after performing each operation.
Pseudocode
START
READ string S
length ← number of characters in S
PRINT length
FOR each character in S
CONVERT to uppercase
PRINT uppercase string
FOR each character in S
CONVERT to lowercase
PRINT lowercase string
REVERSE string S
PRINT reversed string
END
2. Sparse Matrix
Problem Statement
Write a C/C++ program to convert a given matrix into its sparse matrix representation. The program
should identify and store only the non-zero elements using triplet representation.
Pseudocode
START
READ rows, columns
READ matrix A
count ← 0
FOR each element in A
IF element ≠ 0
STORE row, column, value
count ← count + 1
PRINT sparse matrix
END
3. Saddle Point of a Matrix
Problem Statement
Write a C/C++ program to find the saddle point of a matrix. A saddle point is an element that is the
smallest in its row and the largest in its column.
Pseudocode
START
READ matrix A
FOR each row i
FIND minimum element in row i
CHECK if this element is maximum in its column
IF true
PRINT saddle point
EXIT
PRINT "No saddle point"
END
4. Binary Search Tree (BST)
Problem Statement
Write a C/C++ program to create a Binary Search Tree and perform insertion of nodes. Display the
elements using inorder traversal.
Pseudocode
INSERT(node, value)
IF node is NULL
CREATE new node
ELSE IF value < [Link]
INSERT([Link], value)
ELSE
INSERT([Link], value)
INORDER(node)
IF node ≠ NULL
INORDER([Link])
PRINT [Link]
INORDER([Link])
5. Huffman Coding Algorithm
Problem Statement
Write a C/C++ program to implement Huffman Coding for data compression using character frequencies.
Pseudocode
START
READ characters and frequencies
CREATE leaf nodes
INSERT nodes into min priority queue
WHILE queue size > 1
REMOVE two nodes with lowest frequency
CREATE new node with combined frequency
INSERT new node into queue
GENERATE Huffman codes
END
6. Linear Search
Problem Statement
Write a C/C++ program to search an element in an array using linear search.
Pseudocode
START
READ array and key
FOR i = 0 to n-1
IF array[i] == key
PRINT position
EXIT
PRINT "Element not found"
END
7. Binary Search
Problem Statement
Write a C/C++ program to search an element in a sorted array using binary search.
Pseudocode
START
low ← 0, high ← n-1
WHILE low ≤ high
mid ← (low + high) / 2
IF A[mid] == key
PRINT position
EXIT
ELSE IF key < A[mid]
high ← mid - 1
ELSE
low ← mid + 1
PRINT "Element not found"
END
8. Bubble Sort
Problem Statement
Write a C/C++ program to sort an array using Bubble Sort algorithm.
Pseudocode
START
FOR i = 0 to n-1
FOR j = 0 to n-i-2
IF A[j] > A[j+1]
SWAP A[j], A[j+1]
END
END
9. Selection Sort
Problem Statement
Write a C/C++ program to sort an array using the Selection Sort algorithm.
Pseudocode
START
FOR i = 0 to n-1
min ← i
FOR j = i+1 to n-1
IF A[j] < A[min]
min ← j
SWAP A[i], A[min]
END
END
10. Insertion Sort
Problem Statement
Write a C/C++ program to sort an array using Insertion Sort algorithm.
Pseudocode
START
FOR i = 1 to n-1
key ← A[i]
j←i-1
WHILE j ≥ 0 AND A[j] > key
A[j+1] ← A[j]
j←j-1
A[j+1] ← key
END
END
11. Quick Sort
Problem Statement
Write a C/C++ program to sort an array using the Quick Sort algorithm.
Pseudocode
QUICKSORT(A, low, high)
IF low < high
pivot ← PARTITION(A, low, high)
QUICKSORT(A, low, pivot-1)
QUICKSORT(A, pivot+1, high)
12. Merge Sort
Problem Statement
Write a C/C++ program to sort an array using Merge Sort algorithm.
Pseudocode
MERGESORT(A)
IF size > 1
DIVIDE A into left and right
MERGESORT(left)
MERGESORT(right)
MERGE(left, right)
13. Depth First Search (DFS)
Problem Statement
Write a C/C++ program to traverse a graph using Depth First Search.
Pseudocode
DFS(node)
MARK node as visited
PRINT node
FOR each adjacent node
IF not visited
DFS(adjacent)
14. Breadth First Search (BFS)
Problem Statement
Write a C/C++ program to traverse a graph using Breadth First Search.
Pseudocode
START
ENQUEUE source
MARK source visited
WHILE queue not empty
node ← DEQUEUE
PRINT node
FOR each adjacent node
IF not visited
ENQUEUE node
MARK visited
END
15. Floyd–Warshall Algorithm
Problem Statement
Write a C/C++ program to find the shortest paths between all pairs of vertices using the Floyd–Warshall
algorithm.
Pseudocode
START
READ distance matrix D
FOR k = 1 to n
FOR i = 1 to n
FOR j = 1 to n
D[i][j] ← min(D[i][j], D[i][k] + D[k][j])
END
END
16. Dijkstra’s Algorithm
Problem Statement
Write a C/C++ program to find the shortest path from a source vertex using Dijkstra’s algorithm.
Pseudocode
START
INITIALIZE distances
SET source distance = 0
WHILE unvisited vertices exist
SELECT the vertex with the minimum distance
MARK visited
UPDATE distances of adjacent vertices
END
END
17. Binary search