Introduction to computer science, practical sessions

TP1

tp01.pdf

Extra information for the bonus exercise

To implement model 1 you can compute a random permutation sigma of the edges and use Kurskal's algorithm (video) with sigma as the weights.

To implement model 2 you need to understand the Prüfer sequence and implement the prüfer-to-tree algorithm.

To implement diameter you can pick a node n1 randomly; find n2, the farthest node from n1 (for example using Dijkstra's algorithm); and then compute n3 the farthest node from n2. d(n2,n3) is the diameter of the tree.

Super bonus: prove the algorithm given above for the diameter.

TP2

tp02.pdf

1.1.2: Let us consider an input list sorted in reversed order. Each time the algorithm searches for the minimum it will be the last element of the list and thus it costs l where l is the number of remaining elements in the list. Overall sorting such a list with selection sort costs n+(n-1)+...+1 = n*(n-1)/2 which is quadratic.

TP3

tp03.pdf

1.1: In the worst case, the string will be the last m-substring of the text. In this case, there will be n-m+1 substring comparisons for a total of m*(n-m+1) comparisons.

2.2: Each character from the text is read exactly once and results in a O(1) comparisons (maximum arity of a node in the automaton) thus complexity is in O(n)

3.4: Let us consider the string "baaaa...aaa" with m-1 'a' and one 'b'. Let us consider the text "aaaa...aaaaaaabaaaaa...aaa" with n-m 'a' then one 'b' and then m-1 'a' again. Boyer-Moore will start comparing substrings starting from the last character of the string. Since the beginning of the text is composed solely of 'a's each substring comparison will take m comparisons. After an unsuccessful comparison, the mismatched character is an 'a' and since 'a' is the last character from the string it would result in a backward move. In this case, the algorithm moves one step forward instead.
Thus, the first n-m 'a's of the text will require (n-m)*(m) comparisons which is indeed in O(n*m).

TP4

tp04.pdf

TP5

tp05.pdf

Solutions for TP4 and TP5

corrige.pdf

Proof that DFS gives a correct topological order.
Proof that a topological order exists iff the graph is a DAG.