Algorithm exercises

Problem representation Solution Results Conclusion

Exercise 01 1.​ Initialisation des bornes: gauche Cas 1 : l’element recherche Complexite temporelle:
=0 et droite = taille_liste -1 est dans la liste ●​ O(1): la valeur est
2.​ Tant que gauche <= droite trouvee au milieu
●​ Calculer milieu = gauche + ●​ Input: ●​ O(log(n)): A chaque
(droite - gauche) /2 Entrez la taille de la liste: 7 iteraation, la liste est
●​ Comparer liste[milieu] reduite de moitie,
avec la valeur rechercher Entrez les elements de la facilitant la
○​ Si c’est egal -> liste (tries): 2 4 6 9 10 11 12 recherche
element trouve,
retourne l’index Entrez la valeur a Avantage: cet algorithme a
○​ Si c’est inferieur, rechercher: 10 une bonne complexite plus
on cherche dans rapide que la recherche
la partie droite lineaire
○​ Sinon on cherche ●​ Output:
dans la partie Valeur trouvee a l’index 4 Inconvenient: la liste doit
gauche deja etre triees
3.​ Si on sort de la boucle sans Cas 2: l’element recherche
trouver l’element, retourner -1 n’est pas dans la liste

●​ Input:
Entrez la taille de la liste: 7

Entrez les elements de la

liste (tries): 2 4 6 9 10 11 12

Entrez la valeur a
rechercher: 8

●​ Output:
 Valeur non trouvee dans le
tableau

Exercise 02 ●​ BFS ●​ Input Complexite temporelle:

1.​ Ajouter le sommet de depart dans
une file Entrez le nombre de ●​ BFS: O(V+E) ou V:
2.​ Explorer tous ses voisions non sommets: 5 sommets et E:
encore visites Entrez le nombre d'arêtes: 4 aretes
3.​ Les ajouter a la file et marquer Entrez les arêtes (paires de
comme visites sommets) :
4.​ Continuer jusqu’a ce que la file soit 01
vide 12
03
34
●​ DFS Entrez le sommet de départ
1.​ Marquer le sommet actuel comme pour (BFS/DFS): 0
visite
2.​ Afficher le sommet ●​ Output
3.​ Explorer recursivement tous ses Parcours BFS: 0 1 3 2 4
voisins non encore visites Parcours DFS: 0 1 2 3 4
4.​ Revenir en arriere si tous les
voisins ont ete visites

●​ ShortestBFS
1.​ Initialiser le graphe
2.​ Calculer le plus court chemin en
utilisant BFS
3.​ Suivre les parent
4.​ Reconstruire le chemin

Exercise 03 1.​ Declarer une table 2D (dp[i][w], ou ●​ Input: Complexite temporelle:

i est l’objet considere, w la Entrez le nombre d’objets: 3 O(n*W) ou n est le nombre
capacite actuelle du sac et dp[i][w] d’objet et W la capacite du
est la valeur maximale atteignable Objet 1 - valeur: 60 sac
2.​ Remplir la table DP Objet 1 - poids: 10
●​ Cas 1: l’objet peut etre Objet 2 - valeur: 100 Avantage: resout le
inclus Objet 2 - poids: 20 probleme de maniere
●​ Cas 2: l’objet depasse la Objet 3 - valeur: 120 optimale en trouvant la
 capacite et dans ce cas on Objet 3 - poids: 30 meilleure combinaison
ignore
3.​ Retracer les objets choisis Entrez la capacite maximale Inconvenient: si n ou W sont
du sac: 50 tres grands, la memoire et le
temps d’execution
augmentent
●​ Output: considerablement
Valeur maximale pouvant
etre obtenue: 220
Objets selectionnes (index):
[2,1]

On selectionne l’objet 2
(100) et l’objet 3 (120),
sachant que l’index
commence a 0

Exercise 04 1.​ Trier les intervalles en fonction du ●​ Input: Complexite temporelle:

temps de debut Entrez le nombre O(n log(n)) grace au tri
2.​ Initialiser une liste “merged” avec d'intervalles: 4 effectue au debut
le premier intervalle Intervalle 1 -> Début: 1
3.​ Iterer sur la liste des intervalles et Intervalle 1 -> Fin: 3 Inconvenient: ne fonctionne
comparer chaque intervalle avec le Intervalle 2 -> Début: 2 qu’avec les intervalles ayant
dernier “merged” Intervalle 2 -> Fin: 6 des valeurs entieres
●​ Si chevauchement: Intervalle 3 -> Début: 8
fusionner(max(fin1, fin2)) Intervalle 3 -> Fin: 10
●​ Sinon ajouter un nouvel Intervalle 4 -> Début: 15
intervalle a “merged” Intervalle 4 -> Fin: 18

●​ Output
Intervalles fusionnes:
[1,6], [8,10], [15,18]
Exercise 05 1.​ Initialiser somMax = tab[0] et ●​ Input: Complexite temporelle:
somActuelle = tab[0] Entrez la taille du tableau: 9 O(n)
2.​ Parcourir le tableau a partir du 2nd Entrez les éléments du
element tableau: Inconvenient: ne fonctionne
●​ Soit continuer avec le 3 -1 -2 4 -1 2 1 -5 4 qu’avec les valeurs entieres
sous-tableau actuel
(somActuelle + tab[i]) ●​ Output
●​ Soit demarrer un nouveau La somme maximale d'un
sous-tableau (tab[i]) sous-tableau est : 6
●​ Mettre a jour somMax si
somActuelle est plus
grande