Aller au contenu principal

Compétition Kaggle : Survivants du Titanic

Quentin Fortier
Quentin Fortier
Professeur d'informatique

Vous pouvez utiliser ce Codespace pour la compétition d'apprentissage automatique sur les survivants du Titanic. Voir la description dans le README. Le lien vers la compétition Kaggle vous a été envoyé par mail. La compétition est ouverte jusqu'au 22 février au soir.

TD 15/01

Quentin Fortier
Quentin Fortier
Professeur d'informatique

TD "Algorithmes probabiliste", exercice 1. À préparer pour la semaine prochaine : exercice 2.

LeetCode 5

Quentin Fortier
Quentin Fortier
Professeur d'informatique

Deux exercices LeetCode pour ces vacances.

Indice 1er exercice

Parcourir chaque indice du tableau en conservant la somme maximale se terminant à cet indice.

Indice 2ème exercice

Utiliser un algorithme par programmation dynamique en calculant b[i][j] qui vaut vrai si la sous-chaîne d'indice i à j est un palindrome.

Solution
int maxSubArray(int* nums, int numsSize) {
    int maxi = nums[0], max_cur = nums[0];
    for(int i = 1; i < numsSize; i++) {
        // invariant : max_cur est la somme consécutive max qui se termine en i
        max_cur = max_cur + nums[i];
        if(max_cur < nums[i])
            max_cur = nums[i];
        if(max_cur > maxi)
            maxi = max_cur;
    }
    return maxi;
}
Solution
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* subword(char* s, int i, int j) {
    char* t = malloc(j - i + 2);
    for(int k = i; k <= j; k++)
        t[k - i] = s[k];
    t[j - i + 1] = '\0';
    return t;
}

char* longestPalindrome(char* s) {
    int n = strlen(s);
    bool** b = malloc(n*sizeof(bool*));
    for(int i = 0; i < n; i++) {
        b[i] = malloc(n*sizeof(bool));
        for(int j = 0; j < n; j++) {
            b[i][j] = true;
        }
    }

    int imax = 0, kmax = 0;
    for(int k = 1; k < n; k++)
        for(int i = 0; i < n - k; i++) {
            b[i][i + k] = s[i] == s[i + k] && b[i + 1][i + k - 1];
            if(b[i][i + k]) {
                kmax = k;
                imax = i;
            }
        }
    return subword(s, imax, imax + kmax);
}

TD 15/12

Quentin Fortier
Quentin Fortier
Professeur d'informatique
  • Fin TD "Décidabilité et complexité".
  • En MPI* : TD "Algorithme d'approximation" exo 1.

À faire pendant les vacances :

  • DM CCP

LeetCode 4 : Find Edges in Shortest Paths

Quentin Fortier
Quentin Fortier
Professeur d'informatique

Exercice à faire en C sur LeetCode cette semaine : https://leetcode.com/problems/find-edges-in-shortest-paths/description/

Il y a deux indices en bas de la page (Hint).

Details

Indice Pour passer tous les tests, il faut implémenter l'algorithme de Dijkstra ce qui demande une file de priorité (tas min) et est un peu long à implémenter... On pourrait implémenter Floyd-Warshall ou Bellman-Ford à la place.

Solution
#include <stdbool.h>

int** createGraph(int n, int** edges, int edgesSize, int* edgesColSize) { // matrice d'adjacence
    int **g = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        g[i] = (int*)malloc(n * sizeof(int));
        for (int j = 0; j < n; j++)
            g[i][j] = -1;
    }
    for (int i = 0; i < edgesSize; i++) {
        int a = edges[i][0];
        int b = edges[i][1];
        int w = edges[i][2];
        g[a][b] = w;
        g[b][a] = w;
    }
    return g;
}

int** floydWarshall(int n, int** g) {
    int** dist = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        dist[i] = (int*)malloc(n * sizeof(int));
        for (int j = 0; j < n; j++) {
            if (i == j)
                dist[i][j] = 0;
            else if (g[i][j] != -1)
                dist[i][j] = g[i][j];
            else
                dist[i][j] = 1e9;
        }
    }
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
    return dist;
}

bool* findAnswer(int n, int** edges, int edgesSize, int* edgesColSize, int* returnSize) {
    int** g = createGraph(n, edges, edgesSize, edgesColSize);
    int** dist = floydWarshall(n, g);
    bool* answer = (bool*)malloc(edgesSize * sizeof(bool));
    for (int i = 0; i < edgesSize; i++) {
        int a = edges[i][0];
        int b = edges[i][1];
        int w = edges[i][2];
        if (dist[0][a] + w + dist[b][n - 1] == dist[0][n - 1] ||
            dist[0][b] + w + dist[a][n - 1] == dist[0][n - 1])
            answer[i] = true;
        else
            answer[i] = false;
    }
    *returnSize = edgesSize;
    for (int i = 0; i < n; i++) {
        free(g[i]);
        free(dist[i]);
    }
    free(g);
    free(dist);
    return answer;
}