Weekly outline
-
Конспект за практикума по ДАА
1. Запознаване с online judge системи и състезателното програмиране
2. Сортиране О(n2) - bubble sort, selection sort, insertion sort. Сортиране count sort
3. Сортиране О(n*lg(n)) - quick sort, heap sort, merge sort
4. Двоично/Троично търсене
5. Обхождане на непретеглени графи: DFS, BFS, топологично сортиране
6. Най-къси пътища в претеглени графи: Dijkstra, Floyd, Ford-Bellman
7. Минимално покриващо дърво: Prim, Kruskal
8. Динамично програмиране
Курсове от минали години:
— 2012 / 2013 уч. г., зимен семестър;
— 2016 / 2017 уч. г., летен семестър;
— 2017 / 2018 уч. г., зимен семестър;
— 2017 / 2018 уч. г., летен семестър.Схема за оценяване на практикума по ДАА
През семестъра се дават N домашни (между 5 и 10 вкл.), носещи общо 50 точки, т.е. всяко домашно носи по 50 / N точки.
Има две контролни с по три задачи и едно контролно с четири задачи. Това прави общо десет задачи, всяка от които носи по 25 точки, така че максимумът е 250 точки.
Контролните и домашните носят общо 300 точки.
Ще можете да съберете дори повече от 300 точки с помощта на специалните домашни и бонуса за решени задачи.
През семестъра е възможно да има специални домашни, като всяка тяхна задача ще носи по най-много 20 точки при пълно решение. Тези задачи ще бъдат по-трудни и евентуално ще съдържат учебен материал, който не е взет на упражнения, т.е. ще трябва евентуално да положите повече усилия, за да ги решите.Ще има и бонус точки за петимата студенти, решили най-много задачи в "Арената" през семестъра.
Точки на задача се получават пропорционално на броя тестове, на които вашата програма изкарва верен резултат в оказаните ограничения по време и памет, т.е. не е задължително да решите една задача напълно, за да изкарате точки от нея. Няма да бъдете наказвани за изпратени грешни програми и ще се взима най-доброто ваше решение, а не последното.
Контролните ще бъдат по толкова астрономични часа, колкото е броят на задачите. Срокът за всяко домашно ще бъде не по-кратък от две седмици.
Скала за оценяване:
[90т., 104т.] - 3.00 [105т., 119т.] - 3.50 [120т., 134т.] - 4.00 [135т., 149т.] - 4.50 [150т., 164т.] - 5.00 [165т., 179т.] - 5.50 [180т., ∞ ) - 6.00
-
- https://judge.openfmi.net/practice/open_contest?contest_id=32 - Шоколади и Церн
- https://judge.openfmi.net/practice/get_problem_description?contest_id=8&problem_id=22 — тази задача няма да може да се реши с някое от бавните сортирания. Ще я решим за 100 точки с някое от бързите сортирания. Задачата е добра от гледна точка на това, че можете на практика да видите кой алгоритъм от кой е по-бърз и кой колко точки ще ви донесе.
- http://informatika.bg/problems/DAA.2011.Trosver/Trosver.pdf — понеже няма къде да си тествате решението на тази задача, можете да пратите решението си като решение на следващата задача, която е същата, но с малко по-различно условие, ограничения и вход: http://acm.timus.ru/problem.aspx?space=1&num=1290
- https://judge.openfmi.net/practice/get_problem_description?contest_id=3&problem_id=11
-
Задачи за бързи сортировки:
1) https://judge.openfmi.net/practice/open_contest?contest_id=33
· Drinking Game — приложение на HeapSort. Можете да решите задачата за 100 точки и с използването на приоритетна опашка.· PermSwap — намиране на броя на инверсиите в масив — приложение на MergeSort.
· Бързо сортиране — задачата се решава с използването на някой от бързите алгоритми (ако прецените, можете да се опитате да я решите и с бавните алгоритми за сортиране, за да видите колко по-бавни са те при голям вход).
2) https://judge.openfmi.net/practice/open_contest?contest_id=83 — задача, подобна на задачата за шоколадите от предния път. Разликата е, че тук трябва да използвате някое от бързите сортирания.
3) https://judge.openfmi.net/practice/open_contest?contest_id=72 — График (*).
4) https://judge.openfmi.net/practice/get_problem_description?contest_id=40&problem_id=124
5) https://judge.openfmi.net/practice/get_problem_description?contest_id=98&problem_id=314
6) https://judge.openfmi.net/practice/open_contest?contest_id=85 — Evil (за упражнение вкъщи).
-
-
Задачи за двоично и троично търсене:
1) Намерете ∛n с точност до третия знак след десетичната запетая, където n се въвежда от клавиатурата.
2) https://judge.openfmi.net/practice/open_contest?contest_id=77 — E.Sysadmin.
3) https://judge.openfmi.net/practice/open_contest?contest_id=85 — Sequence.
4) https://judge.openfmi.net/practice/open_contest?contest_id=37 — всички задачи.
5) https://judge.openfmi.net/practice/open_contest?contest_id=84 — Elliot.
6) https://judge.openfmi.net/practice/open_contest?contest_id=10 — Алкохолици.
7) https://judge.openfmi.net/practice/open_contest?contest_id=3 — Exam.
8) https://judge.openfmi.net/practice/open_contest?contest_id=98 — Ферма.
Материали за троично търсене:
- https://www.hackerearth.com/practice/algorithms/searching/ternary-search/tutorial/
- https://en.wikipedia.org/wiki/Unimodality#Unimodal_function
- https://en.wikipedia.org/wiki/Ternary_search
- https://www.hackerearth.com/practice/algorithms/searching/ternary-search/tutorial/
-
Обхождане в дълбочина: Школа.
Топологично сортиране: Meteorite.
Обхождане в ширина: Ябълки, Game.
Задачи:
- Състезание № 39 — Школа, Лабиринт и Ябълки.
- Състезание № 28 — Рицари.
- Състезание № 82 — още една редица.
-
(авторово решение на задачата "Школа" —
примерна реализация на търсене в дълбочина)
- Състезание № 39 — Школа, Лабиринт и Ябълки.
-
-
Дийкстра: Пътуване, Cheating (може и с BFS), Sober, Атака, Денивелация, Railways, Lovers, Екскурзия (иска досещане)
МПД: Мрежа, Streets, Space Station
Задачи:
- https://judge.openfmi.net/practice/open_contest?contest_id=82 - Пътища
- https://judge.openfmi.net/practice/open_contest?contest_id=76 - Всичко
- https://judge.openfmi.net/practice/open_contest?contest_id=60 - Превъртял
- http://judge.openfmi.net/practice/open_contest?contest_id=79 – Реконструкция
- http://judge.openfmi.net/practice/open_contest?contest_id=88 – Хипертелепорт
- http://judge.openfmi.net/practice/open_contest?contest_id=86 – Поддръжка
- https://judge.openfmi.net/practice/open_contest?contest_id=82 - Пътища
-
-
-
-
-
-
-
Авторови решения на примерното трето контролно, което направихме за подготовка преди третото контролно по ДАА-практикум върху динамично програмиране.
-