Седмичен изглед
-
Финални точки: https://docs.google.com/spreadsheets/d/1YfYmQo1bbV8FTiUGapka0gS-JoPwnwaP4fVTG1q8lT4
Конспект по ДАА-практикум:1. Запознаване с online judge системи и състезателното програмиране
2. Сортиране О(n^2) - bubble sort, selection sort, insertion sort. Сортиране count sort
3. Сортиране О(nlgn) - quick sort, heap sort, merge sort
4. Binary search
5. Обхождане на непретеглени графи: DFS, BFS, топологично сортиране
6. Обхождане на претеглени графи: Dijkstra, Floyd, Ford-Bellman
7. Минимално покриващо дърво: Prim, Kruskal
8. Динамично програмиране
(Линк към миналогодишния курс може да намерите тук)
Схема за оценяване по ДАА-практикум зимен семестър 2017/2018:
N домашни (5 <= N <= 10) носещи общо 50 точки, т.е. всяко домашно носи по 50/N точки.
(2 контролни * 3 задачи + 1 контролно * 4 задачи) * 25 точки на задача = 250 точки
Общо 300 точки.
Ще можете да съберете дори повече от max 300 точки с помощта на специалните домашни и бонусът за решени задачи, за които можете да прочетете повече тук:
През семестъра ще има две специални домашни, като всяка задача на тях ще носи по най-много 20 точки (при цялостно решение) (* тези задачи ще са по-трудни и евентуално ще съдържат непокрит на упражнения материал, т.е. ще трябва евентуално да положите повече усилия, за да ги решите).Ще има и бонус точки за топ 5 от студентите, този семестър, решили най-много задачи в арената.
Точки на задача се получават пропорционално на броя тестове, на които вашата програма изкарва верен резултат, т.е. не е задължително да решите една задача напълно, за да изкарате точки от нея. Няма да бъдете наказвани за грешни събмити и ще се взима най-доброто ваше решение, а не последното.
Контролните ще бъдат по 3 часа. За всяка домашно ще имате срок >=2 седмици.
Скала за оценките:
[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://skelet.fmi.uni-sofia.bg/practice/get_problem_description?contest_id=114&problem_id=359
Съответното състезание:https://skelet.fmi.uni-sofia.bg/practice/open_contest?contest_id=114
-
Задачи за запознанство със системата:
1) Ще започнем като решим всички задачи от състезанието - „2013 Упражнение 1 – Система“ в арената: (https://skelet.fmi.uni-sofia.bg/practice/open_contest?contest_id=31)
2) За по-бързите „2012 Тема 1 – Домашно“: (https://skelet.fmi.uni-sofia.bg/practice/open_contest?contest_id=5)3) Въведение в spoj0 + задачки за напредналите D и после A: (http://judge.openfmi.net:9080/spoj0/contests.pl?contest_id=126) -
Задачи за бавни сортировки:
1) https://skelet.fmi.uni-sofia.bg/practice/get_problem_description?contest_id=32&problem_id=99
2) https://skelet.fmi.uni-sofia.bg/practice/get_problem_description?contest_id=32&problem_id=100
3) https://skelet.fmi.uni-sofia.bg/practice/get_problem_description?contest_id=8&problem_id=22 – тази задача няма да може да се реши с някое от бавните сортирания. Ще я решим за 100 точки с някое от бързите сортирания. Задачата е добра от гледна точка на това, че можете на практика да видите кой алгоритъм от кой е по-бърз и кой колко точки ще ви донесе.
4) http://informatika.bg/problems/DAA.2011.Trosver/Trosver.pdf - понеже няма къде да си тествате решението на тази задача, можете да пратите решението си като решение на следващата задача, която е същата, но с малко по-различно условие, ограничения и вход: http://acm.timus.ru/problem.aspx?space=1&num=1290
5) https://skelet.fmi.uni-sofia.bg/practice/get_problem_description?contest_id=3&problem_id=11
-
Миналият уикенд арената не работеше, поради спирането на тока (причинено от авария) в петък, но вече отново е на линия. На този линк може да намерите допълнителни задачи за сортировки, с които да се упражнявате.
-
Задачи за бързи сортировки:
1) https://skelet.fmi.uni-sofia.bg/practice/open_contest?contest_id=33
· Drinking Game – приложение на HeapSort. Можете да решите задачата за 100 точки и с използването на priority_queue.
· PermSwap – намиране броя на инверсиите в масив – приложение на MergeSort.
· Бързо Сортиране – задачата се решава с използването на някой от бързите алгоритми (ако прецените може да пробвате да я решите и с бавните алгоритми за сортиране, за да видите колко по-бавни са те при голям вход)
2) https://skelet.fmi.uni-sofia.bg/practice/open_contest?contest_id=83 – задача, подобна на Шоколади от предния път. Разликата е, че тук трябва да използвате някое от бързите сортирания.
3) https://skelet.fmi.uni-sofia.bg/practice/open_contest?contest_id=72 - График (*)
4) https://skelet.fmi.uni-sofia.bg/practice/get_problem_description?contest_id=40&problem_id=124
5) https://skelet.fmi.uni-sofia.bg/practice/get_problem_description?contest_id=98&problem_id=314
6) https://skelet.fmi.uni-sofia.bg/practice/open_contest?contest_id=85 – Evil (за упражнение вкъщи)
-
Поради проблеми с качването на първото домашно в арената за момента можете да намерите само условието тук, за да мислите по нея.
1) Намерете с точност до 3-тия знак след десетичната точка ∛n, където n се въвежда от клавиатурата.
2) https://skelet.fmi.uni-sofia.bg/practice/open_contest?contest_id=77
3) https://skelet.fmi.uni-sofia.bg/practice/get_problem_description?contest_id=85&problem_id=2654) https://skelet.fmi.uni-sofia.bg/practice/open_contest?contest_id=37 - всички задачи
5) https://skelet.fmi.uni-sofia.bg/practice/open_contest?contest_id=84 – Elliot
6) https://skelet.fmi.uni-sofia.bg/practice/open_contest?contest_id=10 – Алкохолици
7) https://skelet.fmi.uni-sofia.bg/practice/open_contest?contest_id=3 – Exam
8) https://skelet.fmi.uni-sofia.bg/practice/open_contest?contest_id=98– Ферма
-
https://skelet.fmi.uni-sofia.bg/practice/open_contest?contest_id=39 :
1) Школа
2) Лабиринт
3) Ябълки
6) Диаметър
7) Long
4) https://skelet.fmi.uni-sofia.bg/practice/open_contest?contest_id=28 – Рицари
5) https://skelet.fmi.uni-sofia.bg/practice/open_contest?contest_id=82 – Още една редица
8) https://skelet.fmi.uni-sofia.bg/practice/open_contest?contest_id=97 -
Ето линк към крайното класиране от първото контролно (ще бъде крайно, когато ~15-те решения в опашката се изтестват):
https://skelet.fmi.uni-sofia.bg/main/results?contest_id=120 -
-
-
-
(17-19 => 18-20)
-
-
- Крускал
- O(m*lg(m)) || O(m*lg(n))
- Прим
- adj. matrix + searching: O(n^2)
- bin. heap + adj. lists: O((n+m)*lg(n)) = O(m*lg(n))
- fib. heap + adj. lists: O(m+n*lg(n))
Задачи:
-
-
https://skelet.fmi.uni-sofia.bg/practice/open_contest?contest_id=82:
1) Още една редица
2) Пътища
https://skelet.fmi.uni-sofia.bg/practice/open_contest?contest_id=76:
1) Пешо
2) Cheating
https://skelet.fmi.uni-sofia.bg/practice/open_contest?contest_id=60:
1) Превъртял
https://skelet.fmi.uni-sofia.bg/practice/open_contest?contest_id=54:
1) Екскурзия
https://skelet.fmi.uni-sofia.bg/practice/open_contest?contest_id=102:
1) Railways
2) Space Station - МПД
-
ДАА - контролно 2 (есен 2012): Паркетиране
2012 Упражнение - Динамични: Всички 8 на брой задачи
Турнир за купата на Декана 2009 - B.Fuel
2011 ДАА - Контролно 2 - Разправия (Известна още като "Братска подялба")
2015 ДАА Тренировка 2 - D.Fuel (Разликите с тази от spoj0 са, че ограниченията за входните данни са по-големи, а ограничението по време - по-малко. Тук ще трябва да напишете итеративно решение, за да имате на всички тестове "ok").