Fall 2019 ITCS 8114 AlgoDS

FALL-2019-ITCS-8114-ALGODS

Este repositório contém os projetos e atribuições, é claro, "ITCS 6114/8114: algoritmos e estruturas de dados" . Este curso foi realizado no semestre do outono de 2019, como parte do meu doutorado na UNC Charlotte.

Lista de projetos

• Projeto 1: Algoritmos de classificação baseados em comparação
• Projeto 2: Algoritmos de gráfico (caminho mais curto de origem e árvore mínima de abrangência)
• Projeto 3: Algoritmos de correspondência de padrões

Abaixo, você encontrará a descrição e os requisitos dos projetos. Para obter os detalhes, vá para o diretório do projeto correspondente.

Projeto 1: Algoritmos de classificação baseados em comparação

---

Implemente os seguintes algoritmos de classificação e compare -os. Você pode usar qualquer linguagem de programação (por exemplo, C/C ++, Java, Python, C#). Neste projeto, você pode trabalhar sozinho ou como equipe de dois.

1. Classificação de inserção
2. Mesclar classificar
3. Heapsort [baseado em vetor e insira um item de cada vez]
4. Quicksort no local (qualquer item aleatório ou o primeiro ou o último item da sua entrada pode ser pivô).
5. Quicksort modificado
   • Use mediana de três como pivô.
   • Para um pequeno suporte de tamanho <= 10, use o tipo de inserção.

Instruções de execução:

1. Execute esses algoritmos para diferentes tamanhos de entrada (por exemplo, n = 1000, 2000, 4000, 5000, 10000 .. 40000, 50000). Você gerará aleatoriamente números para sua matriz de entrada. Registre o tempo de execução (precisa tomar a média conforme discutido na classe) e plotá -los todos em um único gráfico em relação ao tamanho da entrada. Observe que você comparará esses algoritmos de classificação para o mesmo conjunto de dados.
2. Observe também e apresente o desempenho dos dois casos especiais a seguir:
   • A matriz de entrada já está classificada.
   • A matriz de entrada é classificada com reversão.

Esquema de classificação:

Instruções de envio:

• Upload de tela
  1. Um relatório bem formado, cobrindo estruturas de dados escolhidas, análise de complexidade, resultados e código.
  2. Carregue o código do programa para execução. Certifique -se de fornecer leitura para TA.
• Além disso, a cópia impressa do relatório sem código para mim na classe.

Projeto 2: Algoritmos de gráfico (caminho mais curto de origem e árvore mínima de abrangência)

---

Neste projeto, você implementará dois algoritmos de gráfico mencionados abaixo. Nota: você pode trabalhar sozinho ou em uma equipe de dois máximos.

Problema 1: Encontre a árvore de caminho mais curto nos gráficos ponderados direcionados e não direcionados para um determinado vértice da fonte. Suponha que não haja borda negativa no seu gráfico. Você imprimirá cada custo de cada caminho e caminho para uma determinada fonte.

Problema 2: Dado um gráfico conectado, não direcionado e ponderado, encontre uma árvore de extensão usando bordas que minimizam o peso total? (?) = ∑ _{(u, v) ∈T} ? (?,?). Use o algoritmo Kruskal para encontrar a árvore de abrangência mínima (MST). Você imprimirá as bordas da árvore e o custo total da sua resposta.

Formato de entrada: Para cada problema, você receberá a entrada de um arquivo de texto. Digamos que você deseja executar o algoritmo no seguinte gráfico não direcionado. O formato de arquivo correspondente seria:

 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

Aqui, os dois primeiros números representam o número de vértices e bordas. A letra U significa gráfico não direcionado (D para direcionado). Na segunda linha, ele menciona todas as arestas e seu peso (por exemplo, ???? (?,?) E seu peso é 1. A última linha é opcional. Se fornecido, representa o nó de origem.

Instruções de envio:

• Um relatório bem formado, cobrindo uma breve descrição de cada algoritmo, estrutura de dados escolhida, tempo de execução do seu código, amostra de entrada/saída, instrução para executar seu programa facilmente.
• Para cada problema, execute seu programa para quatro gráficos diferentes de sua escolha. Use seu julgamento para definir gráficos de teste que você acha interessante e razoável. Por exemplo:
• Gráfico não direcionado: pelo menos 7 nós e 12 arestas
• Gráfico direcionado: pelo menos 7 nós e 15 arestas
• Código limpo para o TA para executar.
• Você pode usar qualquer linguagem de programação (por exemplo, C/C ++, Java, Python, etc.)
• Se trabalhados em uma equipe, os dois membros devem enviar tudo separadamente.
• Cópia impressa do seu relatório diretamente para mim; uma cópia por equipe.

Esquema de classificação:

Projeto 3: Algoritmos de correspondência de padrões

---

Nota: Você pode trabalhar sozinho ou em uma equipe de três máximos.

Para esta tarefa, você implementará apenas três algoritmos de correspondência de padrões de sua escolha na lista fornecida abaixo.

• Algoritmo de força bruta
• Algoritmo de Boyer-Moore-Horspool
• Algoritmo Knuth-Morris-Pratt
• Algoritmo Boyer-Moore
• Automação finita para correspondência de padrões

Experimentar:

• Compare três algoritmos para vários diferentes textos e padrões de entrada; pelo menos 10 casos diferentes
• Mencione o número de comparações necessárias em uma tabela para cada caso, para cada algoritmo

Submissão:

• Um relatório bem formado, cobrindo uma descrição curta de cada algoritmo, estrutura de dados usada, tempo de execução do seu código, entrada/saída de amostra, instrução para executar seu programa facilmente.
• Código limpo para o TA para executar.
• Você pode usar qualquer linguagem de programação (por exemplo, C/C ++, Java, Python, etc.)
• Se trabalhado em uma equipe, os dois membros ainda precisam enviar tudo separadamente.
• Copio duro do seu relatório diretamente para mim; uma cópia por equipe.

Esquema de classificação:

• 3 x 15 = 45 pontos: para implementar três algoritmos
• 20 pontos: para experimento
• 10 pontos: relatório