Programming III

Final Examinations 1st. Term 2020

Solved Exercises

1 Longest Paths in Ordered Graphs

Assume we have an ordered directed graph G = (V, E) with V = {v1 , . . . , vn }.
We say that G is ordered if it fulfils the following conditions:
• All edges have the form (vi , vj ) with i < j.
• All vertices have outgoing edges except vn .
The objective is to find the length of the longest path from v1 to vn . You are
kindly asked to:
(a) Find a dynamic programming strategy to solve this problem.
(b) Write down the recurrence formulæ.
(c) Write down the pseudo-code.
(d) Calculate the complexity of your program.

Example: the figure shows an ordered graph. The longest path from 0 to 5 is
(0-1-2-3-4-5) and it has length 5.

2 3

0 5

1 4

Solution (a) To establish the strategy, we begin by analysing what is the

advantage of the order of the graph. It is the following one: we know that any
incoming edges to node vj are originated in nodes that are strictly smaller than
vj . Therefore, we need only to look backward, not forward.
We construct a vector L[i] where L[i] contains the longest path from 0 to i.
To construct this array, we take the maximum path from 0 to j such that (j, i)
is an edge and add 1 to it. The position L[n − 1] contains the value we seek.

1
(b) According with what explained above, we have the following recurrence
formulæ: 
0 if i = 0
L[i] =
max(L[j] + 1 | (j, i) ∈ E) otherwise
(c) The pseudo-code is shown below.

1. Algorithm Longest_Path {
2. Input: G: graph;
3. Output: len: int;
4. int n = |G.V |; // Number of vertices of G
5. int m = |G.E|; // Number of edges of G
6. L = initialize array int[n];
7. L[0] = 0 // Value in 0
8. for (i = 1; i < n; i + +) { // Construction of L
9. int mxLen = 0;
10. for each (u, i) ∈ E {
11. mxLen = max (mxLen, L[u]); // Longest previous path
12. }
13. L[i] = mxLen + 1;
14. }
15. return L[n − 1];
16. }

(d) Complexity is simple. We iterate |V | times over all edges. We are therefore
in O(|V ||E|). How do |V | and |E| relate? If he graph is strongly connected, we
have that |E| = O(|V |2 ) and if it has a tree-structure we have that |E| = O(|V |).
Hence complexity oscillates between O(|V |2 ) and O(|V |3 ).

2
2 The Bellman-Ford Algorithm
This is a dynamic programming of the better known Dijkstra algorithm, which
is a greedy algorithm. In this cases, we start from a weighted directed graph
G = (V, E) where the weights might be negative. As it was the case with
Dijkstra, this algorithm finds the shortest path from a given node to all the
other ones.
The strategy begins by creating an array L where each element L[i] contains
the minimal distances from node s to node i in each step. We assume without
loss of generality that the nodes are named with sequential numbers starting at
0 where 0 is the base node.
There is an initialisation step in which we set L[0] = 0 (the distance of s to
itself is of course 0; this will not change in the upcoming steps) and L[i] = ∞
for i > 0 (the distance of all other nodes to the base nodes is set initially to
infinite; this will change in the upcoming steps.)
Next, in each step the distances L[i] are recalculated as follows. We denote
by w(u, v) the weight of edge (u, v) ∈ E. Therefore for each edge (k, i) ∈ E we
take L[i] = min (L[k] + w (k, i), L[i]). This is repeated |V | − 1 times.
(a) Write the recurrence formulæ for this algorithm. As you know, these are
the formulæ that allows us to construct the M matrix.

(b) Write the corresponding pseudo-code.

(c) Calculate the complexity of your program. What happens if we have a tree?
What if we have a strongly connected graph?
(d) Apply the Bellman-Ford algorithm to the following graph to find the mini-
mal distance from node 0 to all other nodes:

-1
1 4

6 -2 3
1
0 5 2
6
3
5 -2
-1

3 5

Solution
(a) The recurrence formulæ are directly given in the statement of the exercise:

 0 if i = 0 (only step 0)
L[i] = +∞ if i = 0 and j > 0 (only step 0)
min (L[i], min L[k] + w(k, j) for all (k, j) ∈ E) if i > 0 and j > 0


3
(b) The pseudo code is the following:

1. Algorithm Bellman-Ford {
2. Input: G: graph, s: int;
3. Output: GBF: graph;
4. int n = |G.V |; // Number of vertices of G
5. int m = |G.E|; // Number of edges of G
6. L = initialize array int[n];
7. L[0] = 0 // Start initialisation
8. for (i = 1; i < n; i + +) {
9. L[i] = ∞;
10. } // End initialisation
11. for (i = 1; i < n; i + +) { // Construction of L
12. for each (u, v) ∈ E {
13. L[v] = min (L[v], L[u] + w(u, v)); // Recalculation
14. }
15. }
16. GBF=initialize graph; // Resulting graph
17. for (i = 1; i < n; i + +) {
18. GBF.addVertex(i); // All vertices of G are in GBF
19. }
20. for (i = 1; i < n; i + +) {
21. GBF.addEdge(0, i, L[i]); // The minimal edges
22. }
22. return GBF;
23. }

(c) Complexity is relatively simple. We iterate |V | times over all edges. We

are therefore in O(|V ||E|). How do |V | and |E| relate? If he graph is strongly
connected, we have that |E| = O(|V |2 ) and if it has a tree-structure we have
that |E| = O(|V |). Hence complexity oscillates between O(|V |2 ) and O(|V |3 ).

(d) We have for the graph of the example:

0 1 2 3 4 5 6
0 0 ∞ ∞ ∞ ∞ ∞ ∞
1 0 6 5 5 ∞ ∞ ∞
2 0 3 3 5 5 4 7
3 0 1 3 5 0 4 3
4 0 1 3 5 0 4 3
5 0 1 3 5 0 4 3
6 0 1 3 5 0 4 3

4
3 Longest Paths in Ordered Graphs Revisited
Back to the ordered graph. Somebody criticises the dynamic programming
solution because it it too complicated and proposes another one instead. We
will denote by N + (vi ) the set of all vertices that can be reached from vi in one
step.
• Start at x = v1 with c = 0.
• Choose the smallest vertex vj in N + (x) and set c + + and x = vj . Repeat
until x = vn .

• Return c
Please answer the following questions.
(a) To which technique corresponds this approach?

(b) Justify that it is correct or prove that it is not with a counterexample.

Solution

(a) This is clearly a greedy approach. The set of candidates are all vertices,
the selection function chooses the smallest one, the objective is to maximise
the length of the path, there is no feasibility function (any candidate can enter
the solution) and the solution function checks that the last vertex vn has been
reached.

(b) It is wrong. A simple counterexample is the following one.

0 5
3

2 4

5
4 Books in a Shelf
We have a set of books B1 , . . . , Bn which we want to put in order in several
shelves 1, . . . , m, all of them having length L. Each book has a width A1 , . . . , An .
You may assume you have all the shelves you need.
You are kindly asked to:
(a) Establish a strategy to put them in an optimal way. This means, that we
want the maximum possible free space in the last shelf. You may assume
that the books are already ordered (i.e., Bj does not come before Bi if
Bi > Bj .) Which technique have you used?
(b) Justify in a convincing way that your strategy is optimal. This is important.
(c) Write the pseudo-code that realises your strategy.
(d) Calculate the complexity of your solution.

Solution

(a) The simplest way is to put all books that fit in the first shelf and continue
with the second one until all books are placed. Since the order is determined,
we just need an array P with n elements in which P [i] is the shelf in which book
B[i] is placed.
(b) Assume there is a better solution. We show that at a given shelf, our
solution puts at least as many books as the other one. This works by induction
on the number of shelves.
Base case: in the first shelf, our solution cannot have less books because we
put all books that fit in the shelf.
Induction step: assume the statement holds for shelf k. We show that it
also holds for statement k + 1. Suppose we finished in statement k with Bi .
The competing solution must have finished with some X ≤ Bi by induction
hypothesis. Since we start in shelf with Bi+1 and put all books that fit, say,
until book Bj , if the other solution starts with X it must put book Bi+1 in shelf
k + 1. Therefore it cannot pass beyond book Bj because otherwise it should be
possible to put another one, which contradicts the procedure.
It is thus impossible to find a better solution. The proposed solution is
optimal. This is clearly a greedy approach where the set of candidates is the
set of all available books, the feasibility function controls that the book fits and
that the order is right, we want to maximise the free space left after the last
book Bn . The solution function verifies that all books have been placed in the
shelf.
(c) The pseudo-code is the following one.

6
 1. Algorithm Books_n_Shelves {
2. Input: A, B: array [n] of int; // The books and their widths
3. L: int; // The length of each shelf
4. Output: P : array [n] of int; // The positions of the books
5. int s = 1; // Index of shelves
6. double free = L; // Free space in a shelf
7. for (i = 0; i < n; i + +) {
8. if A[i] > acum { // The book does not fit
9. free = L; // New shelf
10. s + +;
11. }
12. P [i] = s // B[i] goes to shelf s
13. free = free −A[i];
10. }
11 return P;
12. }

(d) Complexity is clearly O(n).

7
5 Files on Tape
We want to store n files on tape. The process to read a file from a tape is not
the same as to read a file from a disk. A tape provide only sequential access to
the files. Thus, to read a file from tape we have first to fast-forward past all the
other files until we reach the one we want to read. Fast-forwarding takes time.
Let L[1, . . . , n] be an array listing the lengths of each file (file i has length L[i].)
If the files are stored in order from 1 to n, then the cost of accessing the kth file
is
Xk
cost(k) = L[i]
i=1
This calculation reflects the fact that before we read file k we must first scan
past all the preceding files on the tape and afterwards read the file on position
k. If we assume that all files are equally likely to be accessed, then the expected
cost of searching for a random file is simply the average of all costs:
n n k
X cost(k) 1 XX
E(cost) = = L[i]
n n i=1
k=1 k=1

If we change the ordering in which files are stored, the expected access time
changes. Please answer the following questions.
(a) Which is the best ordering to minimise the expected access cost and why?
Give a sound reason. n convincente.
(b) Devise a strategy to store the file according to their size. Which of the
techniques we studied are you using and why?
(c) Write the pseudo-code that realises your strategy and calculate its complex-
ity.

Solution

(a) The ordering seems intuitively clear: we have to sort the files in increasing
order of length. But to be sure that this works, we have to prove it. A simple
proof is the following: let us denote π(i) the position the index of the file stored
at position i in the tape. Suppose we have the files out of order. There must
be at least two files a and b aat neighbouring positions i and i + 1 such that
L[a] > L[b] (namely, there must be at least a pair of adjacent files with the large
one immediately preceding the smaller one.) Now assume we swap both files in
the tape. The access time of file a increases in L[b] and the access time of file b
decreases in L[a].
The expected cost changes as follows:

nL[1] + (n − 1)L[2] + . . . + L[n−i)L[a]+(n−(i+1))L[b] + . . . L[n]

before:
n

8
And then we have:
nL[1] + (n − 1)L[2] + . . . + L[n−i)L[b]+(n−(i+1))L[a] + . . . L[n]
before:
n

Therefore, the difference is L[b]−L[a]

n . But since L[a] > L[b], the situation has
improved. Therefore, we can decrease the expected cost by swapping disordered
pairs of files. In the end, all files will be ordered and any further swapping
will worsen the expected cost. In other words, if we call π(i) the position of
file i in the tape, the expected cost of access is minimised when for all files
L[π(i)] > L[π(i + 1).

(b) The strategy is simple. We put the files on a min-priority queue with the
length of the file as key and then we write the files onto the tape as they come out
the priority queue. This is clearly a greedy strategy, where the candidates are
the files, the selection function the size of the files, the goal is the minimisation
of the expected access cost, there is no feasibility function (any candidate could
go to the tape), and the solution is reached when the priority queue is empty.

(c) The pseudo-code follows.

1. class pair { // We need this to relate

2. int inx; // the indexes of files with their sizes
3. int weight;
4. };
5. Algorithm Files2Tape {
6. Input: L: array of int [n];
7. Output: O: array of int [n]; // Order in the tape
8. U initialize array pair[n];
9. mPQ initialize min-priorityQueue of pair key weight;
10. for (i = 1; i < n; i + +) { // Put all pairs in U
11. U [i].inx = i;
12. U [i].weight = L[i];
13. }
14. for (i = 1; i < n; i + +) { // Put all pairs in mPQ
15. mPQ.insert(U [i]); // O(log n)
16. }
17. for (i = 1; i < n; i + +) { // Put all indexes in O
18. O[i] = mPQ.poll.inx; // O(log n)
19. }
20. return O; // Sequence of writing
21. }

Complexity is straightforward. We iterate n times inserting to and polling

from the priority queue, operations that have both a cost O(log n). Complexity
is thus O(n log n).

9
6 Maximal Independent Set in a Graph
Given n undirected graph G = (V, E), a subset of vertices A ⊆ V is independent
or stable if all elements in A are pairwise non-adjacent. This is an NP-complete
problem, so it is rather improbable that an algorithmic efficient solution exists.
Nothing prevents us, notwithstanding this, to use inefficient solutions. You
are asked to:
1. Determine a backtracking strategy to solve the problem of finding the
largest independent set para of an undirected graph G = (V, E).

2. Write the pseudo-code of your solution. You may assume you have that
the nodes of the graph are sequentially numbered. This will ease your
task.
3. Calculate the complexity of your solution.

Example: in the figure below, the set of green nodes is an independent set.

8 9

3 6 5

1
0

Solution

(a) The strategy is rather primitive: we construct all possible subsets and test
whether they are independent. If they are, they are compared with the largest
independent set we have found so far and, if it is larger, it replaces the ancient
largest set. The independent sets are represented (as is usual with subsets)
with arrays of size |V | with 0 and 1, 0 at position i representing the absence of
element i and 1 representing it presence. A variable e will indicate the depth
of the recursion call. When n = 1, we have completed a subset and then we
evaluate whether it is independent an, in case it is, whether it is larger than the
stored maximal set. The array s contains the subset being constructed and the
array xMax contains the maximal independent set found so far.
At each stage e, a cycle controlled by a variable i ranging from 0 to 1 decides
whether node e will be included (i = 1) or excluded (i = 0) from the subset.

10
(b) The pseudo code is written below.

1. Algorithm MaxIndep {
2. Input: G: graph; // A graph G = (V, E)
3. Output: array [|V |]; // The max. ind. set
4. S, SMax initialize array [|V |] of int; // Current and max. ind. set
5. for (i = 0; i < |V |; i + +) {; // Set S & SMax to 0
6. S[i] = 0;
7. SMax[i] = 0;
8. }
9. MaxIndepRec(G, S, SMax, 0, 1); // The true recursive method
10. return SMax;
11. }
12. Algorithm MaxIndepRec { // The main recursive method
13. Input: G: graph; // The graph
14. S: array [|V |] of int; // The set being constructed
15. SMax: array [|V |] of int; // Max. ind. set found so far
16. mx, s: int; // Maximal length and stage
17. Output: void
18. for (i = 0; i < 2; i + +) { // The main loop
19. if (s == |V |) { // Subset complete?
20. int len = Indep(G,S);
21. if (len > mx) { // Larger ind. set found
22. mx = len; // Replacement procedure
23. for (i = 0; i < |V |; i + +)
24. SMax[i] = S[i];
25. } // Replacement complete
26. } else { // Subset not yet complete
27. MaxIndepRec(G, S, SMax, mx, s + 1) { // Recursive call
28. }
29. }
30. }
31. Algorithm Indep { // Determines if S is ind. set
32. Input: G: graph;
33. S: array [|V |] of int; // The candidate ind. set
34. Output: int; // Size of ind. set; 0 if not ind.
35. size = 0;
36. for (i = 0; i < |V |; i + +) {
37. if (S[i] == 1) {
38. size++
39. for (j = i + 1; j < |V |; j + +) {
40. if (S[j] == 1) {
41. if G.existsEdge(i, j) {
42. return 0; // Not independent
43. }
44. }
45. }
45. }
45. }
46. return size; // Size of independent set found
47. }

11
7 Rabbit in a Maze
A maze is given as a binary matrix of blocks M of size n × n where the entry
is the upper left most block (M [0, 0]) and the exit block is the lower rightmost
block (M [n − 1, n − 1].) A rabbit enters the labyrinth (at the entry point, of
course) and has to reach the exit to escape. The rabbit can move only in two
directions: forward and down. In the maze matrix, 0 means the block is a dead-
end and non-zero number means the block can be used in the path from entry
to exit. The non-zero value of M [i, j] indicates the maximum number of jumps
that the rabbit can make from from it, downwards or rightwards.

Some examples:

2 1 0 0 1 0 0 0
3 0 0 1 1 0 0 1
0 1 0 1 0 0 0 1
0 0 0 1 0 0 0 1

no solution

You are kindly asked to:

1. Establish a backtracking to decide whether the rabbit can escape from a
given maze.

2. Write the pseudo-code that realizes your strategy and calculate the com-
plexity thereof.

Solution

(a) The strategy, as is always the case with backtracking, is fairly basic: we just
try every possible path until we find the good one or exhaust all possibilities.
In this case, we begin at position M [0, 0]. A standard way to solve this kind of
problems is to use a matrix S the same size of the labyrinth. Each element of
this matrix is marked as 0 at the beginning. Each cell we visit is marked as 1.
The skeleton of the algorithm is shown next.
• If we reach the destination cell and it is M [n − 1, n − 1] 6= 0, we mark is
as S[n − 1, n − 1 = 1, print the solution matrix, and return true.

• Otherwise, we mark the current position in S as 1 and try all possible

moves. If none of these work (all return false), we mark the cell as 0 and
return false, thus forcing backtracking.

12
(b) The pseudo-code is shown next.

1. Algorithm Maze {
2. Input: M : matrix [n, n] of int;
3. Output: boolean; // The rabbit escapes
4. S initialize matrix [n, n] of int;
5. for (i = 0; i < n; i + +) { // Set all cells of S to 0
6. for (j = 0; j < n; j + +) {
7. S[i, j] = 0;
8. }
9. }
10. return Rabbit(M , S, 0, 0);
11. }
12. Algorithm Rabbit { // The main recursive method
13. Input: M : matrix of int [n, n]; // The maze
14. i, j: int; // The current position
15. S: matrix of int [n, n]; // The solution matrix
16. Output: boolean; // The rabbit escapes
17. boolean (solved = false;
18. int k = 1;
18. if (isOK(M, i, j)) { // Verifies the current position
19. S[i, j] = 1; // Temporarily marked as OK
20. while (k ≤ M [i, j] && !solved) {
21. if (Rabbit(M, i + k, j, S) { // We try rightwards first
22. solved = true;
23. } else if (Rabbit(M, i, j + k, S) { // We try downwards now
24. solved = true;
25. }
26. k + +;
27. }
28. if (!solved) // It didn’t work
29. S[i, j] = 0 // We unmark the solution
30. }
31. return solved;
32. }
33. Algorithm IsOK { // Verifies if a position is safe
34. Input: M : matrix of int [n, n]; i, j: int;
35. Output: boolean; // Position (i, j) is safe
36. return (i ≤ n && j ≤ n && M [i, j] 6= 0);
37. }

Complexity is calculated according to the number of recursive calls. We have

that, since both i and j are increased, when both of them reach n the process
terminates. We have thus recursion with subtraction. In the worst case there
are 2n recursive calls and b = 1 (worst case, again.) We have thus O(nn ). This
is a horrible complexity, which corresponds to the worst case.

13
8 Complexity
To solve some non-specified problem you are given the choice among three al-
gorithms:

• Algorithm A solves the problem dividing it in five sub-problems of half

the size, solving recursively each sub-problem and combining the solutions
in linear time.
• Algorithm B solves the problem of size n solving recursively two sub-
problems of size n − 1 and combining them in constant time.

• Algorithm C solves a problem of size n dividing it into nine sub-problems of

size n/3, solving recursively each sub-problem and combining the solutions
in quadratic time.
Which is the complexity of each one of these algorithms and which one would
you choose?

Solution

We have the following complexities:

• Algorithm A: this is a case of recursion with division. We have a = 5,
b = 2 and k = 1. Therefore, a = 5 > 21 = bk and thus we get O(nlogb a ) =
O(nlog2 5 ).

• Algorithm B: this a case of recursion with subtraction. We have a = 2,

b = 1 and k = 0. Hence O(nk an/b ) = O(2n ).
• Algorithm C: this is a case of recursion with division. We have a =
9, b = 3, and k = 2. Therefore a = 9 = 32 = bk and we get hence
O(nk log n) = O(n2 log n).

Of course, algorithm B is eliminated in the first selection, because it has an

unacceptable complexity (exponential.) The other two are plausible. Algorithm
A has a larger exponent (log2 5 ∼
= 2.322), but algorithm C has the log n factor.
As usual, we have to determine which function increases faster. We take limit
for n → ∞.
n2.322 n0.322 n
lim = lim = 0.322 lim 0.678 = 0.322 lim n0.322 = ∞
n→∞ n2 log n n→∞ log n n→∞ n n→∞

The best algorithm is therefore C.

14