Automne 2019-ITCS-8114-Algods
Ce référentiel contient les projets et les affectations bien sûr "ITCS 6114/8114: algorithmes et structures de données" . Ce cours a été suivi au semestre de l'automne 2019, dans le cadre de mon doctorat à l'UNC Charlotte.
Liste de projets
- Projet 1: Algorithmes de tri basés sur la comparaison
- Projet 2: Algorithmes graphiques (Chemin le plus court et arbre couvrant minimum)
- Projet 3: Algorithmes de correspondance de motifs
Vous trouverez ci-dessous la description et les exigences des projets. Pour obtenir les détails, veuillez accéder au répertoire de projet correspondant.
Projet 1: Algorithmes de tri basés sur la comparaison
Implémentez les algorithmes de tri suivants et comparez-les. Vous pouvez utiliser n'importe quel langage de programmation (par exemple C / C ++, Java, Python, C #). Dans ce projet, vous pouvez travailler seul ou en équipe de deux.
- Tri insertion
- Fusion
- HEAPSORT [Vector basé sur un vecteur et insérer un élément à la fois]
- Quicksort en place (tout élément aléatoire ou le premier ou le dernier élément de votre entrée peut être pivot).
- Quicksort modifié
- Utilisez la médiane de trois comme pivot.
- Pour un petit sous-problème de taille <= 10, utilisez le tri d'insertion.
Instructions d'exécution:
- Exécutez ces algorithmes pour différentes tailles d'entrée (par exemple n = 1000, 2000, 4000, 5000, 10000 .. 40000, 50000). Vous générerez des nombres au hasard pour votre tableau d'entrée. Enregistrez le temps d'exécution (besoin de prendre la moyenne comme discuté dans la classe) et tracez-les tous dans un seul graphique par rapport à la taille de l'entrée. Notez que vous comparerez ces algorithmes de tri pour le même ensemble de données.
- Observez également et présentent les performances des deux cas spéciaux suivants:
- Le tableau d'entrée est déjà trié.
- Le tableau d'entrée est trié réversement.
Schéma de classement:
Instructions de soumission:
- Téléchargement de la toile
- Un rapport bien formaté couvrant les structures de données choisies, l'analyse de complexité, les résultats et le code.
- Téléchargez le code du programme pour l'exécution. Assurez-vous de fournir une lecture pour TA.
- De plus, la copie papier du rapport sans code dans la classe.
Projet 2: Algorithmes graphiques (Chemin le plus court et arbre couvrant minimum)
Dans ce projet, vous implémenterez deux algorithmes graphiques mentionnés ci-dessous. Remarque: vous pouvez travailler seul ou dans une équipe de deux max.
Problème 1: Trouvez l'arbre de chemin le plus court dans les graphiques pondérés dirigés et non dirigés pour un sommet source donné. Supposons qu'il n'y a pas de bord négatif dans votre graphique. Vous imprimerez chaque chemin et le coût du chemin pour une source donnée.
Problème 2: Étant donné un graphique connecté, non dirigée et pondéré, trouvez un arbre couvrant en utilisant des bords qui minimise le poids total? (?) = ∑ (u, v) ∈T ? (?,?). Utilisez l'algorithme de Kruskal pour trouver un arbre couvrant minimum (MST). Vous imprimerez les bords de l'arbre et le coût total de votre réponse.
Format d'entrée: pour chaque problème, vous prenez les entrées à partir d'un fichier texte. Dites que vous souhaitez exécuter un algorithme sur le graphique non dirigé suivant. Le format de fichier correspondant serait:
6 10 U
A B 1
A C 2
B C 1
B D 3
B E 2
C D 1
C E 2
D E 4
D F 3
E F 3
A
Ici, les deux premiers nombres représentent le nombre de sommets et de bords. La lettre U signifie Graph non dirigée (D pour dirigé). De la deuxième ligne, il mentionne tous les bords et son poids (par exemple ???? (?,?) Et son poids est 1. La dernière ligne est facultative. Si elle est donnée, il représente le nœud source.
Instructions de soumission:
- Un rapport bien formaté couvrant une brève description de chaque algorithme, la structure de données choisie, l'exécution de votre code, l'exemple d'entrée / sortie, des instructions pour exécuter votre programme facilement.
- Pour chaque problème, exécutez votre programme pour quatre graphiques différents de votre choix. Utilisez votre jugement pour définir des graphiques de test que vous pensez intéressants et raisonnables. Par exemple:
- Graphique non dirigée: au moins 7 nœuds et 12 bords
- Graphique réalisé: au moins 7 nœuds et 15 bords
- Nettoyer le code pour l'exécution de TA.
- Vous pouvez utiliser n'importe quel langage de programmation (par exemple C / C ++, Java, Python, etc.)
- S'ils ont travaillé dans une équipe, les deux membres sont tenus de tout soumettre séparément.
- Copie de votre rapport directement; une copie par équipe.
Schéma de classement:
Projet 3: Algorithmes de correspondance de motifs
Remarque: vous pouvez travailler seul ou dans une équipe de trois max.
Pour cette affectation, vous n'implémerez que trois algorithmes de correspondance de motifs de votre choix dans la liste ci-dessous.
- Algorithme de force brute
- Algorithme de Boyer-Moore-Horspool
- Algorithme Knuth-Morris-pratt
- Algorithme de Boyer-Moore
- Automatisation finie pour la correspondance des modèles
Expérience:
- Comparez trois algorithmes pour plusieurs textes et modèles d'entrée différents; Au moins 10 cas différents
- Mentionnez le nombre de comparaisons requises dans un tableau pour chaque cas, pour chaque algorithme
Soumission:
- Un rapport bien formaté couvrant une description courte de chaque algorithme, la structure de données utilisée, l'exécution de votre code, l'exemple d'entrée / sortie, des instructions pour exécuter votre programme facilement.
- Nettoyer le code pour l'exécution de TA.
- Vous pouvez utiliser n'importe quel langage de programmation (par exemple C / C ++, Java, Python, etc.)
- S'ils ont travaillé dans une équipe, les deux membres sont encore tenus de tout soumettre séparément.
- Clissé de votre rapport directement; une copie par équipe.
Schéma de classement:
- 3 x 15 = 45 points: pour implémenter trois algorithmes
- 20 points: pour l'expérience
- 10 points: Rapport
