## CHIT 1A — Sparse Matrix: Addition, Subtraction, Multiplication

```cpp
#include<iostream>
using namespace std;

struct Sparse {
int r, c, nnz;
int data[100][3]; // each row: [row, col, value]
};

void toSparse(int mat[][10], Sparse &s, int r, int c) {

s.r = r; s.c = c; [Link] = 0;
for(int i = 0; i < r; i++)
for(int j = 0; j < c; j++)
if(mat[i][j] != 0) {
[Link][[Link]][0] = i;
[Link][[Link]][1] = j;
[Link][[Link]][2] = mat[i][j];
[Link]++;
}
}

void toFull(Sparse &s, int mat[][10]) {

for(int i = 0; i < s.r; i++)
for(int j = 0; j < s.c; j++)
mat[i][j] = 0;
for(int i = 0; i < [Link]; i++)
mat[[Link][i][0]][[Link][i][1]] = [Link][i][2];
}

void printSparse(Sparse &s) {

cout << "Rows:" << s.r << " Cols:" << s.c << " NNZ:" << [Link] << "\n";
cout << "Row\tCol\tVal\n";
for(int i = 0; i < [Link]; i++)
cout << [Link][i][0] << "\t" << [Link][i][1] << "\t" << [Link][i][2] << "\n";
}

int main() {
int r, c;
cout << "Enter rows and cols (same for both matrices): ";
cin >> r >> c;

int A[10][10], B[10][10], C[10][10];

Sparse sA, sB, sC;

cout << "Enter Matrix A:\n";

for(int i = 0; i < r; i++)
for(int j = 0; j < c; j++)
cin >> A[i][j];

cout << "Enter Matrix B:\n";

 for(int i = 0; i < r; i++)
for(int j = 0; j < c; j++)
cin >> B[i][j];

toSparse(A, sA, r, c);

toSparse(B, sB, r, c);

cout << "\nSparse A:\n"; printSparse(sA);

cout << "\nSparse B:\n"; printSparse(sB);

// Addition
for(int i = 0; i < r; i++)
for(int j = 0; j < c; j++)
C[i][j] = A[i][j] + B[i][j];
toSparse(C, sC, r, c);
cout << "\nA + B (Sparse):\n"; printSparse(sC);

// Subtraction
for(int i = 0; i < r; i++)
for(int j = 0; j < c; j++)
C[i][j] = A[i][j] - B[i][j];
toSparse(C, sC, r, c);
cout << "\nA - B (Sparse):\n"; printSparse(sC);

// Multiplication (square matrices)

cout << "\nA * B (Sparse):\n";
for(int i = 0; i < r; i++)
for(int j = 0; j < c; j++) {
C[i][j] = 0;
for(int k = 0; k < c; k++)
C[i][j] += A[i][k] * B[k][j];
}
toSparse(C, sC, r, c);
printSparse(sC);

return 0;
}
```

---

## CHIT 1B — Fast Transpose of Sparse Matrix

```cpp
#include<iostream>
using namespace std;

void display(int mat[][3], int nnz) {

cout << "Row\tCol\tVal\n";
for(int i = 0; i < nnz; i++)
cout << mat[i][0] << "\t" << mat[i][1] << "\t" << mat[i][2] << "\n";
}
void fastTranspose(int a[][3], int nnz, int rows, int cols, int b[][3], int &bNNZ) {
bNNZ = nnz;
int rowCount[50] = {0};
int rowStart[50] = {0};

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

rowCount[a[i][1]]++;

rowStart[0] = 0;
for(int i = 1; i < cols; i++)
rowStart[i] = rowStart[i-1] + rowCount[i-1];

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

int pos = rowStart[a[i][1]]++;
b[pos][0] = a[i][1];
b[pos][1] = a[i][0];
b[pos][2] = a[i][2];
}
}

int main() {
int r, c;
cout << "Enter rows and cols: ";
cin >> r >> c;

int mat[10][10];
cout << "Enter matrix:\n";
for(int i = 0; i < r; i++)
for(int j = 0; j < c; j++)
cin >> mat[i][j];

int sparse[100][3];
int nnz = 0;
for(int i = 0; i < r; i++)
for(int j = 0; j < c; j++)
if(mat[i][j] != 0) {
sparse[nnz][0] = i;
sparse[nnz][1] = j;
sparse[nnz][2] = mat[i][j];
nnz++;
}

cout << "\nOriginal Sparse:\n";

display(sparse, nnz);

int trans[100][3], tNNZ;

fastTranspose(sparse, nnz, r, c, trans, tNNZ);

cout << "\nTranspose (Fast Transpose):\n";

display(trans, tNNZ);
 return 0;
}
```

---

## CHIT 2A — Linear Probing & Quadratic Probing

```cpp
#include<iostream>
using namespace std;

#define SIZE 10

void linearProbing(int keys[], int n) {

int table[SIZE];
fill(table, table + SIZE, -1);

cout << "\n-- Linear Probing --\n";

for(int i = 0; i < n; i++) {
int pos = keys[i] % SIZE;
int j = 0;
while(table[(pos + j) % SIZE] != -1) j++;
table[(pos + j) % SIZE] = keys[i];
cout << "Inserted " << keys[i] << " at index " << (pos + j) % SIZE << "\n";
}

cout << "\nHash Table:\nIndex\tValue\n";

for(int i = 0; i < SIZE; i++)
cout << i << "\t" << (table[i] == -1 ? 0 : table[i]) << "\n";
}

void quadraticProbing(int keys[], int n) {

int table[SIZE];
fill(table, table + SIZE, -1);

cout << "\n-- Quadratic Probing --\n";

for(int i = 0; i < n; i++) {
int pos = keys[i] % SIZE;
int j = 0;
while(table[(pos + j * j) % SIZE] != -1) j++;
table[(pos + j * j) % SIZE] = keys[i];
cout << "Inserted " << keys[i] << " at index " << (pos + j * j) % SIZE << "\n";
}

cout << "\nHash Table:\nIndex\tValue\n";

for(int i = 0; i < SIZE; i++)
cout << i << "\t" << (table[i] == -1 ? 0 : table[i]) << "\n";
}

int main() {
int n;
 cout << "Enter number of keys: ";
cin >> n;
int keys[100];
cout << "Enter keys: ";
for(int i = 0; i < n; i++) cin >> keys[i];

linearProbing(keys, n);
quadraticProbing(keys, n);

return 0;
}
```

---

## CHIT 2B — Chaining Without Replacement & With Replacement

```cpp
#include<iostream>
using namespace std;

#define SIZE 7

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

Node* newNode(int d) {
Node* n = new Node();
n->data = d; n->next = nullptr;
return n;
}

void appendToEnd(Node** tbl, int pos, Node* nd) {

nd->next = nullptr;
if(!tbl[pos]) { tbl[pos] = nd; return; }
Node* t = tbl[pos];
while(t->next) t = t->next;
t->next = nd;
}

// ---- Without Replacement ----

// New key always appended at end of chain at h(key)
void withoutReplacement(int keys[], int n) {
Node* table[SIZE] = {nullptr};

cout << "\n-- Chaining WITHOUT Replacement --\n";

for(int i = 0; i < n; i++) {
int pos = keys[i] % SIZE;
appendToEnd(table, pos, newNode(keys[i]));
}
 for(int i = 0; i < SIZE; i++) {
cout << "[" << i << "] -> ";
Node* t = table[i];
while(t) { cout << t->data << " -> "; t = t->next; }
cout << "NULL\n";
}
}

// ---- With Replacement ----

// If home slot is occupied by a non-home key, displace it
void withReplacement(int keys[], int n) {
Node* table[SIZE] = {nullptr};

cout << "\n-- Chaining WITH Replacement --\n";

for(int i = 0; i < n; i++) {
int key = keys[i];
int pos = key % SIZE;

if(!table[pos]) {
// Slot empty, insert directly
table[pos] = newNode(key);
} else if(table[pos]->data % SIZE != pos) {
// Head doesn't belong here — displace it
Node* displaced = table[pos];
Node* rest = displaced->next;
displaced->next = nullptr;

// Place new key at its home

table[pos] = newNode(key);

// Move displaced head to its real home

int dpos = displaced->data % SIZE;
appendToEnd(table, dpos, displaced);

// Reinsert rest of displaced chain

Node* cur = rest;
while(cur) {
Node* nxt = cur->next;
cur->next = nullptr;
appendToEnd(table, cur->data % SIZE, cur);
cur = nxt;
}
} else {
// Head belongs here, append at end
appendToEnd(table, pos, newNode(key));
}
}

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

cout << "[" << i << "] -> ";
Node* t = table[i];
while(t) { cout << t->data << " -> "; t = t->next; }
 cout << "NULL\n";
}
}

int main() {
int n;
cout << "Enter number of keys (table size = " << SIZE << "): ";
cin >> n;
int keys[100];
cout << "Enter keys: ";
for(int i = 0; i < n; i++) cin >> keys[i];

withoutReplacement(keys, n);
withReplacement(keys, n);

return 0;
}
```

---

## CHIT 3A — Dijkstra's Algorithm (Greedy)

```cpp
#include<iostream>
using namespace std;

#define INF 99999

#define MAX 10

int dist[MAX], visited[MAX], graph[MAX][MAX], n;

void dijkstra(int src) {

for(int i = 0; i < n; i++) { dist[i] = INF; visited[i] = 0; }
dist[src] = 0;

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

// Pick unvisited vertex with min distance
int u = -1;
for(int j = 0; j < n; j++)
if(!visited[j] && (u == -1 || dist[j] < dist[u])) u = j;

visited[u] = 1;

for(int v = 0; v < n; v++)

if(!visited[v] && graph[u][v] && dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
}

int main() {
cout << "Enter number of vertices: ";
 cin >> n;
cout << "Enter adjacency matrix (0 if no edge):\n";
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
cin >> graph[i][j];

int src;
cout << "Enter source vertex (0-indexed): ";
cin >> src;

dijkstra(src);

cout << "\nShortest distances from vertex " << src << ":\n";
for(int i = 0; i < n; i++)
cout << "To " << i << " : " << (dist[i] == INF ? -1 : dist[i]) << "\n";

return 0;
}
```

---

## CHIT 3B — Bellman-Ford Algorithm (Dynamic Programming)

```cpp
#include<iostream>
using namespace std;

#define INF 99999

struct Edge { int u, v, w; };

int main() {
int n, e;
cout << "Enter number of vertices and edges: ";
cin >> n >> e;

Edge edges[200];
cout << "Enter edges (u v weight):\n";
for(int i = 0; i < e; i++)
cin >> edges[i].u >> edges[i].v >> edges[i].w;

int src;
cout << "Enter source vertex: ";
cin >> src;

int dist[100];
for(int i = 0; i < n; i++) dist[i] = INF;
dist[src] = 0;

// Relax all edges n-1 times

for(int i = 0; i < n - 1; i++)
 for(int j = 0; j < e; j++)
if(dist[edges[j].u] != INF && dist[edges[j].u] + edges[j].w < dist[edges[j].v])
dist[edges[j].v] = dist[edges[j].u] + edges[j].w;

// Check for negative weight cycle

bool negCycle = false;
for(int j = 0; j < e; j++)
if(dist[edges[j].u] != INF && dist[edges[j].u] + edges[j].w < dist[edges[j].v])
negCycle = true;

if(negCycle) {
cout << "\nNegative weight cycle detected!\n";
} else {
cout << "\nShortest distances from " << src << ":\n";
for(int i = 0; i < n; i++)
cout << "To " << i << " : " << (dist[i] == INF ? -1 : dist[i]) << "\n";
}

return 0;
}
```

---

## CHIT 4A — Fractional Knapsack (Greedy)

```cpp
#include<iostream>
#include<algorithm>
using namespace std;

struct Item {
int weight, value;
double ratio;
};

bool cmp(Item a, Item b) { return [Link] > [Link]; }

int main() {
int n, W;
cout << "Enter number of items: ";
cin >> n;
cout << "Enter knapsack capacity: ";
cin >> W;

Item items[100];
cout << "Enter weight and value for each item:\n";
for(int i = 0; i < n; i++) {
cin >> items[i].weight >> items[i].value;
items[i].ratio = (double)items[i].value / items[i].weight;
}
 sort(items, items + n, cmp);

double totalValue = 0;
int rem = W;

cout << "\nItems selected:\n";

for(int i = 0; i < n && rem > 0; i++) {
if(items[i].weight <= rem) {
totalValue += items[i].value;
rem -= items[i].weight;
cout << "Full item: w=" << items[i].weight << " v=" << items[i].value << "\n";
} else {
double frac = (double)rem / items[i].weight;
totalValue += frac * items[i].value;
cout << "Fraction " << frac << " of item: w=" << items[i].weight << " v=" <<
items[i].value << "\n";
rem = 0;
}
}

cout << "\nMaximum value = " << totalValue << "\n";

return 0;
}
```

---

## CHIT 4B — 0/1 Knapsack (Dynamic Programming)

```cpp
#include<iostream>
using namespace std;

int main() {
int n, W;
cout << "Enter number of items: ";
cin >> n;
cout << "Enter knapsack capacity: ";
cin >> W;

int w[100], v[100];

cout << "Enter weights: ";
for(int i = 0; i < n; i++) cin >> w[i];
cout << "Enter values: ";
for(int i = 0; i < n; i++) cin >> v[i];

int dp[101][101] = {0};

for(int i = 1; i <= n; i++)

for(int j = 0; j <= W; j++) {
dp[i][j] = dp[i-1][j]; // don't take item i
if(w[i-1] <= j) // take item i if it fits
 dp[i][j] = max(dp[i][j], dp[i-1][j - w[i-1]] + v[i-1]);
}

cout << "\nMaximum value = " << dp[n][W] << "\n";

// Trace which items were selected

cout << "Items selected (1-indexed):\n";
int j = W;
for(int i = n; i >= 1; i--) {
if(dp[i][j] != dp[i-1][j]) {
cout << "Item " << i << " (w=" << w[i-1] << ", v=" << v[i-1] << ")\n";
j -= w[i-1];
}
}

return 0;
}
```

---

## CHIT 5 — Finding Maximum and Minimum (Divide & Conquer)

```cpp
#include<iostream>
using namespace std;

struct Pair { int mn, mx; };

Pair maxMin(int arr[], int l, int r) {

Pair res;

if(l == r) {
[Link] = [Link] = arr[l];
return res;
}
if(r - l == 1) {
[Link] = min(arr[l], arr[r]);
[Link] = max(arr[l], arr[r]);
return res;
}

int mid = (l + r) / 2;
Pair left = maxMin(arr, l, mid);
Pair right = maxMin(arr, mid + 1, r);

[Link] = min([Link], [Link]);

[Link] = max([Link], [Link]);
return res;
}

int main() {
 int n;
cout << "Enter number of elements: ";
cin >> n;
int arr[100];
cout << "Enter elements: ";
for(int i = 0; i < n; i++) cin >> arr[i];

Pair res = maxMin(arr, 0, n - 1);

cout << "\nMaximum = " << [Link] << "\n";
cout << "Minimum = " << [Link] << "\n";

return 0;
}
```

---

## CHIT 6A — Traveling Salesman Problem (Branch & Bound)

```cpp
#include<iostream>
#include<climits>
using namespace std;

int n;
int graph[10][10];
int finalCost;
int finalPath[10];
bool visited[10];

void tsp(int path[], int level, int curCost) {

if(level == n) {
// Try to return to start
if(graph[path[level - 1]][path[0]] > 0) {
int total = curCost + graph[path[level - 1]][path[0]];
if(total < finalCost) {
finalCost = total;
for(int i = 0; i < n; i++) finalPath[i] = path[i];
}
}
return;
}

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

if(!visited[i] && graph[path[level - 1]][i] > 0) {
int newCost = curCost + graph[path[level - 1]][i];
if(newCost < finalCost) { // Bounding: prune if already worse
path[level] = i;
visited[i] = true;
tsp(path, level + 1, newCost);
visited[i] = false;
}
 }
}
}

int main() {
cout << "Enter number of cities: ";
cin >> n;
cout << "Enter cost matrix (0 = no edge):\n";
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
cin >> graph[i][j];

fill(visited, visited + n, false);

finalCost = INT_MAX;
int path[10];
path[0] = 0;
visited[0] = true;

tsp(path, 1, 0);

if(finalCost == INT_MAX)
cout << "\nNo complete tour possible.\n";
else {
cout << "\nMinimum Cost = " << finalCost << "\n";
cout << "Tour: ";
for(int i = 0; i < n; i++) cout << finalPath[i] + 1 << " -> ";
cout << finalPath[0] + 1 << "\n";
}

return 0;
}
```

---

## CHIT 6B — 0/1 Knapsack (Branch & Bound)

```cpp
#include<iostream>
#include<algorithm>
using namespace std;

struct Item { int w, v; double ratio; };

bool cmp(Item a, Item b) { return [Link] > [Link]; }

int n, W, maxVal;
Item items[100];

// Upper bound using fractional relaxation

double upperBound(int level, int curW, int curV) {
double bound = curV;
 int rem = W - curW;
for(int i = level; i < n && rem > 0; i++) {
if(items[i].w <= rem) {
bound += items[i].v;
rem -= items[i].w;
} else {
bound += items[i].ratio * rem;
rem = 0;
}
}
return bound;
}

void solve(int level, int curW, int curV) {

if(level == n) {
maxVal = max(maxVal, curV);
return;
}

// Include item
if(curW + items[level].w <= W)
solve(level + 1, curW + items[level].w, curV + items[level].v);

// Exclude item — only if upper bound is promising

if(upperBound(level + 1, curW, curV) > maxVal)
solve(level + 1, curW, curV);
}

int main() {
cout << "Enter number of items: ";
cin >> n;
cout << "Enter capacity: ";
cin >> W;

cout << "Enter weight and value for each item:\n";

for(int i = 0; i < n; i++) {
cin >> items[i].w >> items[i].v;
items[i].ratio = (double)items[i].v / items[i].w;
}

sort(items, items + n, cmp); // Sort by ratio for better bounds

maxVal = 0;
solve(0, 0, 0);

cout << "\nMaximum value = " << maxVal << "\n";

return 0;
}
```

---

## CHIT 7A — Multistage Graph (Dynamic Programming)

```cpp
#include<iostream>
using namespace std;

#define INF 99999

int main() {
int n;
cout << "Enter total number of vertices: ";
cin >> n;

int cost[20][20];
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
cost[i][j] = INF;

int e;
cout << "Enter number of edges: ";
cin >> e;
cout << "Enter edges (from to cost):\n";
for(int i = 0; i < e; i++) {
int u, v, c;
cin >> u >> v >> c;
cost[u][v] = c;
}

int dist[20], next[20];

for(int i = 0; i < n; i++) { dist[i] = INF; next[i] = -1; }
dist[n - 1] = 0; // Sink has cost 0

// Process vertices from sink backwards

for(int i = n - 2; i >= 0; i--)
for(int j = i + 1; j < n; j++)
if(cost[i][j] != INF && dist[j] != INF)
if(cost[i][j] + dist[j] < dist[i]) {
dist[i] = cost[i][j] + dist[j];
next[i] = j;
}

cout << "\nMinimum cost from 0 to " << n - 1 << " = " << dist[0] << "\n";
cout << "Path: ";
int cur = 0;
while(cur != -1) {
cout << cur;
if(next[cur] != -1) cout << " -> ";
cur = next[cur];
}
cout << "\n";

return 0;
}
```

---

## CHIT 7B — 0/1 Knapsack (Backtracking)

```cpp
#include<iostream>
using namespace std;

int n, W;
int w[100], v[100];
int maxVal, curVal, curW;
int bestItems[100], curItems[100];

void backtrack(int level) {

if(level == n) {
if(curVal > maxVal) {
maxVal = curVal;
for(int i = 0; i < n; i++) bestItems[i] = curItems[i];
}
return;
}

// Include item
if(curW + w[level] <= W) {
curW += w[level];
curVal += v[level];
curItems[level] = 1;
backtrack(level + 1);
curW -= w[level];
curVal -= v[level];
}

// Exclude item
curItems[level] = 0;
backtrack(level + 1);
}

int main() {
cout << "Enter number of items: ";
cin >> n;
cout << "Enter capacity: ";
cin >> W;
cout << "Enter weights: ";
for(int i = 0; i < n; i++) cin >> w[i];
cout << "Enter values: ";
for(int i = 0; i < n; i++) cin >> v[i];

maxVal = 0; curVal = 0; curW = 0;

backtrack(0);
 cout << "\nMaximum value = " << maxVal << "\n";
cout << "Items selected (1-indexed):\n";
for(int i = 0; i < n; i++)
if(bestItems[i])
cout << "Item " << i + 1 << " (w=" << w[i] << ", v=" << v[i] << ")\n";

return 0;
}
```

---

## CHIT 8A — N-Queens Problem (Backtracking)

```cpp
#include<iostream>
using namespace std;

int n;
int board[20][20];
int solutionCount = 0;

bool isSafe(int row, int col) {

// Check column above
for(int i = 0; i < row; i++)
if(board[i][col]) return false;

// Check upper-left diagonal

for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
if(board[i][j]) return false;

// Check upper-right diagonal

for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++)
if(board[i][j]) return false;

return true;
}

void printBoard() {
cout << "\nSolution " << ++solutionCount << ":\n";
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++)
cout << (board[i][j] ? "Q " : ". ");
cout << "\n";
}
}

void solve(int row) {

if(row == n) { printBoard(); return; }

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

if(isSafe(row, col)) {
 board[row][col] = 1;
solve(row + 1);
board[row][col] = 0;
}
}
}

int main() {
cout << "Enter N: ";
cin >> n;

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

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

solve(0);

if(solutionCount == 0)
cout << "No solution exists for N = " << n << "\n";
else
cout << "\nTotal solutions = " << solutionCount << "\n";

return 0;
}
```

---

## CHIT 8B — Vertex Cover (Approximate Algorithm)

```cpp
#include<iostream>
using namespace std;

int main() {
int v, e;
cout << "Enter number of vertices and edges: ";
cin >> v >> e;

int edges[200][2];
cout << "Enter edges (u v):\n";
for(int i = 0; i < e; i++)
cin >> edges[i][0] >> edges[i][1];

bool inCover[100] = {false};

bool edgeDone[200] = {false};

// Greedy: pick any uncovered edge, add both endpoints to cover

for(int i = 0; i < e; i++) {
if(!edgeDone[i]) {
int u = edges[i][0], v2 = edges[i][1];
inCover[u] = true;
 inCover[v2] = true;

// Mark all edges incident to u or v2 as covered

for(int j = 0; j < e; j++)
if(edges[j][0] == u || edges[j][1] == u ||
edges[j][0] == v2 || edges[j][1] == v2)
edgeDone[j] = true;
}
}

cout << "\nVertex Cover: { ";

int size = 0;
for(int i = 0; i < v; i++)
if(inCover[i]) { cout << i << " "; size++; }
cout << "}\n";
cout << "Size of Vertex Cover = " << size << "\n";

return 0;
}
```

---