## Shortcut to seniority

##### Home

Go to main page

##### Section level: Junior

A journey into the programming realm

##### Section level: Intermediate

The point of no return

##### Section level: Senior

Leaping into the unknown

You are not allowed to print this document.

Go to main page

A journey into the programming realm

The point of no return

Leaping into the unknown

## Chapter warning

This chapter will contain some algorithms that are usually learned in school.

It is great if you're able to follow the problem and the solution, but if not, do not discourage yourself!

Algorithms are great for exposing you to different problem-solving techniques. However, you will not use them in your everyday programming, and if you actually do need one, you can always look them up on the internet.

Therefore, it's a good idea to read this chapter, but if you are stuck or simply get bored, feel free to go directly to Chapter 3 and come back later on.

Problem statementA thief is robbing a house and can carry into his knapsack a maximal weight W.

There are n available items, each of them with their weight and profit of selecting that item.

Which items should the thief take?

The 0-1 Knapsack problem is similar to the Fractional Knapsack problem that we solved using Greedy.

The difference between them is that in here, items cannot be broken – the item should be taken as a whole or not taken at all.

This problem cannot be always optimally solved through Greedy.

Assuming the capacity of the knapsack is 30, and we can choose from the following items:

Item | A | B | C |
---|---|---|---|

Profit | 25 | 20 | 15 |

Weight | 25 | 20 | 10 |

The greedy approach will get the most profitable first (A) , and we will be able to take only one item. The profit for this item will be 25.

We can see that the optimal solution here would be to take B and C, reaching a profit of 35 and entirely filling the knapsack. Therefore, we need to find ourselves another solution.

The easiest way for us would be to consider all subsets of items and then calculate their weight and value. Then, out of all subsets, we can pick the subset with the maximum value.

Each item will be either included in the optimal set, or not. Therefore, the maximum value is the maximum between two values:

- Excluding nth item: Maximum value obtained by n-1 items and W weight
- Including nth item: Value of nth item plus the maximum value obtained by n-1 items and W, minus weight of that item

The problem with this implementation is that it computes the same subproblems again and again.

Overlapping subproblems is a property of Dynamic Programming, So, let’s try to use such approach now.

` ````
int max(int a, int b) { return (a > b) ? a : b; }
int knapsack(int capacity, int weights[], int values[], int totalItems) {
// No more items / No capacity left - getting out
if (totalItems == 0 || capacity == 0) return 0;
// If the weight including this item exceeds capacity -> exclude it
if (weights[totalItems - 1] > capacity) {
return knapsack(capacity, weights, values, totalItems - 1);
}
else {
// We can either add the item, or not. So we recursively call the function
// with and without the item, and we get the maximum out of these two
int newCapacity = capacity - weights[totalItems - 1];
int valueNewCapacity = knapsack(newCapacity, weights, values, totalItems - 1);
int valueWithItem = values[totalItems-1] + valueNewCapacity;
int valueWithoutItem = knapsack(capacity, weights, values, totalItems - 1);
return max(valueWithItem, valueWithoutItem);
}
}
int main() {
int values[] = { 400, 100, 120, 90, 100, 200 };
int weights[] = { 10, 15, 5, 10, 10, 10 };
int capacity = 50;
int totalItems = 6;
cout << knapsack(capacity, weights, values, totalItems);
return 0;
}
```

Index | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|

Value | 400 | 100 | 120 | 90 | 100 | 200 |

Weight | 10 | 15 | 5 | 10 | 10 | 10 |

Capacity = 50, totalItems = 6

knapsack(50, weights, values, 6);

- Line 7 = not the case
- Line 10 = 10 > 50 - not the case

=> Max(200 + knapsack(50-10, weights, values, 5), knapsack(50, weights, values, 5))

So we return the maximum between having the item and not having the item included in our solution.

**1st subproblem – index 5 added into the knapsack**

knapsack(40, weights, values, 5)

- Line 7 = not the case
- Line 10 = 10 > 40 – not the case

=> Max(100 + knapsack(40-10, weights, values, 4), knapsack(40, weights, values, 4))

**2nd subproblem – index 5 not added into the knapsack**

knapsack(50, weights, values, 5):

- Line 7 = not the case
- Line 10 = 10 > 50 - not the case

=> Max(100 + knapsack(50-10, weights, values, 4), knapsack(50, weights, values, 4))

The dynamic programming implementation of the 0-1 Knapsack problem is a bit more complicated. It relies on having a 2-dimensional array (matrix), where the rows are the values from 1 to the bag capacity, and the columns are the values from 1 to the number of items (choices) we have. The value in the array is calculated based on the maximum profit we can make that relies on the choices we have at one moment. If the capacity is too small for any item, then the value in the solution matrix is 0.

If we don’t have any items to choose from, the value in the solution matrix is also 0.

In case we have only one item to pick from – the weight of the item will be added into our matrix if the bag capacity allows us to take that item.

When there are multiple items involved, we need to see whether we can pick all of them. If not, then we’ll have to see which item we’d benefit more from.
These values will be taken by using the maximum between either picking the item, or not.

If the item is picked, then we look into our solution table for the profit we could have for when the bag capacity is reduced by the weight of the item we chose to pick. Otherwise, we look into our solution table for the profit we had when the item was not chosen.

Let’s see some code to make it more clear.

` ````
int max(int a, int b) { return (a > b) ? a : b; }
int knapsack(int capacity, int weights[], int values[], int totalItems) {
int **Table = new int*[totalItems + 1];
for (int i = 0; i < totalItems + 1; ++i)
Table[i] = new int[capacity + 1];
for (int i = 0; i <= totalItems; i++) {
for (int w = 0; w <= capacity; w++) {
if (i == 0 || w == 0)
Table[i][w] = 0;
else if (weights[i - 1] <= w)
Table[i][w] = max(
values[i - 1] + Table[i - 1][w - weights[i - 1]],
Table[i - 1][w]
);
else
Table[i][w] = Table[i - 1][w];
}
}
return Table[totalItems][capacity];
}
int main() {
int values[] = { 400, 100, 120, 90, 100, 200 };
int weights[] = { 10, 15, 5, 10, 10, 10 };
int capacity = 50;
int totalItems = 6;
cout << knapsack(capacity, weights, values, totalItems);
return 0;
}
```

The main() function is at line 25, and further down we initialize a bunch of data: Values per object, weights of each object, the knapsack capacity, and the number of items we can add in it.

The function is called at line 30, and the implementation for it is at line 3.

Line 1 introduces a function which returns the max of two values, and we’ll use it further into our code. In lines 4-6, we allocate a matrix (2 dimensional array), with the size based on the items and the knapsack capacity.

The Table is built in a bottom up manner.

The value of first row and first column is set to 0 (Lines 10-11).

For all the other rows and columns (where each row refer to an item, and each column refer to the capacity):

**If the weight of the object is smaller than the capacity (Line 12):**The value is the maximum value we can get between taking that object or not (Lines 13-16).**Otherwise:**The value is the same as the value for the previous iteration (Line 18)

The very first thing is to draw a matrix (Capacity * Items).

So we’ll have a matrix with 6 rows and 50 columns. The row and column with index 0 is set to 0.

- If we have a bag with 0 value => we cannot select any item.
- If we don’t have any items => we cannot pick any item.

For value[m][n] => m is the item taken, n is the capacity of the bag.

If m=1, n=1:

- The capacity of the bag is 1
- We check if we can take the first item
- The capacity of first item is bigger, so we execute line 18

IF m=1, n=10:

- The capacity of the bag is 10
- We check if we can take the first item
- The capacity of the item is the same as the value of the bag, so we can take the item (execute line 14).

Therefore, we write the profit of the item in the Table[m][n].

For all the values in the first row:

- The capacity of the bag goes from 10 to 50
- We check if we can take the first item
- We have only one item available, and the capacity of the item is 10, so we will pick that one in all cases (execute line 13)

Therefore, in Table[1][n], we will have value 0 for n <= weights[0], and the value of values[0] for n >= weights[0]

When we advance with the rows, we will have more than 1 item to choose from.

We will set 0 in the matrix until the capacity of the bag is bigger or equal to the weight of any of those items. If we have to choose, we calculate the profit (line 13-15).

If we have item with weight {1,2}, value {3,4}, and the capacity of bag is 2: We can add either first or second item.

But how do we choose which one?

If we select item 1, we take profit 3. If we select item 2, we have profit 4. In the code, the logic is:

Maximum between:

- Value of item (3) + Value in the table for that row, but where the column is the bag capacity minus the weight of the item (2-1),
- Value of the previous item for that weight (when we don’t select that one – we take the maximum profit we can have without that item)

Problem statement

Bellman-Ford algorithmis yet another algorithm for finding the shortest path distance. Unlike Dijkstra’s, Bellman-Ford works for graphs that contain negative weight edges.In case you forgot what type of problem Shortest path distance solves, it finds the shortest path from a source node to all other vertices in a given graph.

The algorithm uses Dynamic Programming technique to calculate shortest path by using the bottom-up manner. First, it calculates the shortest distance between two neighbours (one edge in-between).

Afterwards, it calculates the shortest distance between vertices that have two edges in-between, and so on.

The algorithm maintains an array of distances which correspond to all the vertices in the graph. The value is defaulted to infinite (highest possible value), while the item which corresponds to our initial source is set to 0. (the distance between a node and itself).

After the distances vector has been set, we iterate through the vertices in the graph, and update the distances based on the algorithm. After we iterated through all the vertices, we check whether we have a negative weight cycle in the graph.

The algorithm says that you go out relaxing all edges for (N-1) times, where N = number of vertices.

Relaxation means that between a pair of vertices (u,v) which have an edge between them:

`If distance[u] + C(u,v) < distance[v], `

then Distance[v] = distance[u] + C(u, v),

where C(u,v) is cost of the edge between u and v.

- Source = A
- Number of vertices = 4
- Number of relaxation steps = (4-1) = 3
- Set edges distance to infinite, except the source itself, where we set 0.

A | B | C | D |
---|---|---|---|

0 | INF | INF | INF |

Edges: (A, B), (A, D), (D, C), (C, B)

We can see the values of the distance tabel below

A | B | C | D |
---|---|---|---|

0 | INF | INF | INF |

**Edge (A, B)**

- Distance[A] = 0
- C(A,B) = 3
- Distance[B] = INF

0 + 3 < INF => Distance[B] = 3

A | B | C | D |
---|---|---|---|

0 | 3 | INF | INF |

**Edge (A, D)**

- Distance[A] = 0
- C(A,D) = 4
- Distance[D] = INF

0 + 4 < INF => Distance[D] = 4

A | B | C | D |
---|---|---|---|

0 | 3 | INF | 4 |

**Edge (D, C)**

- Distance[D] = 4
- C(D, C) = 5
- Distance[C] = INF

4 +5 < INF => Distance[C] = 9

A | B | C | D |
---|---|---|---|

0 | 3 | 9 | 4 |

**Edge (C, B)**

- Distance[C] = 9
- C(C, B) = -10
- Distance[B] = 3

9-10 < 3 => Distance[B] = -1

A | B | C | D |
---|---|---|---|

0 | -1 | 9 | 4 |

We can see the values of the distance tabel below

A | B | C | D |
---|---|---|---|

0 | -1 | 9 | 4 |

**Edge (A, B)**

- Distance[A] = 0
- C(A,B) = 3
- Distance[B] = -1

0 + 3 < -1 => No, stick with -1

**Edge (A, D)**

- Distance[A] = 0
- C(A,D) = 4
- Distance[D] = 4

0 + 4 < 4 ? => No, stick with 4

**Edge (D, C)**

- Distance[D] = 4
- C(D, C) = 5
- Distance[C] = 9

4 +5 < 9 => No, stick with 9

**Edge (C, B)**

- Distance[C] = 9
- C(C, B) = -10
- Distance[B] = -1

9-10 < -1 => No, stick with -1

**No change from previous relaxation, so the answers are final.**

` ````
int Vertices = 5;
struct Edge {
int source;
int destination;
int weight;
};
class Graph {
public:
using GraphMap = vector<Edge>;
void addEdge(int from, int to, int cost) {
edges.push_back({ from, to, cost });
}
const GraphMap& getEdges() const { return edges; }
private:
GraphMap edges;
};
void display(const vector<int>& distances) {
std::cout << "Vertex - Distance from Source";
for (int i = 0; i < distances.size(); ++i) {
cout << i << " - " << distances[i];
}
}
int main() {
Graph graph;
graph.addEdge(0, 1, -1);
graph.addEdge(0, 2, 4);
graph.addEdge(1, 2, 3);
graph.addEdge(1, 3, 2);
graph.addEdge(1, 4, 2);
graph.addEdge(3, 2, 5);
graph.addEdge(3, 1, 1);
graph.addEdge(4, 3, -3);
BellmanFord(graph.getEdges(), 0);
return 0;
}
```

The main() function starts on line 27.

We have an integer that defines the number of our vertices (Line 1).

We create a graph and add a few edges onto it (Lines 28-36). If we check the implementation of the function (Lines 12-13), we see that the edges are pushed into a vector.

The edge structure contains both the source and the destination (Lines 3-7), therefore we can assume that we are talking about a directed graph.

The algorithm is called on line 38, and the implementation of it can be seen below. The function receives the edges and the source vertex, which in our case will be 0.

` ````
void BellmanFord(const Graph::GraphMap& graph, int source) {
const int MAX_INT = std::numeric_limits<int>::max();
std::vector<int> distances(Vertices, MAX_INT);
distances[source] = 0;
// Iterate through all edges multiple times
// and update the distances between vertices
for (int i = 1; i < Vertices - 1; ++i) {
for (const auto& edge : graph) {
int src = edge.source;
int dst = edge.destination;
int cost = edge.weight;
if (distances[src] != MAX_INT && distances[src] + cost < distances[dst])
distances[dst] = distances[src] + cost;
}
}
// final loop for negative cycle detection
for (const auto& edge : graph) {
int src = edge.source;
int dst = edge.destination;
int cost = edge.weight;
if (distances[src] != MAX_INT && distances[src] + cost < distances[dst])
cout << "Negative cycle";
}
display(distances);
}
```

We define MAX_INT as a constant for our highest possible integer (Line 2). This will be used as an initial value for our distances vector, (Line 3), in order to further calculate the smallest distance.

The distances vector has a size of Vertices, so each vertex will have assigned a distance – which is the distance required to reach that vertex from the starting point.

The distance from source to itself is set to 0 (Line 4).

In order to do the relaxation process, we need to iterate through each edge from the graph multiple times (the number of vertices in the graph minus one).

In line 8 we start the iteration process.

For each edge in the graph (Line 8):

- If the distance from starting point to the source node is already known AND
- If the distance from our source to this source, plus the cost it takes to reach the destination node, is smaller then the distance we already have from starting point to the destination node (Line 13):
- Then: We update the distance from starting point to destination node to be the distance to source node plus the cost.

Let’s give an example.

Node A is the starting point.

The cost of reaching point B from A is 10. (A-> B = 10)

The cost of reaching point C from B is 2 (B -> C = 2)

The initial cost of reaching point C from A is 30 (A -> C = 30)

If we go from A to B, it will cost 10. If we go from B to C, it will cost 2 more. Therefore, we can reach C by going A -> B -> C, with the total cost of 12. Our current route is direct (A->C) and it costs 30. So let’s update the distance required to reach C, to be 12.

We need to apply the same logic multiple times (the total number of times is the number of vertices), because a change in one step will propagate to the next ones. We will use that updated distance to calculate the distance to other vertices from the graph.

This solution needs to be understood this way:

The condition in line 22 requires that the distance from source point to the node should be different than MAX_INT.

MAX_INT is the default value for our distances vector (except source).

Therefore, the only edges that will pass the condition are the nodes that are directly connected to our source node.

In the next step, we already know the distance to reach the neighbours, and we can use that to get the smallest distance required to reach the 2nd level neighbours (direct connections of direct connections of source node).

By doing this over and over, we will eventually find the smallest distance from our source node to its furthest connection.

The lines 18-24 are the same as the ones above, and they are there to check for negative cycles.

If we already know the value of smallest distances, but we check again and we get different results, it means we have a cycle in the graph that is negative.

**Let’s give an example.**

{A-> B = 2}, { B-> C = 3}, {C-> A = - 10}.

Going from A to A will take 2+3-10 = -5 distance. Initially we started with 0 distance from A, now we are in the same point with -5.

If we do another loop (A-> B-> C -> A), we will get -5 + 2 + 3 -10 = -10. The distance was again updated, although we haven’t changed anything.

This will go into an infinite loop, because the distance is updated everytime we do another loop.

The travelling salesman problem (TSP)asks the following question: “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the starting point?”

First step is to choose a node to be our starting/ending point.

Afterwards, we will generate all (n-1)! permutations of cities, where n is the number of cities.

While doing so, we calculate the cost of every permutation and keep track of the minimum cost.

In the end, we return the permutation we have stored, which will be the one with the minimum travelling cost.

Assuming we have the following graph: We pick 1 as start / end point.

We generate all possible permutations which have 1 as starting and ending point

- 1-2-3-4-1 => cost 95
- 1-2-4-3-1 => cost 80
- 1-3-2-4-1 => cost 95
- 1-3-4-2-1 => cost 80
- 1-4-2-3-1 => cost 95
- 1-4-3-2-1 => cost 95

=> 80 (1-2-4-3-1 / 1-3-4-2-1)

` ````
int starting_point = 0;
int TravellingSalesman(vector<vector<int>>& graph, int start) {
vector<int> vertex;
for (int i = 0; i < graph.size(); i++)
if (i != start)
vertex.push_back(i);
int minimum_path = std::numeric_limits<int>::max();
do {
int current_permutation_weight = 0;
int k = start;
for (int i = 0; i < vertex.size(); i++) {
current_permutation_weight += graph[k][vertex[i]];
k = vertex[i];
}
current_permutation_weight += graph[k][start];
minimum_path = std::min(minimum_path, current_permutation_weight);
} while (std::next_permutation(vertex.begin(), vertex.end()));
return minimum_path;
}
int main() {
vector<vector<int>> graph = {
{ 0, 10, 15, 20 },
{ 10, 0, 35, 25 },
{ 15, 35, 0, 30 },
{ 20, 25, 30, 0 }
};
cout << TravellingSalesman(graph, starting_point);
return 0;
}
```

The main function, at line 25, will be initially called.

We have a graph which contains the weights from a node x to a node y, where x and y are the rows and columns of the matrix.

For example, we can see that graph[0][4] is 20, which is the weight from node 0 to 4.

We select 0 as starting point in our graph, and we call the TravellingSalesman function.

This function creates a vector and copies all the vertices except our starting point.

This means that, for the nodes {0,1,2,3,4}, the vector will have the values {1,2,3,4}.

We initialize minimum_path with maximum possible value, because we want to overwrite it when we find a path that is less than that.

At the end of the function, we return the minimum path.

Before that, we have the big do – while, which goes on until we have a next permutation for our vector.

This means that we will permute the vector, and its values will change like this:

{1,2,3,4} -> {1,3,2,4} -> {1,4,2,3} …

{2,1,3,4} -> {2,3,1,4} -> {2,3,4,1} …

And so on.

In the do-while, what we’re gonna do is:

- Set current_permutation_weight to 0. Meaning that this will reset for each permutation
- We set k at starting point, and we add to the current_permutation_weight, the value of graph[k][ vertex[i] ]
- Since k is the starting point, we add graph[0] [1], graph[0][2], graph[0][3], and graph[0][4].
- At the end of the for, we set K to vertex[i], so in the end it will have the value 4.
- Next, we add to the sum graph[k][start], so graph[4][0] => we return back to the source.

At the end, before we go on with the next permutation, we check whether the value of current_permutation_weight is lower than what we have right now, and we overwrite it if so.

Given two sequences, find the length of the longest subsequence that is present in both of them.

A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous.

Let's take an example.

For the string “aeiou”, the following are valid subsequences: “ae”, “aio”, “aiu”, “eu”, “eiu” etc.

Given two strings, one string of length m and one string of length n, we will use a matrix with m+1 rows and n+1 columns, to keep the value of common subsequences.

The first row and first column is initially set to 0.

Assuming we have the first string S1 = “ABCDE”, and the second string S2 = “BAD”.

We can observe the LCS will be of size 2 (“BD”).

Let’s see how we can reach this value.

**(S1 = ABCDE)**

String | A | B | C | D | E |
---|---|---|---|---|---|

Index | 1 | 2 | 3 | 4 | 5 |

**(S2 = BDE)**

String | B | D | E |
---|---|---|---|

Index | 1 | 2 | 3 |

We see that I’ve started the index from 1 and not from 0 – that’s because the first row and first column will have their values defaulted to 0.

The algorithm is as follows:

- If the characters in both strings match, we fill the matrix of their position to be 1 + the diagonal value of previous characters.
- If the characters do not match, we fill the matrix of their position to be the maximum value between the value from the left and from the top position.

Let’s make this clear with some drawing.

Let’s define a table and set the first rows and columns to 0.

# | A | B | C | D | E | |
---|---|---|---|---|---|---|

# | 0 | 0 | 0 | 0 | 0 | 0 |

B | 0 | |||||

D | 0 | |||||

E | 0 |

Let’s compare S1[1] and S2[1].

A is different than B => do not match, so we take the maximum value between top and left.

S1[1] != S2[1] =>grid[1][1] = max ( grid[0][1], grid[1][0] )

= max (0,0)

= 0

# | A | B | C | D | E | |
---|---|---|---|---|---|---|

# | 0 | 0 | 0 | 0 | 0 | 0 |

B | 0 | 0 | ||||

D | 0 | |||||

E | 0 |

Let’s compare S1[2] and S2[1].

B is the same as B => they match, so we increment 1 to the value of the diagonal.

S1[2] == S2[1] =>

grid[2][1] = 1+ grid[2-1][1-1]

= 1 + 0

= 1

# | A | B | C | D | E | |
---|---|---|---|---|---|---|

# | 0 | 0 | 0 | 0 | 0 | 0 |

B | 0 | 0 | 1 | |||

D | 0 | |||||

E | 0 |

When we compare the remaining entries, we see that they are different characters, so we fill them with max between left and top.

On the left side we have 1, while on the top we have 0, so we fill the remaining entries with 1.

What is that telling us, is that between the strings “ABCDE” and the string “B” we have maximum a subsequence of 1.

Now, we continue for the next digit.

# | A | B | C | D | E | |
---|---|---|---|---|---|---|

# | 0 | 0 | 0 | 0 | 0 | 0 |

B | 0 | 0 | 1 | 1 | 1 | 1 |

D | 0 | |||||

E | 0 |

S1[1] != S2[1] =>

Grid[1][1] = max ( grid[1][0], grid[0][1])

= 0

# | A | B | C | D | E | |
---|---|---|---|---|---|---|

# | 0 | 0 | 0 | 0 | 0 | 0 |

B | 0 | 0 | 1 | 1 | 1 | 1 |

D | 0 | 0 | ||||

E | 0 |

S1[2] != S2[2] =>

Grid[2][2] = max ( grid[2,1], grid[1][2] ) = 1

Why we suddenly have 1 ?

Because although B != D, we already had a subsequence on the top, meaning that:

AB and B have a substring of 1

A and BD have a substring of 0

AB and BD have a substring of 1

# | A | B | C | D | E | |
---|---|---|---|---|---|---|

# | 0 | 0 | 0 | 0 | 0 | 0 |

B | 0 | 0 | 1 | 1 | 1 | 1 |

D | 0 | 0 | 1 | |||

E | 0 |

D and C differ, so we set in the grid the max value between 1 and 1 => 1

# | A | B | C | D | E | |
---|---|---|---|---|---|---|

# | 0 | 0 | 0 | 0 | 0 | 0 |

B | 0 | 0 | 1 | 1 | 1 | 1 |

D | 0 | 0 | 1 | 1 | ||

E | 0 |

D and D are the same character, so we increment the value we had on the diagonal.

# | A | B | C | D | E | |
---|---|---|---|---|---|---|

# | 0 | 0 | 0 | 0 | 0 | 0 |

B | 0 | 0 | 1 | 1 | 1 | 1 |

D | 0 | 0 | 1 | 1 | 2 | |

E | 0 |

D and E differ, so we take the maximum between 2 and 1 => we write 2 in the grid.

That means:

ABCDE and B have a subsequence of 1

ABCD and BD have a subsequence of 2

ABCDE and BD have a subsequence of 2

# | A | B | C | D | E | |
---|---|---|---|---|---|---|

# | 0 | 0 | 0 | 0 | 0 | 0 |

B | 0 | 0 | 1 | 1 | 1 | 1 |

D | 0 | 0 | 1 | 1 | 2 | 2 |

E | 0 |

…And so on

# | A | B | C | D | E | |
---|---|---|---|---|---|---|

# | 0 | 0 | 0 | 0 | 0 | 0 |

B | 0 | 0 | 1 | 1 | 1 | 1 |

D | 0 | 0 | 1 | 1 | 2 | 2 |

E | 0 | 0 | 1 | 1 | 2 | 3 |

We have the following grid, and we start from the lower right.

We see that the last result in the array is 3, meaning that ABCDE and BDE have the longest subsequence of 3.

# | A | B | C | D | E | |
---|---|---|---|---|---|---|

# | 0 | 0 | 0 | 0 | 0 | 0 |

B | 0 | 0 | 1 | 1 | 1 | 1 |

D | 0 | 0 | 1 | 1 | 2 | 2 |

E | 0 | 0 | 1 | 1 | 2 | 3 |

We know the longest subsequence as a number, but now we need to know which letters form the longest subsequence. We find the sequence by finding the values that were incremented from the diagonal, which were in fact the logical step we used when the characters were the same.

We see that the value is different than left and top, meaning that the character was the same, so we got the value by incrementing from diagonal – we mark it and go diagonally.

# | A | B | C | D | E | |
---|---|---|---|---|---|---|

# | 0 | 0 | 0 | 0 | 0 | 0 |

B | 0 | 0 | 1 | 1 | 1 | 1 |

D | 0 | 0 | 1 | 1 | 2 | 2 |

E | 0 | 0 | 1 | 1 | 2 | 3 |

We see that the value is different than left and top, meaning that the character was the same, so we got the value by incrementing from diagonal – we mark it and go diagonally.

# | A | B | C | D | E | |
---|---|---|---|---|---|---|

# | 0 | 0 | 0 | 0 | 0 | 0 |

B | 0 | 0 | 1 | 1 | 1 | 1 |

D | 0 | 0 | 1 | 1 | 2 | 2 |

E | 0 | 0 | 1 | 1 | 2 | 3 |

We see that the value is the same as the one from left, so we go left.

# | A | B | C | D | E | |
---|---|---|---|---|---|---|

# | 0 | 0 | 0 | 0 | 0 | 0 |

B | 0 | 0 | 1 | 1 | 1 | 1 |

D | 0 | 0 | 1 | 1 | 2 | 2 |

E | 0 | 0 | 1 | 1 | 2 | 3 |

We see that the value is different than left and top, meaning that the character was the same, so we got the value by incrementing from diagonal – we mark it and go diagonally. We reached the value 0 so we stop there.

# | A | B | C | D | E | |
---|---|---|---|---|---|---|

# | 0 | 0 | 0 | 0 | 0 | 0 |

B | 0 | 0 | 1 | 1 | 1 | 1 |

D | 0 | 0 | 1 | 1 | 2 | 2 |

E | 0 | 0 | 1 | 1 | 2 | 3 |

The values we marked were B, D, and E => BDE is the longest common subsequence.

` ````
class Matrix {
int* arr;
int width, height;
public:
Matrix(int x, int y) {
width = x; height = y;
arr = new int[x * y] {}; // default to 0
}
int& at(int x, int y) const { return arr[x + width * y]; }
};
int lcs(string s1, string s2) {
const int m = s1.size();
const int n = s2.size();
Matrix grid(m + 1, n + 1);
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1[i - 1] == s2[j - 1])
grid.at(i, j) = grid.at(i-1, j-1) + 1;
else
grid.at(i, j) = std::max(grid.at(i-1, j), grid.at(i, j-1));
}
}
return grid.at(m, n);
}
int main() {
string s1 = "ABCDE";
string s2 = "BDE";
cout << "LCS = " << lcs(s1, s2);
return 0;
}
```

The main() function starts on line 29.

Afterwards, we declare two strings (Lines 30-31) and call the LCS function.

The matrix class (Lines 1-10) is used to store a 2D array. The at() function (Line 9) receives 2 parameters (row and column) and returns the value at that location.

The LCS function starts at line 12.

Then, we get the size of the strings and create the 2d matrix (Lines 13-14).

If we check the line 17-18, we see that we start from index 1. That is because the algorithm behaves this way: the rows and columns with index 0 must have value 0 for our algorithm to work.

- If the characters at a given index are the same in both strings (Line 19): The value of the matrix at that location will be the value that we had on the diagonal incremented by 1 (Line 20).
- Otherwise: The value of the matrix at that location will be the maximum between what we have to the top of it, and what we have to the left of it (Line 22).

That’s the reason why we keep the first row and first column with value 0 – so we can have the algorithm working even when the first character in both strings match (because we will need to access index-1 on both row and column.

At the end, we return the bottom-right location of our matrix, which contains the longest common subsequence.

The rows and the columns are based on the strings we have, so given the first string to be of 3 letters, and 2nd string to be of 5 letters, we will have a matrix of 4x6 (first row and column defaulted to 0, the rest is for each letter in each string).

When we iterate on row, we compare each letter of string 2 to string 1.

When we iterate on column, we compare each letter of string 1 to string 2.

Let’s give an example:

S1 = ABC

S2 = DEF

Row 0, column 0 will have value 0.

- M[1][1] = D vs A
- M[2][1] = E vs A
- M[3][1] = F vs A

Row one will be the longest sequence when we reached the end of S2, but only parsed first letter of S1.

A vs DEF

- M[1][1] = D vs A
- M[1][2] = D vs B
- M[1][3] = D vs C

Column one will be the longest sequence when we reached the end of S1 but only parsed first letter of S2

D vs ABC

Therefore, if the strings have letters in common, we take the maximum between what’s on left and what’s on top until that point.

If strings are ABC, DEF, and we are at location [3][3] (C vs F)

- Left is the LCS for ABC vs DE
- Right is the LCS for AB vs DEF
- Since C and F differ, LCS is the maximum value between (ABC vs DE) AND (AB vs DEF)

The Floyd-Warshall algorithmis used for finding the shortest path between every pair of vertices in a directed Graph.

The algorithm uses a solution matrix, which is initialized so that the entries correspond to the input graph matrix.

Assuming A is the source vertex and B is the destination, we need to find the shortest distance from A to B.

The shortest path could be by going directly from A to B. However, this may not be always the case, and a more efficient solution would be to go through one or multiple other vertices first, such as: A->C->B, or A->D->C->B

This algorithm moves the source vertex as the middle vertex -> The shortest path that reaches B by going through A.

Let’s create a matrix that contains the distances that we have.

In the matrix we will have the following digits:

- 0, for self loop
- Infinity, if there’s no edge
- Otherwise, the cost of the edge between vertices

# | A | B | C | D |
---|---|---|---|---|

A | ||||

B | ||||

C | ||||

D |

Let’s fill the matrix now:

Self-loop -> 0’s

# | A | B | C | D |
---|---|---|---|---|

A | 0 | |||

B | 0 | |||

C | 0 | |||

D | 0 |

No edge - infinity

# | A | B | C | D |
---|---|---|---|---|

A | 0 | INF | INF | |

B | 0 | INF | ||

C | INF | 0 | ||

D | INF | INF | 0 |

Edge between vertices – write the cost

# | A | B | C | D |
---|---|---|---|---|

A | 0 | 5 | INF | INF |

B | 7 | 0 | 2 | INF |

C | 6 | INF | 0 | 1 |

D | 8 | INF | INF | 0 |

**So now we have this solution matrix that represents our graph, and we will use it to calculate the shortest path from one source to all the other vertices.**

# | A | B | C | D |
---|---|---|---|---|

A | 0 | 5 | INF | INF |

B | 7 | 0 | 2 | INF |

C | 6 | INF | 0 | 1 |

D | 8 | INF | INF | 0 |

Let’s assume the source vertex is A – we copy the values we had on that row and column, and also the 0’s we had for the self loops.

Now let’s calculate the paths, starting with the first unset position (B, C)

# | A | B | C | D |
---|---|---|---|---|

A | 0 | 5 | INF | INF |

B | 7 | 0 | ||

C | 6 | 0 | ||

D | 8 | 0 |

We see in the solution matrix that the value that we have is 2.

The shortest path is the minimum value between the initial one (2) and the sum of vertices where the source is added in-between.

Let’s see what that means.

We need to calculate [B,C]

We know [B, C] is 2.

The source vertex is A.

Let’s replace each edge with A, and calculate the sum of these values.

Replacing [B, C] =

- A moved as source = [A, C]
- A moved as destination = [B, A]

[A, C] in the solution table = infinity

[B, A] in the solution table = 7

The shortest path for [B, C]:

Min([B, C], [B, A] + [A, C]) = Min( 2, (infinity + 7)

=> It’s clear that 2 is the minimum value.

# | A | B | C | D |
---|---|---|---|---|

A | 0 | 5 | INF | INF |

B | 7 | 0 | 2 | |

C | 6 | 0 | ||

D | 8 | 0 |

The shortest path for [B,D]:

Min (INF, [B, A] + [A, D] ) = Min( INF, 7 + INF)

=> INF

# | A | B | C | D |
---|---|---|---|---|

A | 0 | 5 | INF | INF |

B | 7 | 0 | 2 | INF |

C | 6 | 0 | ||

D | 8 | 0 |

The shortest path for [C, B]:

Min (INF, [C, A] + [A, B]) = Min( INF, 6 + 5)

=> 11

# | A | B | C | D |
---|---|---|---|---|

A | 0 | 5 | INF | INF |

B | 7 | 0 | 2 | INF |

C | 6 | 11 | 0 | |

D | 8 | 0 |

The shortest path for [C, D]:

Min (1, [C,A] + [A, D]) = Min(1, 6 + INF)

=> 1

# | A | B | C | D |
---|---|---|---|---|

A | 0 | 5 | INF | INF |

B | 7 | 0 | 2 | INF |

C | 6 | 11 | 0 | 1 |

D | 8 | 0 |

The shortest path for [D, B]:

Min (INF, [D, A] + [A, B]) = Min(INF, 8 + 5)

=> 13

# | A | B | C | D |
---|---|---|---|---|

A | 0 | 5 | INF | INF |

B | 7 | 0 | 2 | INF |

C | 6 | 11 | 0 | 1 |

D | 8 | 13 | 0 |

The shortest path for [D, C]:

Min (INF, [D, A] + [A, C]) = Min(INF, 8 + INF)

=> INF

# | A | B | C | D |
---|---|---|---|---|

A | 0 | 5 | INF | INF |

B | 7 | 0 | 2 | INF |

C | 6 | 11 | 0 | 1 |

D | 8 | 13 | INF | 0 |

**If we continue and select the next node as starting node, we will keep updating the table. In the end, the table will look like this:**

# | A | B | C | D |
---|---|---|---|---|

A | 0 | 5 | 7 | 8 |

B | 7 | 0 | 2 | 3 |

C | 6 | 11 | 0 | 1 |

D | 8 | 13 | 15 | 0 |

The values that were infinity are now small, finite numbers.

We understand why the first row/column were infinite, since we never calculated them, but what about BD, and DC?

BD = min(INF, BA + AD)

> AD was infinite because it was never calculated

> BD is also infinite at first iteration

DC = min(INF, DA + AC)

> AC was infinite because it was never calculated

> DC is also infinite at first iteration

` ````
int INF = 99999;
void display(vector<vector<int>> & graph) {
for (const auto& items : graph) {
for (const auto& item : items) {
if (item == INF)
cout << "INF ";
else
cout << item << " ";
}
}
}
void floydWarshall(vector<vector<int>> & graph) {
const int len = graph.size();
for (int k = 0; k < len; k++) {
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
graph[i][j] = std::min(graph[i][j], graph[i][k] + graph[k][j]);
}
}
}
display(graph);
}
int main() {
vector<vector<int>> graph = {
{ 0, 5, INF, INF },
{ 7, 0, 2, INF },
{ 6, INF, 0, 1 },
{ 8, INF, INF, 0 }
};
floydWarshall(graph);
return 0;
}
```

The main() function starts on line 27.

Afterwards, we create a graph, by using a vector of vectors – in other words, a two-dimensional matrix, which contains the distances from one node to another. (eg. Item on row = 3, column = 4, is the edge cost from node 3 to node 4. The value 0 is used for the distance from node to self (row equal to column). In case there’s no edge between two given vertices, the INF value is used. This value is defined on line 1.

Why did we not use something such as the max integer value? We could have used that, but I wanted to make the algorithm as simple as possible.

Explanation:

In line 20, we will have a sum of values, and adding any positive value with the highest possible value that can be written with those bits will cause an integer overflow, so we’ll go on the negative side.

This would have required for the algorithm to become more complex, checking for such overflows and so on.

In line 35, we call the floydWarshall() function, which will create the solution for us.

The display() function from lines 3-12 receives the graph as parameter and iterates through it, displaying its values.

Ok, let’s go to the function we’re interested in – floydWarshall (Line 14).

Line 17 will simply do the same logic over and over again – for X times, where X is the number of vertices we have.

In line 18 and 19, we iterate through our 2d matrix – and update the edge cost, based on the information we have at that point.

Let’s read the code from line 20:

**The value of graph[i][j] (the cost required to get from node i to node j) is, either the current value, if that’s the smallest one, either the sum of the costs by reaching that point through an intermediary node.**

And that’s why we have the line 17 -> each node will be, at some point, the intermediary node for each traversal.

So, what we’re actually saying, is that:

Assuming k=1, i=2, j=3 =>

- What is the cost of reaching node 3, from node 2? Let’s say X.
- What is the cost of reaching node 3, by going from node 2 to node 1, and then from node 1 to node 3? Let’s say Y.
- Is Y a shorter route than X? Then let’s update the value in the matrix, because we found a shorter path.
- What if I and k are the same value?
- - Then we are actually using ourselves as intermediary. The value for self-cost is 0, so nothing changes
- What if there’s no edge from node 2 to 1, or from node 1 to 3?
- Then we will check the minimum cost between a given value X, and the sum of something to which we add INF (which is a very big number). The minimum cost will not change

Sudokuis a number placement puzzle, where the objective is to fill a square grid, with numbers between 1 to 9. As constraints, each row, column, and sub-grids should contain empty spaces or unique numbers from 1 to 9.

With backtracking, we try to add the digits one by one. When we find that a digit cannot lead to a solution, we backtrack (remove it) and try the next digit.

**Steps:**

- Make a list of all the empty places
- Select a position and place a number between 1 and 9, and validate the grid
- If the constraint fails – abandon the candidate and go back to step 2 with another number
- Until the solution is not found – repeat steps 2-3

Let’s only look on the top-left grid first.

9 | 3 | |

5 | 1 | |

2 |

Each square contains all the digits from 1 to 9.

We see that we have 4 empty places, and 4 digits that are not there (4, 6, 7, 8)

One of the constrains is to have unique digits in a sub-grid such as this one, so we have to use those digits to fill the empty spaces.

We start with the first available position, and iterate through all digits.

We write 1 in the empty place, and then we check the constraints:

We fail the constraints, because we already have the digit 1 in the same sub-grid. Therefore, we continue with the next digit

We write 2 in the empty place, and then we check the constraints:

We fail the constraints, because we already have the digit 2 in the same sub-grid. Therefore, we continue with the next digit.

Same goes for 3 (exists in sub-grid), 4 (exists in same row), 5 (exists in sub-grid), 6 (exists in same col).

7 is valid, because it doesn’t break the constraints.

Therefore, we write 7 and check the next empty-space.

1,2,3 are in the same sub-grid, so they fail the constraints, but 4 is ok so we write it and check the next empty-space.

1,2,3,4,5 are in the same sub-grid, but 6 doesn’t break constraints, so we write it and check the next empty space.

8 is the only remaining digit that doesn’t exist in sub-grid. We write 8 in the empty-space, but we see that the constraints are broken (same column).

Because the constraints are broken, we clear the value and continue to the next digit.

Since we don’t have any remaining digit (9 in same sub-grid), we return to the previously written digit and continue to the next available digit.

We write the digit 8, but the constraints are again broken (already exists in the same column), and 9 already is in the same sub-grid, so we set as empty space and go one more step back to the previously written digit and continue to the next available digit.

We continue from the current digit (4):

- 5 is invalid (same sub-grid)
- 6 is invalid (same row)
- 7 is invalid (same sub-grid)
- 8 is invalid (same column)
- 9 is invalid (same sub-grid)

We set as empty space and go one more step back to the previously written digit and continue to the next available digit.

We continue from the current digit (7):

8 is valid, no constraints are broken

We write 8 and check the next empty space

… and so on.

` ````
int UNSET = 0;
int N = 9;
int main() {
int grid[N][N] = {
{ 9, 3, 0, 0, 0, 4, 2, 0, 0 },
{ 5, 0, 1, 6, 2, 0, 0, 8, 0 },
{ 0, 0, 2, 0, 9, 0, 4, 5, 1 },
{ 2, 0, 3, 0, 0, 0, 0, 0, 8 },
{ 0, 1, 0, 0, 0, 0, 0, 3, 0 },
{ 8, 0, 0, 0, 0, 0, 7, 0, 5 },
{ 4, 5, 9, 0, 3, 0, 6, 0, 0 },
{ 0, 8, 0, 0, 4, 6, 5, 0, 2 },
{ 0, 0, 6, 9, 0, 0, 0, 4, 3 }
};
Sudoku sudoku(grid);
if (sudoku.solve() == true)
sudoku.display();
return 0;
}
```

We have a main() function, we create the matrix, and we call the solve function from the Sudoku class (Line 18).

` ````
class Sudoku {
int grid[N][N] = {};
public:
Sudoku(int _grid[N][N]) { /* copy the grid to our class */ }
void display() { /* iterate through grid and display data */ }
bool solve();
private:
bool isLegalMove(int row, int col, int num) {
return grid[row][col] == UNSET &&
false == alreadyInRow(row, num) &&
false == alreadyInCol(col, num) &&
false == alreadyInBox(row - row % 3, col - col % 3, num);
}
bool findNextEmpty(int &row, int &col) {
for (row = 0; row < N; row++)
for (col = 0; col < N; col++)
if (grid[row][col] == UNSET)
return true;
return false;
}
bool alreadyInRow(int row, int num) {
for (int col = 0; col < N; col++)
if (grid[row][col] == num) return true;
return false;
}
bool alreadyInCol(int col, int num) {
for (int row = 0; row < N; row++)
if (grid[row][col] == num) return true;
return false;
}
bool alreadyInBox(int box_row, int box_col, int num) {
for (int row = 0; row < 3; row++)
for (int col = 0; col < 3; col++)
if (grid[row + box_row][col + box_col] == num)
return true;
return false;
}
};
```

IsLegalMove() function (Line 8-13) returns true if all the conditions below are met:

- The value at that location is not already set (Line 9)
- If we don’t have that value already on the same row (Line 10) – implementation in lines 23-27.
- If we don’t have that value already on the same column (Line 11) – implementation in lines 29-33.
- If we don’t have that value already in the sub-grid (Line 12) – implementation in lines 35-41.

FindNextEmpty() function (Line 15-21) returns true if:

There’s still an empty position in the grid.

The location for that position is returned through params, as they are sent as reference.

Now we’re left with the solve function, which is implemented below:

` ````
bool Sudoku::solve() {
int row, col;
if (!findNextEmpty(row, col))
return true;
for (int num = 1; num <= 9; num++) {
if (isLegalMove(row, col, num)) {
grid[row][col] = num;
if (solve())
return true;
grid[row][col] = UNSET;
}
}
return false;
}
```

The solve() function is a recursive function.

In line 2 we declare two variables, row and col, which we’ll pass further as references in line 4.

As usual, in each recursive function, we first declare the exit function.

If the findNextEmpty() function returns false, it means we’re out of unset cells, so the sudoku is solved. Therefore, we return true.

For all numbers from 1 to 9 (Line 7):

If it’s a legal move, or in other words, if we can add a digit in that location without having any failed constraints (Line 8):

- We update the grid with that digit at that location
- We call the solve function recursively

If the solve function failed – we unset the value in the grid and go for the next digit.

If we iterated through all digits and failed, it means we’re out of the loop. Therefore, we return false (Line 17).

The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each other.

In order for two queens not to attack each other, we need the following constraints:

- They should not be on the same row
- They should not be on the same col
- They should not be on the same diagonal

With backtracking, we are adding first queen in the upper-left corner, and since the constraints are not broken, we attempt to add the 2nd queen on the 2nd row. Each time we add a queen on the chess board, we check for constraints, and if they are broken, we backtrack to the next available location, and so forth.

For example, following is a solution for 4 Queen problem.

Let’s use a binary matrix which contains 1 in places where queens are placed.

The output matrix for the solution above is the following:

0 | 1 | 0 | 0 |

0 | 0 | 0 | 1 |

1 | 0 | 0 | 0 |

0 | 0 | 1 | 0 |

**We start with the chess board empty (no queen placed)**

0 | 0 | 0 | 0 |

0 | 0 | 0 | 0 |

0 | 0 | 0 | 0 |

0 | 0 | 0 | 0 |

We need to position 4 queens (Q1, Q2, Q3, Q4).

Let’s apply our first constrain: queens cannot be on the same row, or on the same column. (otherwise they’re attacking each other.)

I’ll go with them being on different rows.

1 | 0 | 0 | 0 |

0 | 0 | 0 | 0 |

0 | 0 | 0 | 0 |

0 | 0 | 0 | 0 |

We are currently placing Q1.

We start with the first available position (upper-left corner).

1 | 0 | 0 | 0 |

1 | 0 | 0 | 0 |

0 | 0 | 0 | 0 |

0 | 0 | 0 | 0 |

Since the constraints are not broken, we continue with 2^{nd} queen.

After we placed the 2^{nd} queen, we see that the constraints are broken.

Therefore, we return false from the function and choose the next available position for the 2^{nd} queen.

1 | 0 | 0 | 0 |

0 | 1 | 0 | 0 |

0 | 0 | 0 | 0 |

0 | 0 | 0 | 0 |

After we placed the 2^{nd} queen, we see that the constraints are broken.

Therefore, we return false from the function and choose the next available position for the 2^{nd} queen.

1 | 0 | 0 | 0 |

0 | 0 | 1 | 0 |

0 | 0 | 0 | 0 |

0 | 0 | 0 | 0 |

Since the constraints are not broken, we continue with 3rd queen.

1 | 0 | 0 | 0 |

0 | 0 | 1 | 0 |

0 | 0 | 0 | 0 |

0 | 0 | 0 | 0 |

After we placed the 3^{rd} queen, we see that the constraints are broken.

Therefore, we return false from the function and choose the next available position for the 3^{rd} queen.

1 | 0 | 0 | 0 |

0 | 0 | 1 | 0 |

0 | 0 | 0 | 0 |

0 | 0 | 0 | 0 |

After multiple iterations, we see that the constraints are broken for all remaining positions.

Therefore, we return false from the function and choose the next available position for the 2^{nd} queen.

1 | 0 | 0 | 0 |

0 | 0 | 0 | 1 |

0 | 0 | 0 | 0 |

0 | 0 | 0 | 0 |

No constraints are broken, go for the 3rd queen.

1 | 0 | 0 | 0 |

0 | 0 | 0 | 1 |

0 | 1 | 0 | 0 |

0 | 0 | 0 | 0 |

After iterations, we see that we have only a possible location for 3rd queen, and we place it there.

1 | 0 | 0 | 0 |

0 | 0 | 0 | 1 |

0 | 1 | 0 | 0 |

0 | 0 | 0 | 0 |

There is no available location for 4th queen (all of them break constraints)

So we return false and move Q3.

We don’t have other possible locations for Q3, as it will be attacking Q2

So we return false and move Q2.

There are no available locations for Q2

So we return false and move Q1

0 | 1 | 0 | 0 |

0 | 0 | 0 | 1 |

0 | 1 | 0 | 0 |

0 | 0 | 0 | 0 |

Q1 has been moved to the 2nd column, and now we start moving Q2.

The algorithm continues until all 4 queens have been placed, and no constraints are broken.

` ````
int N = 4;
void printSolution(int board[N][N]) { /* function to display the board */ }
bool isSafe(int board[N][N], int row, int col) {
for (int i = 0; i < col; i++)
if (board[row][i])
return false;
for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j])
return false;
for (i = row, j = col; j >= 0 && i<N; i++, j--)
if (board[i][j])
return false;
return true;
}
bool do_solveNQ(int board[N][N], int col) {
if (col >= N)
return true;
for (int i = 0; i < N; i++) {
if (isSafe(board, i, col)) {
board[i][col] = 1;
if (do_solveNQ(board, col + 1))
return true;
board[i][col] = 0; // backtrack
}
}
return false;
}
bool solveNQ() {
int board[N][N] = {};
if (do_solveNQ(board, 0) == false) {
cout << "There is no solution";
return false;
}
printSolution(board);
return true;
}
int main() {
solveNQ();
return 0;
}
```

As usual, we start from main(), in line 52, which simply calls the solveNQ() function.

The implementation of this function is found on line 40.

In line 41, we create a matrix of size N (where N is declared on line 1).

Afterwards, we call the do_solveNQ() function, passing it the board and the column we’re working with (we start with 0). We use this delegation because this function is recursive.

In case we find a solution, we print it (Line 48). I’ve skipped this implementation, to fit into the page. The display function simply iterates through the board and displays its values.

Line 5 introduces a helper function (isSafe), which receives the board and a location, This function returns true if we cannot add a queen on that location. This happens if:

- we have a value of 1 in the same column (Line 6-8)
- we have a value of 1 in the big diagonal (Line 10-12)
- we have a value of 1 in the small diagonal (Line 14-16)

If this is not the case, then we are free to use that location to position our queen, so we return true (Line 18).

In Line 21 we start the do_solveNQ function.

As previously said, we receive the board and the column we are on.

First, we add the exit condition (Line 22-23): If we finished placing all queens on the table, we solved the problem.

If not, we try to find a location for the queen, in the current column.

For each possible row location (Line 25):

- If we’re able to insert the queen at that location (no attack from other queens)
- Add the queen at that location (Line 27)
- Call the same function, but for the next column => find a location for the next queen.

If we reached line 32, it means the condition on line 29 have failed – so we were unable to place the next queen.

This means that it is impossible to have a solution if our queen is positioned on that location – so we backtrack, removing it from that position (Line 32).

We are inside a for statement, so we will attempt to place this queen on the next row.

If there are no more rows available, we will eventually leave the function from line 36, returning false to the caller -> which will continue from line 32.

This was the case with our previous queen:

- We position the first queen
- We try to find a location for the 2nd queen, that is not attacked by the first one.
- Once we find a viable location, we do the same for the 3rd queen.
- 3rd queen goes through all the rows (Line 25), but is unable to find a safe location (Line 26). Therefore, it returns false, exiting in line 36.
- The call goes back to 2nd queen, in line 29. The condition fails, so we try to find another location for 2nd queen. If we are out of options, we’ll face the same faith, and we’ll go back to 1st queen and move it on the next location.

If the 1st queen goes through all rows and doesn’t find a proper location, it exits on line 36, returning false to the caller (Line 43) -> So we will not have any solution.

On the happy case, where there’s a solution, we position first queen (Line 27), recursively call the same function for col=1 (Line 29).

This will continue with the 2nd, 3rd , and 4th queen, so when we will call the line 29 to solve the problem for col=5, we will reach line 22-23 and returns true.

Returning true from do_solveNQ will go back to the caller in line 29-30, until we go back to solveNQ function in line 43. The if statement will fail, because the return value of the function is true, not false, so we will print the solution (Line 48).

A maze is given as a N*N matrix where the source is in the upper left (0,0) and the destination is on the lower right (N-1, N-1). In this problem, we have a rat which has to start from the source and he has to reach the destination, and can only move down and to the right.

First of all, we will need to check if we have reached the destination. If not:

- We mark the current cell (set to 1)
- We move to the right by recursively calling the same function (with different param)
- If there’s no solution: We move down by recursivelly calling the same function (with different param)
- If there’s no solution: We unmark the current cell (set to 0) and backtrack (return false from the function)

The main function will be the following:

The main() function starts at line 1. We create a maze object (Line 9) and pass a matrix that contains the value 1 where the road is clear, and 0 if the road is blocked (Line 2-7).

The line 10 calls the algorithm which finds the maze exit and solution.

We need to keep a matrix which represents our maze.

1 | 0 | 0 | 0 |

1 | 1 | 0 | 1 |

0 | 1 | 0 | 0 |

1 | 1 | 1 | 1 |

` ````
int main() {
int grid[N][N] = {
{ 1, 0, 0, 0 },
{ 1, 1, 0, 1 },
{ 0, 1, 0, 0 },
{ 1, 1, 1, 1 }
};
Maze maze(grid);
maze.solve();
return 0;
}
```

` ````
int N = 4;
class Maze {
int maze[N][N] = {};
int sol[N][N] = {};
public:
Maze(int _maze[N][N]) {
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
maze[i][j] = _maze[i][j];
}
void display() {
for (int row = 0; row < N; row++) {
for (int col = 0; col < N; col++) {
cout << sol[row][col] << " ";
}
cout << std::endl;
}
}
bool solve() {
if (do_solve(0, 0) == false) {
cout << "There is no available solution";
return false;
}
display();
return true;
}
private:
bool do_solve(int x, int y) {
if (x == N - 1 && y == N - 1) {
sol[x][y] = 1;
return true;
}
if (isInsideMaze(x, y) == true) {
// add to the soslution
sol[x][y] = 1;
if (do_solve(x + 1, y))
return true;
if (do_solve(x, y + 1))
return true;
// Backtrack
sol[x][y] = 0;
return false;
}
return false;
}
bool isInsideMaze(int x, int y) {
if (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1)
return true;
return false;
}
};
```

The solve() function called from main is found on line 22. This function simply calls another function (do_solve), which returns a boolean value (True when a solution has been found). We use this function because we will call it recursively, starting from top-left side (0, 0) and advance it’s location until we reach the bottom-right side.

Let’s talk about the class itself. It receives the maze on the constructor (Line 7), and we copy it to our own matrix (Line 8-10). The display() function simply displays the solution for the maze (Line 13-20).

The function defined in line 55 is a helper function (used to help solving the maze). This function returns true if both x and y coordonates are part of the maze (bigger than 0 and less than the maximum size), and if the value of the maze at that location is 1.

Let’s talk now about the do_solve() function (Line 32).

This function receives two parameters (the current location).

First, we have the exit condition. If the current location is the end location, we mark the location as solution and we exit (Line 33-35).

If we haven’t reached the exit yet – we need to keep moving. Because we know that we always start from top left and we always have to reach bottom down, we are interested in moving down and to the right – and that’s exactly what we’ll do.

If we haven’t reached a blocking point (coordonates are still legal and in the maze, and we have somewhere to go), we add the current location as a solution (Line 40). That is because the isInsideMaze function already checks if the current location is set to 1, so we won’t ignore separately the areas in which we cannot go in.

After we mark the current location as solution, we try to go right. This will happen recursively. If the function returned true, it means the solution was recursively found, and at some point we returned from line 35. That is the only point in the function that returns true – the rest of them are triggered from another recursive call.

If at some point we reach a dead end, we reach back to the function that called. We try to go down instead. The same story applies. Assuming this is a dead end – we enter the function (Line 33), the if statement fails, because we’re not at the end point, the if statement on line 38 fails again, because the value of the maze at that location is 0 – so we return false.

If we haven’t found a solution by going recursively to the right or to the bottom, we reached a dead end and we have to go back. (backtrack). Therefore, we remove the current location as a part of solution (Line 49) and return false to the caller.

Towers of Hanoi is a puzzle in which we have x rods and y disks. We need to place the entire stack of disks into another rod, while following the rules:

- Only one disk can be moved at once
- A move consists of taking the disk from the top of the stack and place it on top of another stack
- You cannot place a disk on top of a smaller disk

This puzzle is easily implemented through recursion. We need to have a stop point in the recursive function, when we are working with the latest disk from that stack.

In the function, we call the function again for the next disk in the stack, and thus we will keep calling this recursively until we reach the biggest disk. Since that is the stopping point, we can proceed with the next line in the function, in which we will recursively call the function, but this time we will move the disk to the destination stack.

Let’s proceed with an example, to be more clear.

Assuming we have 5 disks that needs to be moved from A to B:

Because we cannot move big disks on top of smaller ones, we need to use the temporary stack as auxiliary.

The first step is to move all disks except the last one, from A to C (destination for remaining disks), using B as a spare.

auxiliary position, we can move the biggest one to our destination.

Now that we have the biggest item in the destination, our purpose will be to move all but one item from source stack (C) to auxiliary stack (A), and then append that item to our destination stack (B)

` ````
int disks = 4;
int point_start = 0;
int point_aux = 1;
int point_end = 2;
void towerOfHanoi(int n, int from, int to, int aux) {
if (n == 1) return;
towerOfHanoi(n - 1, from, aux, to);
towerOfHanoi(n - 1, aux, to, from);
}
int main() {
towerOfHanoi(disks, point_start, point_end, point_aux);
return 0;
}
```

The code is short, but there’s a lot of recursion going on.

We have a few constants (Lines 1-4) defined for our code:

- The number of disks we’re gonna use (Line 1)
- The location that initially contains all the disks (Line 2)
- The location that will be used as intermediary (Line 3)
- The location that will contain all the disks after the algorithm ends (Line 4)

The first function called will be main(), in line 14, which simply calls our algorithm.

The algorithm is called with n = 4 (our disks), from = point_start, to = point_end, aux = point_aux (Line 7).

Line 8 handles the recursion, which exits if we are working with disk 1. We’ll see why later.

The algorithm is implemented with two lines (10-11) – with the help of recursion.

Let’s try to make this simple, by using the following terms:

- R1 for line 10
- R2 for line 11
- RC for returning to the caller (either from line 10, or from line 15).

Let’s take the situation for number of disks = 2. Please follow the code as you follow the steps.

- Disk 2 => R1
- Disk 1 => RC (disk 2)
- Disk 2 => R2
- Disk 1 => RC (disk 2)
- Disk 2 => RC (exit)

We will call this situation 1.

Let’s take the situation for number of disks = 3. Please follow the code as you follow the steps.

- Disk 3 => R1
- Disk 2 => R1
- Disk 1 => RC (disk 2)
- Disk 2 => R2
- Disk 1 => RC (disk 2)
- Disk 2 => RC (disk 3)
- Disk 3 => R2
- ...
- Disk 3 => RC (exit)

We will call this situation 2.

We see that we can simplify this expression as follows:

Situation 2:

- Disk 3 => R1
- Situation 1
- Disk 3 => R2
- Situation 1
- Disk 3 => RC (exit)

Based on this, we will have the following logic for 4 disks:

- Disk 4 => R1
- Situation 2
- Disk 4 => R2
- Situation 2
- Disk 4 => RC (exit)

- Given a number as input, count the number of bits with value 1 (e.g. 0101 – 2, 1111 – 4).
- Given a number as input, check if it’s a power of 2. Can you do that without looping?
- How can we detect whether a graph contains cycles?
- How can we check whether there’s a path between two vertices, in a directed graph?
- Given the tree root node and the destination node – find out the level of the destination node.

Given two strings A and B of equal lengths, containing only lower case letters, your job is to count the minimum number of changes required on string A to make it equal to string B.

Given n a positive number bigger than 1, count the number of trailing zeros of the factorial result.

Assuming n is 10, the factorial result will be 1*2*3* … * 10.

Given a linked list and having access only to the head element, print the reverse list without using recursion or extra allocated space.

A permutation is a rearrangement of the elements. A string of length n has n! permutations.

Assuming our string is ABC, the following permutations are possible: {ABC, ACB, BAC, BCA, CAB, CBA}.

We can see that we started with A and shuffled the letters, then we moved B as first position and did the same, and then the same way for C.

Having Longest Common Sequence in mind – calculate the longest increasing subsequence (the length of the longest subsequence in which all elements are sorted in increasing order).

Given an array of jobs (each with their own deadline and with a given profit only if the job is finished before the deadline), and knowing that every job takes at least one unit of time (minimum deadline is 1) and that only one job can be scheduled at a time – Create an algorithm to maximize total profit.

Given a directed graph, that does not contain a cycle – count the number of paths that exist between two vertices.

I suggest installing Ubuntu on your personal computer, or searching online for a playground / practical course. There are a few basic commands that you must know by heart, such as copying or moving files, creating and removing files and directories, reading the content of a file, executing binaries or changing the access permissions of a file.

The next thing you should do after you exercise with such commands, is to write them into a script and execute it.

This will get you used to creating scripts for repetitive commands.

Python has increased in popularity lately, and I recommend learning it, because it excels at small scripts, due to its powerful libraries which allows some rapid development. Take a text file with lot of information from it and:

- Read in the file
- Create a collection of words and their occurrences
- Create a collection of anagrams
- Create a collection of words and the positions in which they occur (line#, word position)
- Remove all of the white space from the file
- Write all of the above data to their own files

- Create a timer and do something on process event
- Create delegates / events and add them in the code
- Create a unit test for a public function
- Create a basic GUI (button, label, progressbar - that increases on timer tick)
- Use LINQ statement to calculate some specific values based on collection data
- Encrypt and decrypt a password using Security namespace
- Create a database and connect to it
- Use SQL to make DB requests (CRUD)

- Create a library and a new project, link with your library (both statically and dynamically).
- Create a small application (client/server) that communicate with each other through sockets.
- Integrate makefile with the build project and make it cross-platform compilable.
- Integrate some open-source library into your project, such as curl, rapidjson, zlib.

- Create a basic GUI application and add a class with signals and slots.
- Emit a signal on button press that changes the color of a button.
- Change the button color on mouse hover, on left and right click, on entering and leaving the area.

Vertex: Node containing data

Edge: The line that connects two vertices

Cycle: Cycles occur when nodes are connected in a way that they forms a closed structure.

Cycle: Cycles occur when nodes are connected in a way that they forms a closed structure.

Self loop: An edge that connects a vertex to itself (source = destination).

Negative weight edge refer to edges with a negative cost.