ALGORITHM/CODE QUESTIONS:
1)Recursive quick sort:
int partition(vector<int>& arr, int start, int end) {
int pivot = arr[end];
int idx = start - 1;
for (int j = start; j < end; j++) {
if (arr[j] < pivot) {
idx++;
swap(arr[idx], arr[j]);
}
}
swap(arr[idx + 1], arr[end]);
return idx + 1;
}
void quickSort(vector<int>& arr, int start, int end) {
if (start < end) {
int pivotIdx = partition(arr, start, end);
quickSort(arr, start, pivotIdx - 1);
quickSort(arr, pivotIdx + 1, end);
}
}
2)Recursive heap sort:
void heapify(vector<int>& arr, int n, int idx) {
int largest = idx, left = 2 * idx + 1, right = 2 * idx + 2;
if (left < n && arr[left] > arr[largest]) largest = left;
if (right < n && arr[right] > arr[largest]) largest = right;
if (largest != idx) {
swap(arr[idx], arr[largest]);
heapify(arr, n, largest);
}
}
void buildMaxHeap(vector<int>& arr, int n, int idx) {
if (idx >= 0) {
heapify(arr, n, idx);
buildMaxHeap(arr, n, idx - 1);
}
}
void heapSort(vector<int>& arr, int n) {
buildMaxHeap(arr, n, n / 2 - 1);
if (n > 1) {
swap(arr[0], arr[n - 1]);
heapSort(arr, n - 1);
}
}
3)write the algorithm for matrix chain multiplication and
compute its time complexity
int matrixChainOrder(vector<int>& dims, int i, int j, vector<vector<int>>&
dp) {
if (i == j) return 0;
if (dp[i][j] != -1) return dp[i][j];
int minCost = INT_MAX;
for (int k = i; k < j; k++) {
int cost = matrixChainOrder(dims, i, k, dp) +
matrixChainOrder(dims, k + 1, j, dp) + dims[i - 1] * dims[k] * dims[j];
minCost = min(minCost, cost);
}
return dp[i][j] = minCost;
}
int matrixChainMultiplication(vector<int>& dims) {
int n = dims.size();
vector<vector<int>> dp(n, vector<int>(n, -1));
return matrixChainOrder(dims, 1, n - 1, dp);
}
The time complexity of the recursive solution with memoization is O(n^3)
1.O(n^2)subproblems.
2.Each subproblem iterates over O(n)O(n)O(n) splits to nd the
minimum.
fi
4. write the algorithm for graph coloring problem and nd its
time complexity
bool isSafe(int node, vector<vector<int>>& adjMatrix, vector<int>&
colors, int color) {
for (int neighbor = 0; neighbor < adjMatrix.size(); neighbor++) {
if (adjMatrix[node][neighbor] == 1 && colors[neighbor] == color)
return false;
}
return true;
}
bool graphColoringUtil(vector<vector<int>>& adjMatrix, int maxColors,
vector<int>& colors, int node) {
if (node == adjMatrix.size()) return true;
for (int color = 1; color <= maxColors; color++) {
if (isSafe(node, adjMatrix, colors, color)) {
colors[node] = color;
if (graphColoringUtil(adjMatrix, maxColors, colors, node + 1))
return true;
colors[node] = 0;
}
}
return false;
}
bool graphColoring(vector<vector<int>>& adjMatrix, int maxColors) {
vector<int> colors(adjMatrix.size(), 0);
return graphColoringUtil(adjMatrix, maxColors, colors, 0);
}
The time complexity of this algorithm is O(m^n⋅n^2), where:
1. n is the number of vertices in the graph.
2. m is the number of colors.
5.write the algorithm for 01 ksp using backtracking and nd
its time complexity in the
best and worst case.
fi
fi
int knapsackRecursion(vector<int>& weights, vector<int>& values, int
capacity, int n, int idx, int currentValue, int currentWeight, int& maxValue)
{
if (idx == n) {
if (currentWeight <= capacity) {
maxValue = max(maxValue, currentValue);
}
return maxValue;
}
knapsackRecursion(weights, values, capacity, n, idx + 1,
currentValue, currentWeight, maxValue);
if (currentWeight + weights[idx] <= capacity) {
knapsackRecursion(weights, values, capacity, n, idx + 1,
currentValue + values[idx], currentWeight + weights[idx], maxValue);
}
return maxValue;
}
int knapsack01(vector<int>& weights, vector<int>& values, int capacity)
{
int maxValue = 0;
return knapsackRecursion(weights, values, capacity, weights.size(), 0,
0, 0, maxValue);
}
6)Write an algorithm for 01 ksp using branch and bound technique and
nd its time complexity
struct KnapsackNode {
int level, value, weight, bound;
};
int calculateBound(KnapsackNode node, int n, int W, vector<int>&
weights, vector<int>& values) {
if (node.weight >= W) return 0;
int boundVal = node.value, j = node.level + 1, totalWeight =
node.weight;
while (j < n && totalWeight + weights[j] <= W) {
totalWeight += weights[j];
boundVal += values[j];
fi
j++;
}
if (j < n) boundVal += (W - totalWeight) * values[j] / weights[j];
return boundVal;
}
int knapsackBB(int capacity, vector<int>& weights, vector<int>& values)
{
int n = weights.size(), maxValue = 0;
priority_queue<KnapsackNode> pq;
KnapsackNode node, childNode;
node.level = -1, node.value = node.weight = 0, node.bound =
calculateBound(node, n, capacity, weights, values);
pq.push(node);
while (!pq.empty()) {
node = pq.top(); pq.pop();
if (node.bound > maxValue) {
childNode.level = node.level + 1;
childNode.weight = node.weight + weights[childNode.level];
childNode.value = node.value + values[childNode.level];
if (childNode.weight <= capacity && childNode.value >
maxValue) maxValue = childNode.value;
childNode.bound = calculateBound(childNode, n, capacity,
weights, values);
if (childNode.bound > maxValue) pq.push(childNode);
childNode.weight = node.weight;
childNode.value = node.value;
childNode.bound = calculateBound(childNode, n, capacity,
weights, values);
if (childNode.bound > maxValue) pq.push(childNode);
}
}
return maxValue;
}
Time Complexity
1) Worst Case: O(2^n), similar to backtracking, as all nodes in the
decision tree might
be explored.
2) Best Case: O(klogk), where k is the number of nodes explored. This
happens when
effective bounding reduces the exploration space signi cantly.
7)write the algorithm for tsp using branch and bound and
compute its time complexity
in best and worst case.
struct Node {
int level, cost, bound;
vector<int> path;
};
int calculateBound(Node u, vector<vector<int>>& graph, int itemCount) {
int bound = u.cost, minCost;
vector<bool> visited(itemCount, false);
for (int i : u.path) visited[i] = true;
for (int i = 0; i < itemCount; i++) {
if (!visited[i]) {
minCost = INT_MAX;
for (int j = 0; j < itemCount; j++) {
if (!visited[j] && i != j) minCost = min(minCost, graph[i][j]);
}
bound += minCost;
}
}
return bound;
}
int tspBB(vector<vector<int>>& graph) {
int itemCount = graph.size();
priority_queue<pair<int, Node>, vector<pair<int, Node>>, greater<>>
pq;
Node u, v;
u.level = 0, u.cost = 0, u.bound = 0;
u.path.push_back(0);
u.bound = calculateBound(u, graph, itemCount);
pq.push({u.bound, u});
fi
int minCost = INT_MAX;
while (!pq.empty()) {
u = pq.top().second;
pq.pop();
if (u.bound >= minCost) continue;
if (u.level == itemCount - 1) {
int nalCost = u.cost + graph[u.path.back()][u.path[0]];
if ( nalCost < minCost) minCost = nalCost;
continue;
}
for (int i = 0; i < itemCount; i++) {
if ( nd(u.path.begin(), u.path.end(), i) == u.path.end()) {
v.level = u.level + 1;
v.cost = u.cost + graph[u.path.back()][i];
v.path = u.path;
v.path.push_back(i);
v.bound = calculateBound(v, graph, itemCount);
if (v.bound < minCost) pq.push({v.bound, v});
}
}
}
return minCost;
}
Time Complexity:
1) Worst Case: O(n!), as all permutations of cities may be explored.
2) Best Case: O(klogk), where k is the number of nodes processed.
Effective pruning
reduces the search space, leading to fewer nodes explored.
8)algorithm for Dijkstra’s shortest path using a Fibonacci
heap:
fi
fi
fi
fi
void dijkstraFibonacciHeap(vector<vector<int>>& adjMatrix, int
startVertex, int numVertices) {
vector<int> distances(numVertices, INT_MAX);
distances[startVertex] = 0;
FibonacciHeap fh;
fh.insert(startVertex, 0);
while (!fh.isEmpty()) {
int currentVertex = fh.extractMin();
for (int neighbor = 0; neighbor < numVertices; neighbor++) {
if (adjMatrix[currentVertex][neighbor] != 0) {
int newDist = distances[currentVertex] +
adjMatrix[currentVertex][neighbor];
if (newDist < distances[neighbor]) {
distances[neighbor] = newDist;
fh.decreaseKey(neighbor, newDist);
}
}
}
}
for (int i = 0; i < numVertices; i++) {
cout << "Shortest distance from " << startVertex << " to " << i << ": "
<< distances[i] << endl;
}
}
● Let n be the number of vertices in the graph.
● Create a Fibonacci heap to manage the priority queue of vertices.
● Set the distance for all vertices as in nity except the source vertex,
which is set to 0.
● Insert all vertices into the Fibonacci heap with their respective
distances.
Main Loop (Processing the Fibonacci heap):
While the Fibonacci heap is not empty:
● Extract the vertex uuu with the minimum distance from the Fibonacci
heap.
● For each neighbour vvv of uuu:
fi
● If the distance from the source to vvv through uuu is less than the
current
distance of vvv.Update the distance of vvv to this new smaller
value.Decrease
the key of vvv in the Fibonacci heap to re ect the updated distance.
Terminate:
● Once the heap is empty, the algorithm terminates. The shortest
distances from the
source to all other vertices are now available.
9)Implement dijkstra using normal queue:
void dijkstraNormalQueue(vector<vector<int>>& adjMatrix, int
startVertex, int numVertices) {
vector<int> distances(numVertices, INT_MAX);
distances[startVertex] = 0;
queue<int> processingQueue;
processingQueue.push(startVertex);
while (!processingQueue.empty()) {
int currentVertex = processingQueue.front();
processingQueue.pop();
for (int neighbor = 0; neighbor < numVertices; neighbor++) {
if (adjMatrix[currentVertex][neighbor] != 0) {
int newDist = distances[currentVertex] +
adjMatrix[currentVertex][neighbor];
if (newDist < distances[neighbor]) {
distances[neighbor] = newDist;
processingQueue.push(neighbor);
}
}
}
}
for (int i = 0; i < numVertices; i++) {
cout << "Shortest distance from " << startVertex << " to " << i << ": "
<< distances[i] << endl;
fl
}
}
