Here are some solved practical slips for Master's in Computer Science:
*Slip 1: Sorting Algorithms*
Implement the following sorting algorithms and analyze their time and space complexity:
- Bubble Sort
- Selection Sort
- Insertion Sort
- Merge Sort
- Quick Sort
*Solution:*
#include <iostream>
using namespace std;
// Bubble Sort
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], arr[j + 1]);
}
}
}
}
// Selection Sort
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
swap(arr[minIndex], arr[i]);
}
}
// Insertion Sort
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
// Merge Sort
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int* leftArr = new int[n1];
int* rightArr = new int[n2];
for (int i = 0; i < n1; i++) {
leftArr[i] = arr[left + i];
}
for (int j = 0; j < n2; j++) {
rightArr[j] = arr[mid + 1 + j];
}
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (leftArr[i] <= rightArr[j]) {
arr[k] = leftArr[i];
i++;
} else {
arr[k] = rightArr[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = leftArr[i];
i++;
k++;
}
while (j < n2) {
arr[k] = rightArr[j];
j++;
k++;
}
}
// Quick Sort
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++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return i + 1;
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
cout << "Sorted array (Bubble Sort): ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
*Slip 2: Searching Algorithms*
Implement the following searching algorithms and analyze their time and space complexity:
- Linear Search
- Binary Search
*Solution:*
#include <iostream>
using namespace std;
// Linear Search
int linearSearch(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i;
}
}
return -1;
}
// Binary Search
int binarySearch(int arr[], int n, int target) {
int left = 0;
int right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
int main() {
int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 23;
int result = linearSearch(arr, n, target);
if (result != -1) {
cout << "Target found at index " << result << " using Linear Search." << endl;
} else {
cout << "Target not found using Linear Search." << endl;
}
result = binarySearch(arr, n, target);
if (result != -1) {
cout << "Target found at index " << result << " using Binary Search." << endl;
} else {
cout << "Target not found using Binary Search." << endl;
}
return 0;
}
*Slip 3: Graph Traversal*
Implement the following graph traversal algorithms:
- Breadth-First Search (BFS)
- Depth-First Search (DFS)
*Solution:*
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
class Graph {
public:
int numVertices;
vector<vector<int>> adjList;
Graph(int numVertices) {
this->numVertices = numVertices;
adjList.resize(numVertices);
}
void addEdge(int u, int v) {
adjList[u].push_back(v);
adjList[v].push_back(u);
}
void bfs(int startVertex) {
vector<bool> visited(numVertices, false);
queue<int> q;
visited[startVertex] = true;
q.push(startVertex);
while (!q.empty()) {
int currentVertex = q.front();
cout << currentVertex << " ";
q.pop();
for (int neighbor : adjList[currentVertex]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
}
void dfs(int startVertex) {
vector<bool> visited(numVertices, false);
dfsHelper(startVertex, visited);
}
void dfsHelper(int currentVertex, vector<bool>& visited) {
visited[currentVertex] = true;
cout << currentVertex << " ";
for (int neighbor : adjList[currentVertex]) {
if (!visited[neighbor]) {
dfsHelper(neighbor, visited);
}
}
}
};
int main() {
Graph graph(6);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 5);
cout << "BFS Traversal: ";
graph.bfs(0);
cout << endl;
cout << "DFS Traversal: ";
graph.dfs(0);
cout << endl;
return 0;
}
// Recursive implementation of DFS
void dfs(int startVertex) {
vector<bool> visited(numVertices, false);
dfsHelper(startVertex, visited);
}
void dfsHelper(int currentVertex, vector<bool>& visited) {
visited[currentVertex] = true;
cout << currentVertex << " ";
for (int neighbor : adjList[currentVertex]) {
if (!visited[neighbor]) {
dfsHelper(neighbor, visited);
}
}
}
*Slip 4: Dynamic Programming*
Implement the following dynamic programming problems:
- Fibonacci Series
- Longest Common Subsequence (LCS)
*Solution:*
#include <iostream>
#include <vector>
using namespace std;
// Fibonacci Series
int fibonacci(int n) {
vector<int> fib(n + 1);
fib[0] = 0;
fib[1] = 1;
for (int i = 2; i <= n; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
}
return fib[n];
}
// Longest Common Subsequence (LCS)
int lcs(string str1, string str2) {
int m = str1.length();
int n = str2.length();
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 0;
} else if (str1[i - 1] == str2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
int main() {
int n = 10;
cout << "Fibonacci number at position " << n << " is " << fibonacci(n) << endl;
string str1 = "AGGTAB";
string str2 = "GXTXAYB";
cout << "Length of LCS is " << lcs(str1, str2) << endl;
return 0;
}
These are just a few examples of solved practical slips for Master's in Computer Science. There are many more topics and problems that can be covered.
No comments:
Post a Comment