Пояснения за оценките -- често срещани грешки на изпита, неокончателност, нанасяне
Често срещани грешки в решенията:
1. в зад. 4, акумулаторът (броячът) не се връща от ф-иите, а се инкрементира вътре в тях, явно се разчита, че е глобална променлива или че ф-ята действа върху него със side effect, но това не е казано явно. -2 т
2- в зад. 5, при ползване на рекурсия без мемоизация,
алгоритъмът стаав суперекспоненциален. 0 т за такъв отговор.
Нормалното е да се смята отдолу нагоре.
// казва се prime number, не simple number
3. В зад 4, строене на dag за инверсиите е абсолютно излишно, той не ни дава нищо, а строенето му струва O(n^2). 0 т. за такова нещо
4. В зад. 1, ползване на Counting sort или Radix sort (?!?!) върху претеглените ребра носи 0 т на задачата. Теглата са произволни и сложността на такова сортиране не е дефивирана.
5. В зад 1 има много "решения", които броят ребрата, по-леки от даденото, сравняват с n-1, и от това вадят заключение за отговора на задачата. 0 т за такова решение. Никиой не е казал, че ВСИЧКИ n-1 най-леки ребра са в МПД. Очевидно някои от тях може да образуват цикли с други от тях.
6. Всякакви опити за броене на цикли носят 0 т. Циклите са суперекспоненциално много в най-лошия случай, а броят на циклите НЕ Е равен на броя на обратните ребра (DFS).
------------------------
Оценките са окончателни, ама не съвсем. При успешно изкаран практикум може да има корекция нагоре.
-------------------------
За
внасяне на оценките на редовния курс: вторник от 09 до 12, при
необходимост ще има и друго време за нанасяне. За миналите години --
чакайте информация тук, в муудъл.