angeld55/algorithms_fmi

Repository with examples for the "Design and аnalysis of аlgorithms" course given by me @ Faculty of Mathematics and Informatics, Sofia University (2018 - present)

Записки и код от семинарите по "Дизайн и анализ на алгоритми" - спец. Информатика/Компютърни науки

• Тема 1: Асимптотични нотации. Асимптотични сравнения на функции.
• Тема 2: Анализ на сложността на итеративни алгоритми. Задачи. Анализ на сложността на алгортими за търсене и алгоритми за сортиране (в най-лош случай и среден случай)
• Тема 3: Амортизиран анализ. Анализ на сложността на рекурсивни алгоритми. Задачи. Решаване на рекурентни уравнения по метода с характерситчното уравнение. Решаване на р.у. с други методи.
• Тема 4: Анализ на сложността на рекурсивни алгоритми - част 2. Алгоритми изградени по схемата Разделяй и владей. Сортиращи алгоритми (изградени по Р.В.). Мастър теоремата. Разширение на М.Т. и примерни задачи.
• Тема 5: Задачи за предговор. Асимптотични нотации, амортизиран анализ и анализ на рекурсивни алгоритми (пример с комбинаторно генериране). Коректност на итеративни алгоритми. Доказателство за коректност с инварианта на цикъла.
• Тема 6: Доказателство за терминация на итеративни алгоритми. Доказателство за коректност с инварианта на цикъла (част 2).
• Тема 7: Доказателство за коректност с инварианта на цикъла (част 3). Доказателство на линейно търсене и на сортиране по метода на мехучето.
• Тема 8: Доказателство за коректност на рекурсивни алгоритми. Доказателство с индукция, доказателство за финитност, сложност. Решаване на рекурентно уравнение с индукция.
• Тема 9: Долни граници. Доказателство за долна граница чрез дърво на вземане на решения и чрез "игра срещу противник".
• Тема 10: Долни граници (част 2). Доказателство за долна граница чрез редукция.
• Тема 11: Съставяне на алгоритми върху масиви. Модификации на изучавани алгоритми.
• Тема 12: Алгоритми върху графи (част 1). BFS, DFS(итеративна и рекурсвна имплементация). Приложения и алгоритми с BFS и DFS (търсене на цикъл, топологично сортиране и др.).
• Тема 13: Алгоритми върху графи (част 2). Алгоритми за най-къс път и минимално покриващо дърво.
• Тема 14: Динамично програмиране. Мемоизация.
• Тема 15: Задачи за предговор. Динамично програмиране. Долни граници. Алгоритми върху графи.

Код от семинарите по Алгоритми и Програмиране (част 2) - ФМИ

• Тема : Комбинаторно генериране. Генериране на прости комбинаторни обекти.
• Тема : Сегментни дървета.
• Тема : Многонишково програмиране.

algorithms_fmi's Issues

Семинарче 2 - корекцийки

На задачка 4, функцията f се извиква lgn пъти, не n.
На същата задачката, res е винаги 1, не 0 или 1.
На линейно търсене, търсим елемента, не търсим елементът.

Грешки

DP.txt:
Ред 61: matrix[i-1][j], mаtrix[i][j-1] -> DP[i-1][j], DP[i][j-1]
Ред 67: мисива -> масива
Ред 93: DP[i][j] = DP[i-1][j] или DP[i-1][j - arr[i-1]]] -> DP[i][j] = DP[i-1][j] или DP[i-1][j - arr[i]]]