Séminaire 4 : Introduction au projet

Algorithmique et structures de données — Université de Genève

Objectifs d’apprentissage¶

À la fin de ce séminaire vous serez capable de :

Comprendre la portée du projet, les livrables et la notation
Télécharger et charger le jeu de données des montres connectées dans Python
Explorer les données de façon programmatique à l’aide de statistiques de base
Implémenter votre premier algorithme sur des données réelles (trouver le jour le plus actif)
Identifier trois analyses que vous implémenterez pour votre projet (une par niveau)

Partie 1 : Le projet¶

1. Objectif¶

Travailler avec des données réelles est bien plus gratifiant que des exemples synthétiques. Dans ce projet, vous travaillerez avec des données physiologiques collectées par le Quality of Life Lab auprès de douze personnes à l’aide de montres connectées Withings ScanWatch. Les données contiennent le nombre de pas mesurés par heure et par jour sur plusieurs mois.

Vous appliquerez les algorithmes présentés dans ce cours — tri, recherche, structures de données, récursion, programmation dynamique, graphes — pour répondre à des questions concrètes dérivées du jeu de données.

L’accent est mis sur :

Choisir des structures de données appropriées pour le problème posé
Implémenter correctement les algorithmes — pas seulement appeler les fonctions intégrées de pandas
Argumenter pourquoi votre solution est efficace (complexité temporelle et spatiale)
Écrire du code Python propre et testable avec un README documenté

Livrables et notation¶

Le projet compte pour 30 % de votre note finale :

Livrable	Poids	Date limite
Dépôt de code + `README.md`	15%	19 May 2026, 23:59
Revue de code par les pairs	15%	31 May 2026, 23:59
Total	30%	—

Grille de notation détaillée¶

Dépôt de code + README (15%)¶

Critère	Poids à l’intérieur des 15%	Attente pour le plein crédit
Correctitude	5%	Sorties correctes sur cas normaux et cas limites
Raisonnement algorithmique	4%	Choix clair de structure de données/algorithme + complexité justifiée
Tests	2%	Tests pertinents, incluant cas limites
Qualité du README	3%	Explication claire pour chaque analyse
Qualité du code	1%	Code lisible, structuré, conforme à PEP-8

Revue de code par les pairs (15%)¶

Critère	Poids à l’intérieur des 15%	Attente pour le plein crédit
Couverture	5%	Couvre toutes les analyses requises et le README
Exactitude technique	5%	Commentaires corrects sur la justesse, la complexité, les tests
Feedback actionnable	3%	Suggestions spécifiques avec corrections concrètes
Professionnalisme	2%	Ton respectueux et structure claire

Définition du “Done” (exigences minimales)¶

Votre soumission est considérée comme complète uniquement si tout est vrai :

Au moins 3 analyses : 1 Débutant + 1 Intermédiaire + 1 Avancé
Chaque analyse implémentée sous forme de fonction(s) Python propres
Tests pour les fonctions centrales (incluant cas limites)
Section README par analyse : problème, algorithme, pourquoi, complexité
Instructions de reproduction dans le dépôt
researchdata/ est dans .gitignore (pas de données privées commitées)

2. Installation avec le jeu de données fourni (obligatoire)¶

Cette installation est requise pour tout le monde. Toutes les tâches du projet et la notation peuvent être accomplies en utilisant uniquement ces données.

2.0 Démarrage rapide (voir ci-dessous pour plus de détails)¶

Créez un nouveau dossier nommé “votre nom - ALG project”
Créez/activez votre environnement virtuel
Téléchargez et extrayez l’archive. Les données brutes seront disponibles dans researchdata/
Ajoutez researchdata/ et les autres dossiers extraits par yareta à un .gitignore
Exécutez l’Exercice 1 et confirmez que vous pouvez charger un CSV
Exécutez l’Exercice 2 et générez merged.csv

2.1 Télécharger les données¶

Le jeu de données des montres connectées provenant de 12 participants anonymisés est disponible sur Yareta :

https://yareta.unige.ch/archives/19bf7f3c-7d07-48be-8c03-9f754f766906

Téléchargez l’archive et extrayez-la dans votre répertoire de projet :

project/
  └── researchdata/
        ├── 1487.csv
        ├── 1488.csv
        └── ...  (12 files total)

⚠️ Ajoutez researchdata/ à votre .gitignore. Les données sont privées — ne les commitez jamais dans git.

Avant de commencer à coder, lisez la documentation fournie pour comprendre les données :

Qui a contribué les données (organisation et nom) ?
Quelle est la taille de l’échantillon ?
Combien de jours de données ont été collectés par participant ?

2.2 Charger les données dans Python¶

Les fichiers sont au format CSV. Utilisez pandas pour les charger :

import pandas as pd

# Load a single participant's data
df = pd.read_csv("researchdata/1487.csv")

print("Shape:", df.shape)
print("\nFirst 5 rows:")
print(df.head())

print("\nColumn names:", df.columns.tolist())
print("\nData types:")
print(df.dtypes)

Partie 2 : Exercices¶

Exercice 1 — Charger le jeu de données et afficher des statistiques de base¶

Chargez un fichier d’un participant (par ex. 1487.csv) et répondez à ces questions en utilisant pandas :

Combien de lignes et de colonnes contient-il ?
Quels sont les noms des colonnes et leurs types de données ?
Affichez la sortie de df.describe() — que remarquez-vous au sujet des nombres de pas ?
Y a-t-il des valeurs manquantes ? (df.isnull().sum())

Rédigez une courte observation (3–4 phrases) sur ce que vous observez dans les données.

Preuves attendues avant de continuer :

capture d’écran ou sortie collée de shape, des colonnes, de describe(), des valeurs manquantes
votre observation en 3–4 phrases

import pandas as pd

# Load one participant
df = pd.read_csv("researchdata/1487.csv")

# --- YOUR CODE HERE ---
# 1. Print shape

# 2. Print column names and data types

# 3. Print describe()

# 4. Check for missing values

(Écrivez ici votre observation de 3–4 phrases.)

Exercice 2 — Aplatir tous les fichiers participants dans `merged.csv`¶

Chargez les 12 fichiers CSV du dossier researchdata/, ajoutez une colonne participant_id (nom de fichier sans .csv), et concaténez-les en un seul fichier merged.csv.

Après l’enregistrement, vérifiez :

Combien de lignes contient merged.csv ?
Combien de participants uniques y a-t-il ?

Preuves attendues avant de continuer :

merged.csv existe à la racine de votre projet
affichage du nombre total de lignes et du nombre de participants (devrait être 12 participants)

import pandas as pd
import os

# TODO: Load all CSV files from researchdata/,
# add participant_id column, concatenate and save to merged.csv.

dfs = []

for filename in os.listdir("researchdata"):
    if filename.endswith(".csv"):
        # --- YOUR CODE HERE ---
        pass

# Concatenate all DataFrames
merged = pd.concat(dfs, ignore_index=True)

# Save
merged.to_csv("merged.csv", index=False)

print(f"Total rows:       {len(merged):,}")
print(f"Participants:     {merged['participant_id'].nunique()}")
print(f"Columns:          {merged.columns.tolist()}")

Exercice 3 — Explorer les données manuellement¶

En utilisant merged.csv, calculez ce qui suit sans appeler df.max(), df.min() ou df.mean(). Utilisez des boucles explicites pour pratiquer la réflexion algorithmique :

Quel participant a le total de pas le plus élevé (somme de tous ses pas journaliers) ?
Quelle est la moyenne quotidienne de pas sur toutes les lignes (tous participants confondus) ?
Quel est le minimum quotidien de pas, en ignorant les jours avec 0 pas ?

Indice : utilisez un dict pour accumuler les totaux par participant pour la question 1.

Preuves attendues avant de continuer :

résultats imprimés pour les trois questions
courte note (1–2 lignes) expliquant pourquoi votre approche en boucle est O(n)

import pandas as pd

merged = pd.read_csv("merged.csv")

# --- YOUR CODE HERE ---

# 1. Most active participant (total steps)


# 2. Average daily step count


# 3. Minimum daily step count (excluding 0-step days)

Exercice 4 — `find_most_active_day()`¶

Implémentez une fonction qui retourne la date avec le total de pas le plus élevé à travers tous les participants.

Contraintes :

Ne pas utiliser df.idxmax(), df.sort_values(), ou df.groupby() — implémentez la recherche manuellement.
Votre fonction doit s’exécuter en O(n) où n est le nombre de lignes.

Ce qu’il faut documenter dans votre README (exercez-vous maintenant) :

Problème : trouver le jour le plus actif parmi tous les participants
Algorithme : parcours linéaire, en conservant le maximum dans une variable courante
Pourquoi approprié : un seul passage sur les données, O(n) en temps, O(d) en espace (d = dates distinctes)
Complexité : O(n) temps, O(d) espace

Preuves attendues avant de continuer :

sortie de la fonction et vérification avec pandas affichées
un court paragraphe type README utilisant les 4 points ci‑dessus

import pandas as pd

merged = pd.read_csv("merged.csv")


def find_most_active_day(df: pd.DataFrame) -> tuple:
    """
    Return the date with the highest total step count across all participants.

    Do NOT use df.idxmax() or df.sort_values().
    Implement using a loop and a dictionary for date aggregation.

    Parameters
    ----------
    df : pd.DataFrame
        Must contain 'date' and 'steps' columns.

    Returns
    -------
    tuple : (date_str, total_steps) for the most active day

    Complexity
    ----------
    Time:  O(n) — one pass to aggregate, one pass to find max
    Space: O(d) — where d is the number of distinct dates
    """
    # Step 1: Aggregate total steps per date
    totals: dict = {}
    for _, row in df.iterrows():
        date = row["date"]
        steps = row["steps"]
        # --- YOUR CODE HERE ---
        pass

    # Step 2: Find the date with the maximum total
    # --- YOUR CODE HERE ---
    best_date = None
    best_steps = -1

    return best_date, best_steps


date, steps = find_most_active_day(merged)
print(f"Most active day: {date}")
print(f"Total steps:     {steps:,}")

# Cross-check with pandas (should agree)
check = merged.groupby("date")["steps"].sum().idxmax()
print(f"\nCross-check (pandas): {check}  →  {'✓ matches' if date == check else '✗ mismatch'}")

Exercice 5 — Plus longue série de jours actifs¶

Implémentez une fonction qui trouve la plus longue série consécutive de jours où le nombre de pas d’un participant est supérieur ou égal à un seuil donné (par défaut : 8 000 pas).

Ceci est un motif classique de la programmation dynamique :

Let streak[i] = longueur de la plus longue série active se terminant au jour i
Transition : streak[i] = streak[i-1] + 1 si steps[i] >= threshold, sinon 0
Réponse : max(streak[i] for all i)

Vous n’avez besoin que de garder la trace de la série courante — aucun tableau nécessaire.

Ce qu’il faut documenter dans votre README :

Problème : plus longue série de jours au-dessus d’un seuil de pas
Algorithme : DP avec un compteur courant (variante de l’algorithme de Kadane)
Pourquoi approprié : O(n) temps, O(1) espace additionnel — optimal pour un parcours séquentiel
Complexité : O(n) temps, O(1) espace

Preuves attendues avant de continuer :

les 4 tests fournis passent
une phrase expliquant pourquoi il s’agit de DP et non de force brute

def longest_streak(steps_per_day: list, threshold: int = 8000) -> int:
    """
    Return the length of the longest consecutive streak of days where
    step count >= threshold.

    Parameters
    ----------
    steps_per_day : list of int
        Daily step counts in chronological order.
    threshold : int
        Minimum steps to count as an active day (default: 8000).

    Returns
    -------
    int : length of the longest streak

    Complexity
    ----------
    Time:  O(n)
    Space: O(1)
    """
    # --- YOUR CODE HERE ---
    pass


# --- Tests ---
# Test 1: provided example
data1 = [9000, 7500, 8200, 8100, 9500, 6000, 8800, 9100, 7000, 8300]
result1 = longest_streak(data1, threshold=8000)
print(f"Test 1: {result1}  (expected 3 — days 2,3,4: 8200, 8100, 9500)")

# Test 2: all above threshold
data2 = [9000, 8500, 8100, 9500]
result2 = longest_streak(data2, threshold=8000)
print(f"Test 2: {result2}  (expected 4 — all days active)")

# Test 3: none above threshold
data3 = [5000, 6000, 7000]
result3 = longest_streak(data3, threshold=8000)
print(f"Test 3: {result3}  (expected 0 — no active days)")

# Test 4: empty input
result4 = longest_streak([], threshold=8000)
print(f"Test 4: {result4}  (expected 0 — empty input)")

3. Questions de projet que vous pouvez choisir de résoudre¶

Vous devez compléter au moins 3 analyses au total :

1 Débutant
1 Intermédiaire
1 Avancé

Vous pouvez choisir parmi les exemples ci‑dessous ou proposer vos propres questions.

3.1 Qu’est-ce qui définit chaque niveau ?¶

Le niveau est défini par la technique algorithmique utilisée, pas par le sujet.

Débutant (compétences Semaines 0–4) : boucles, conditionnels, listes/dicts, tri de base, comptages/agrégations simples.
Intermédiaire (compétences Semaines 5–7) : conception algorithmique structurée (ex. : fenêtre glissante, hachage pour recherches rapides, tri + recherche, approche de référence vs amélioration).
Avancé (Semaines 8+) : algorithmes sur graphes, programmation dynamique, ou choix d’optimisation/modélisation plus avancés avec justification claire.

3.2 Niveau Débutant (commencez à implémenter maintenant)¶

Objectif : Montrer une résolution de problème correcte avec du Python de base et une réflexion algorithmique élémentaire.

Exigences (toutes doivent être remplies) :

Résoudre une question clairement énoncée en utilisant une logique algorithmique explicite (pas seulement des one-liners de bibliothèque comme max(), min() ou pd.sort_values()).
Utiliser au moins une des techniques suivantes : parcours linéaire, comptage avec dict, agrégation manuelle, tri simple ou list comprehensions.
Indiquer la complexité de façon informelle (ex. « un seul passage sur les lignes -> O(n) »).

Exemples de questions (choisissez-en une ou développez la vôtre) :

Quelle date a le total de pas le plus élevé ?
Quel participant a la moyenne quotidienne de pas la plus élevée ?
Combien de jours chaque participant dépasse un seuil choisi (ex. 10 000 pas) ?
Classer les participants par total de pas en utilisant un tri de base (ex. tri à bulles).
Trouver le jour le plus actif de chaque participant (maximum avec parcours linéaire).

3.3 Niveau Intermédiaire (après le début des cours d’algorithmique, ~semaine 6)¶

Objectif : Comparer au moins deux approches et montrer pourquoi l’une est meilleure.

Exigences (toutes doivent être remplies) :

Implémenter une technique intermédiaire (ex. : fenêtre glissante, recherche rapide par hachage, tri + recherche binaire).
Inclure une approche de référence (baseline) et une approche améliorée.
Expliquer la complexité de chacune et justifier l’amélioration.

Exemples de questions (choisissez-en une ou développez la vôtre) :

Détecter des tendances sur 7 jours dans l’activité en utilisant une moyenne mobile (fenêtre glissante).
Détecter des jours anormalement actifs/inactifs en utilisant une règle et une stratégie de recherche efficace.
Classer les utilisateurs selon plusieurs métriques et comparer deux implémentations de classement.
Trouver des motifs d’activité répétés sur des fenêtres fixes (boucles imbriquées de base vs méthode optimisée).
Interroger les « top-k days » par participant (tri complet en baseline vs stratégie plus efficace).

3.4 Niveau Avancé (plus tard dans le cours, ~semaine 8+)¶

Objectif : Modéliser le problème avec un paradigme algorithmique plus poussé.

Exigences (toutes doivent être remplies) :

Utiliser au moins une méthode avancée (parcours de graphe, plus court chemin, programmation dynamique, etc.).
Justifier pourquoi ce choix de modélisation convient à la question.
Indiquer clairement la complexité temporelle et spatiale.

Exemples de questions (choisissez-en une ou développez la vôtre) :

Plus longue série active sous une définition donnée (formulation de style DP).
Construire un graphe de similarité entre participants et trouver communautés/composantes (BFS/DFS).
Modéliser les transitions d’état d’activité et calculer les transitions de coût minimal (style Dijkstra).
Détecter le segment de motif le plus stable sous contraintes (DP ou suivi d’états optimisé).
Comparer une approche basée sur graphe vs une baseline non‑graphe pour une question de relations.

3.5 Proposer votre propre question (fortement encouragé)¶

Vous êtes fortement encouragé·e à proposer votre propre question d’analyse.

Pour classifier votre question, vérifiez :

Technique : Quelle idée algorithmique du cours nécessite-t-elle ?
Complexité : Pouvez-vous expliquer runtime/espace de manière significative ?
Preuves : Pouvez-vous montrer des résultats sur le jeu de données fourni ?
Comparaison : (Intermédiaire/Avancé) Pouvez-vous comparer à une approche baseline plus simple ?

Si ces éléments sont clairs, votre question personnalisée est valide.

Exemple de README¶

Vous pouvez trouver un exemple de soumission avec une mise en page possible d’un README ici.

4. Optionnel : Utiliser vos propres données Withings¶

Cette section n’est pas obligatoire. Elle vous permet d’exécuter vos algorithmes sur vos propres données d’activité et de vous comparer à la cohorte.

Étape 1 : Installer l’application Withings¶

Téléchargez Withings Health Mate depuis l’App Store ou Google Play et créez un compte. Assurez‑vous que la synchronisation avec les capteurs de votre téléphone est activée.

Étape 2 : Authentification OAuth¶

Withings requiert OAuth 2.0 pour accéder à vos données personnelles. Exécutez le script ci‑dessous pour compléter le flux d’authentification. Vous devrez fournir une URL de callback — utilisez cette page hébergée :

https://withings-token-show.lovable.app/

Étape 3 : Exécuter le script d’authentification¶

# withings_auth.py — save this to a file and run: python withings_auth.py
# This cell only prints the script content; it does not execute OAuth.

import json, random, webbrowser, requests

CLIENT_ID       = "549043381e026880160c3f4c34984c8d7677df0d9acf73cc4e629c2fb938e3fe"
CONSUMER_SECRET = "ed922958cb33597d6c8f536b8c9c779460904a12d9edc9436a1f8fb7ea84b04b"
CALLBACK_URL    = "https://withings-token-show.lovable.app/"
AUTH_URL        = "https://account.withings.com/oauth2_user/authorize2"
TOKEN_URL       = "https://wbsapi.withings.net/v2/oauth2"
SCOPE           = "user.activity"
CONFIG_FILE     = "config.json"

def main():
    url = (f"{AUTH_URL}?response_type=code&client_id={CLIENT_ID}"
           f"&redirect_uri={CALLBACK_URL}&scope={SCOPE}"
           f"&state={random.randint(0, 999999999)}")
    print("Opening browser for Withings login...")
    webbrowser.open(url)
    code = input("\nPaste the code you received: ").strip()
    data = {"action": "requesttoken", "grant_type": "authorization_code",
            "client_id": CLIENT_ID, "client_secret": CONSUMER_SECRET,
            "code": code, "redirect_uri": CALLBACK_URL}
    resp   = requests.post(TOKEN_URL, data=data)
    resp.raise_for_status()
    tokens = resp.json()["body"]
    config = {"client_id": CLIENT_ID, "consumer_secret": CONSUMER_SECRET,
              "access_token": tokens["access_token"],
              "refresh_token": tokens["refresh_token"],
              "userid": tokens["userid"]}
    with open(CONFIG_FILE, "w") as f:
        json.dump(config, f, indent=2)
    print(f"Tokens saved to {CONFIG_FILE}")
    print("Important: add config.json to your .gitignore!")

if __name__ == "__main__":
    main()

Résumé¶

Sujet	Principale idée à retenir
Notation	30% au total : 15% code + 15% revue par les pairs avec grilles explicites
Définition du “Done”	3 analyses (D/I/A) + tests + README + dépôt reproductible
Jeu de données	Withings ScanWatch, 12 participants, dossier local `researchdata/`
README	Pour chaque analyse : problème · algorithme · pourquoi · complexité
Confidentialité des données	Ne jamais committer les fichiers `researchdata/`
Revue par les pairs	Semaine 12, feedback technique spécifique et actionnable

Actions à faire avant le prochain séminaire¶

Télécharger le jeu de données, compléter l’Exercice 1 et enregistrer vos observations
Construire merged.csv à partir de tous les participants (Exercice 2)
Compléter au moins une analyse Débutant avec des tests
Rédiger une section d’analyse de type README en utilisant l’exemple travaillé

Université de Genève — Algorithmique et structures de données

Objectifs d’apprentissage¶

Partie 1 : Le projet¶

1. Objectif¶

Livrables et notation¶

Grille de notation détaillée¶

Dépôt de code + README (15%)¶

Revue de code par les pairs (15%)¶

Définition du “Done” (exigences minimales)¶

2. Installation avec le jeu de données fourni (obligatoire)¶

2.0 Démarrage rapide (voir ci-dessous pour plus de détails)¶

2.1 Télécharger les données¶

2.2 Charger les données dans Python¶

Partie 2 : Exercices¶

Exercice 1 — Charger le jeu de données et afficher des statistiques de base¶

Exercice 2 — Aplatir tous les fichiers participants dans merged.csv¶

Exercice 3 — Explorer les données manuellement¶

Exercice 4 — find_most_active_day()¶

Exercice 5 — Plus longue série de jours actifs¶

3. Questions de projet que vous pouvez choisir de résoudre¶

3.1 Qu’est-ce qui définit chaque niveau ?¶

3.2 Niveau Débutant (commencez à implémenter maintenant)¶

3.3 Niveau Intermédiaire (après le début des cours d’algorithmique, ~semaine 6)¶

3.4 Niveau Avancé (plus tard dans le cours, ~semaine 8+)¶

3.5 Proposer votre propre question (fortement encouragé)¶

Exemple de README¶

4. Optionnel : Utiliser vos propres données Withings¶

Étape 1 : Installer l’application Withings¶

Étape 2 : Authentification OAuth¶

Étape 3 : Exécuter le script d’authentification¶

Résumé¶

Actions à faire avant le prochain séminaire¶

Exercice 2 — Aplatir tous les fichiers participants dans `merged.csv`¶

Exercice 4 — `find_most_active_day()`¶