# Untitled

unknown
plain_text
a year ago
9.8 kB
1
Indexable
Never
```//ACTIVITY SELECTION

#include <iostream>
using namespace std;
void printMaxActivities(int s[], int f[], int n)
{
int i, j;
cout << "Following activities are selected" << endl;
i = 0;
cout << i << " ";
for (j = 1; j < n; j++) {
// If this activity has start time greater than or
// equal to the finish time of previously selected
// activity, then select it
if (s[j] >= f[i]) {
cout << j << " ";
i = j;
}
}
}
int main()
{
int s[] = { 1, 3, 0, 5, 8, 5 };
int f[] = { 2, 4, 6, 7, 9, 9 };
int n = sizeof(s) / sizeof(s[0]);
printMaxActivities(s, f, n);
return 0;
}

pseudocode:
n ← length [s]
A ← {1}
j ← 1.
for i ← 2 to n
do if si ≥ fi
then A ← A ∪ {i}
j ← i
return A
......................................................................................................................

//MATRIX CHAIN MULTIPLICATION

#include <iostream>
using namespace std;
int MatrixChainOrder(int p[], int i, int j)
{
if (i == j)
return 0;
int k;
int mini = INT_MAX;
int count;
for (k = i; k < j; k++)
{
count = MatrixChainOrder(p, i, k)
+ MatrixChainOrder(p, k + 1, j)
+ p[i - 1] * p[k] * p[j];

mini = min(count, mini);
}
return mini;
int main()
{
int arr[] = { 1, 2, 3, 4, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << "Minimum number of multiplications is "
<< MatrixChainOrder(arr, 1, N - 1);
return 0;
}
...................................................................................

// 0-1 knapsack

#include <iostream>
using namespace std;
int max(int a, int b) { return (a > b) ? a : b; }
int knapSack(int W, int wt[], int val[], int n)
{
if (n == 0 || W == 0)
return 0;
if (wt[n - 1] > W)
return knapSack(W, wt, val, n - 1);
else
return max(
val[n - 1]
+ knapSack(W - wt[n - 1], wt, val, n - 1),
knapSack(W, wt, val, n - 1));
}
int main()
{
int profit[] = { 60, 100, 120 };
int weight[] = { 10, 20, 30 };
int W = 50;
int n = sizeof(profit) / sizeof(profit[0]);
cout << knapSack(W, weight, profit, n);
return 0;
}
...................................................................................

//MAXIMUM SUM SUBARRAY

#include <iostream>
using namespace std;
int max(int a, int b) {
return (a > b) ? a : b;
}
int max(int a, int b, int c) {
return max(max(a, b), c);
}
int maxCrossingSum(int arr[], int l, int m, int h) {
int sum = 0;
int left_sum = INT_MIN;
for (int i = m; i >= l; i--) {
sum = sum + arr[i];
if (sum > left_sum)
left_sum = sum;
}
sum = 0;
int right_sum = INT_MIN;
for (int i = m; i <= h; i++) {
sum = sum + arr[i];
if (sum > right_sum)
right_sum = sum;
}
return max(left_sum + right_sum - arr[m], left_sum, right_sum);
}
int maxSubArraySum(int arr[], int l, int h) {
if (l > h)
return INT_MIN;
if (l == h)
return arr[l];
int m = (l + h) / 2;
return max(maxSubArraySum(arr, l, m - 1),
maxSubArraySum(arr, m + 1, h),
maxCrossingSum(arr, l, m, h));
}
int main() {
int arr[] = { 2, 3, 4, 5, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
int max_sum = maxSubArraySum(arr, 0, n - 1);
cout << "Maximum contiguous sum is " << max_sum;
return 0;
}
..............................................................................................

//Rabin karp

#include <iostream>
using namespace std;
#define d 256
void search(char pat[], char txt[], int q)
{
int M = strlen(pat);
int N = strlen(txt);
int i, j;
int p = 0; // hash value for pattern
int t = 0; // hash value for txt
int h = 1;
for (i = 0; i < M - 1; i++)
h = (h * d) % q;
for (i = 0; i < M; i++) {
p = (d * p + pat[i]) % q;
t = (d * t + txt[i]) % q;
}
for (i = 0; i <= N - M; i++) {
if (p == t) {
/* Check for characters one by one */
for (j = 0; j < M; j++) {
if (txt[i + j] != pat[j]) {
break;
}
}
if (j == M)
cout << "Pattern found at index " << i
<< endl;
}
if (i < N - M) {
t = (d * (t - txt[i] * h) + txt[i + M]) % q;
if (t < 0)
t = (t + q);
}
}
}
int main()
{
char txt[] = "GEEKS FOR GEEKS";
char pat[] = "GEEK";
int q = INT_MAX;
search(pat, txt, q);
return 0;
}
...................................................................................

//floyd warshell

#include <iostream>
using namespace std;
#define V 4
#define INF 99999
void printSolution(int dist[][V]);
void floydWarshall(int dist[][V])
{

int i, j, k;
for (k = 0; k < V; k++) {
for (i = 0; i < V; i++) {
for (j = 0; j < V; j++) {
if (dist[i][j] > (dist[i][k] + dist[k][j])
&& (dist[k][j] != INF
&& dist[i][k] != INF))
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
printSolution(dist);
}
void printSolution(int dist[][V])
{
cout << "The following matrix shows the shortest "
"distances"
" between every pair of vertices \n";
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][j] == INF)
cout << "INF"
<< " ";
else
cout << dist[i][j] << " ";
}
cout << endl;
}
}
int main()
{
floydWarshall(graph);
return 0;
}
...................................................................................

//ford fulkerson

#include <iostream>
#include <limits.h>
#include <queue>
#include <string.h>
using namespace std;
#define V 6
bool bfs(int rGraph[V][V], int s, int t, int parent[])
{
bool visited[V];
memset(visited, 0, sizeof(visited));
queue<int> q;
q.push(s);
visited[s] = true;
parent[s] = -1;
while (!q.empty()) {
int u = q.front();
q.pop();

for (int v = 0; v < V; v++) {
if (visited[v] == false && rGraph[u][v] > 0) {
if (v == t) {
parent[v] = u;
return true;
}
q.push(v);
parent[v] = u;
visited[v] = true;
}
}
}
return false;
}
int fordFulkerson(int graph[V][V], int s, int t)
{
int u, v;
int rGraph[V]
[V];
for (u = 0; u < V; u++)
for (v = 0; v < V; v++)
rGraph[u][v] = graph[u][v];

int parent[V];
int max_flow = 0;
while (bfs(rGraph, s, t, parent)) {
int path_flow = INT_MAX;
for (v = t; v != s; v = parent[v]) {
u = parent[v];
path_flow = min(path_flow, rGraph[u][v]);
}
for (v = t; v != s; v = parent[v]) {
u = parent[v];
rGraph[u][v] -= path_flow;
rGraph[v][u] += path_flow;
}
max_flow += path_flow;
}
return max_flow;
}
int main()
{
int graph[V][V]
= { { 0, 16, 13, 0, 0, 0 }, { 0, 0, 10, 12, 0, 0 },
{ 0, 4, 0, 0, 14, 0 }, { 0, 0, 9, 0, 0, 20 },
{ 0, 0, 0, 7, 0, 4 }, { 0, 0, 0, 0, 0, 0 } };

cout << "The maximum possible flow is "
<< fordFulkerson(graph, 0, 5);

return 0;
}
................................................................................................

//randomized quick sort

#include <cstdlib>
#include <time.h>
#include <iostream>
using namespace std;
int partition(int arr[], int low, int high)
{
int pivot = arr[high];
int i = (low - 1);

for (int j = low; j <= high - 1; j++)
{
if (arr[j] <= pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return (i + 1);
}
int partition_r(int arr[], int low, int high)
{
srand(time(NULL));
int random = low + rand() % (high - low);
swap(arr[random], arr[high]);

return partition(arr, low, high);
}
void quickSort(int arr[], int low, int high)
{
if (low < high) {
int pi = partition_r(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
cout<<arr[i]<<" ";
}
int main()
{
int arr[] = { 10, 7, 8, 9, 1, 5 };
int n = sizeof(arr) / sizeof(arr[0]);

quickSort(arr, 0, n - 1);
printf("Sorted array: \n");
printArray(arr, n);

return 0;
}
..................................................................................
//maze backtracking

#include <iostream>
using namespace std;
#define N 4
bool solveMazeUtil(int maze[N][N], int x, int y,int sol[N][N]);
void printSolution(int sol[N][N])
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
cout<<" "<<sol[i][j]<<" ";
cout<<endl;
}
}
bool isSafe(int maze[N][N], int x, int y)
{
if (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1)
return true;
return false;
}
bool solveMaze(int maze[N][N])
{
int sol[N][N] = { { 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 } };
if (solveMazeUtil(maze, 0, 0, sol) == false) {
cout<<"Solution doesn't exist";
return false;
}
printSolution(sol);
return true;
}
bool solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N])
{
if (x == N - 1 && y == N - 1 && maze[x][y] == 1) {
sol[x][y] = 1;
return true;
}
if (isSafe(maze, x, y) == true) {
if (sol[x][y] == 1)
return false;
sol[x][y] = 1;
if (solveMazeUtil(maze, x + 1, y, sol) == true)
return true;
if (solveMazeUtil(maze, x - 1, y, sol) == true)
return true;
if (solveMazeUtil(maze, x, y + 1, sol) == true)
return true;
if (solveMazeUtil(maze, x, y - 1, sol) == true)
return true;
sol[x][y] = 0;
return false;
}
return false;
}
int main()
{
int maze[N][N] = { { 1, 0, 0, 0 },
{ 1, 1, 0, 1 },
{ 0, 1, 0, 0 },
{ 1, 1, 1, 1 } };
solveMaze(maze);
return 0;
}

```