Fall 2019 ITCS 8114 AlgoDS

Осень 2019 г.-ITCS-8114-Algods

Этот репозиторий содержит проекты и задания, конечно, «ITCS 6114/8114: алгоритмы и структуры данных» . Этот курс был проведен в семестре осенью 2019 года в рамках моей степени доктора философии в UNC Charlotte.

Список проектов

• Проект 1: Алгоритмы сортировки на основе сравнения
• Проект 2: Алгоритмы графика (самый короткий путь в одиночном стиле и минимальное дерево
• Проект 3: Алгоритмы сопоставления шаблонов

Ниже вы найдете описание и требования проектов. Чтобы получить детали, перейдите в соответствующий каталог проектов.

Проект 1: Алгоритмы сортировки на основе сравнения

---

Реализуйте следующие алгоритмы сортировки и сравните их. Вы можете использовать любой язык программирования (например, C/C ++, Java, Python, C#). В этом проекте вы можете работать в одиночку или в команде из двух.

1. Вставка сортировки
2. Слияние сортировки
3. Heapsort [на основе вектора и вставьте по одному элементу за раз]
4. QuickSort на месте (любой случайный элемент или первый или последний элемент вашего ввода может быть поворотом).
5. Модифицированный QuickSort
   • Используйте медиана три в качестве Pivot.
   • Для небольшой подпрограммы размера <= 10 используйте вставку.

Инструкции по исполнению:

1. Запустите эти алгоритмы для различных размеров ввода (например, n = 1000, 2000, 4000, 5000, 10000 .. 40000, 50000). Вы будете случайным образом генерировать числа для вашего массива ввода. Запишите время выполнения (необходимо принять среднее значение, как обсуждалось в классе) и постройте их все на одном графике против размера ввода. Обратите внимание, что вы будете сравнивать эти алгоритмы сортировки для того же набора данных.
2. Также наблюдайте и представляют показатели следующих двух особых случаев:
   • Входной массив уже отсортирован.
   • Входной массив обратный отсортирован.

Схема оценки:

Инструкции по подаче:

• Загрузка холста
  1. Хорошо форматированный отчет, охватывающий выбранные структуры данных, анализ сложности, результаты и код.
  2. Загрузите код программы для выполнения. Убедитесь, что вы предоставили Readme для TA.
• Кроме того, хардкопия отчета без кода для меня в классе.

Проект 2: Алгоритмы графика (самый короткий путь в одиночном стиле и минимальное дерево

---

В этом проекте вы будете реализовать два алгоритма графика, упомянутых ниже. Примечание: вы можете работать в одиночку или в команде из двух макс.

Проблема 1: Найдите самое короткое дерево пути как в направленных, так и в неопределенных взвешенных графиках для данной вершины источника. Предположим, что в вашем графике нет отрицательного преимущества. Вы напечатаете каждый путь и стоимость пути для данного источника.

Проблема 2: Учитывая подключенный, неправомерный, взвешенный график, найдите живое дерево с использованием ребра, которое минимизирует общий вес? (?) = ∑ _{(u, v) ∈t} ? (?,?). Используйте алгоритм Kruskal, чтобы найти минимальное охваточное дерево (MST). Вы распечатываете края дерева и общую стоимость вашего ответа.

Формат ввода: для каждой проблемы вы будете принимать ввод из текстового файла. Скажите, что вы хотите запустить алгоритм на следующем неисправенном графике. Соответствующий формат файла будет:

 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

Здесь первые два числа представляют количество вершин и краев. Буква u означает неисправный график (D для направленного). Со второй строки он упоминает все края и вес (например ,?

Инструкции по подаче:

• Хорошо форматированный отчет, охватывающий краткое описание каждого алгоритма, выбранной структуры данных, времени выполнения вашего кода, ввода/вывода образца, инструкциями для легкого запуска вашей программы.
• Для каждой проблемы запустите свою программу для четырех разных графиков по вашему выбору. Используйте свое суждение, чтобы определить тестовые графики, которые вы считаете интересными и разумными. Например:
• Недоставленный график: не менее 7 узлов и 12 краев
• Направленный график: не менее 7 узлов и 15 краев
• Чистый код для TA для выполнения.
• Вы можете использовать любой язык программирования (например, C/C ++, Java, Python и т. Д.)
• Если они работают в команде, оба участника обязаны подать все отдельно.
• Хардкопия вашего отчета мне напрямую; одна копия на команду.

Схема оценки:

Проект 3: Алгоритмы сопоставления шаблонов

---

Примечание: вы можете работать в одиночку или в команде из трех макс.

Для этого задания вы будете реализовать только три алгоритма соответствия шаблонов по вашему выбору из списка, приведенного ниже.

• Алгоритм грубой силы
• Boyer-Moore-Horspool Algorithm
• Алгоритм Кнут-Моррис-Пратт
• Алгоритм Бойер-Мур
• Конечная автоматизация для сопоставления рисунков

Эксперимент:

• Сравните три алгоритма для нескольких различных входных текстов и шаблонов; не менее 10 различных случаев
• Укажите количество сравнений, необходимых в таблице для каждого случая, для каждого алгоритма

Подчинение:

• Хорошо форматированный отчет, охватывающий краткое описание каждого алгоритма, используемой структуры данных, времени выполнения вашего кода, ввода/вывода образца, инструкция для легко запуска вашей программы.
• Чистый код для TA для выполнения.
• Вы можете использовать любой язык программирования (например, C/C ++, Java, Python и т. Д.)
• Если они работают в команде, оба участника должны быть представлены отдельно.
• HardcopyOf ваш отчет мне напрямую; одна копия на команду.

Схема оценки:

• 3 x 15 = 45 баллов: для реализации трех алгоритмов
• 20 баллов: для эксперимента
• 10 баллов: отчет