Дизайн и анализ на алгоритми, КН2, летен семестър 2017/2018

Често срещани грешки в решенията:

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, при необходимост ще има и друго време за нанасяне.  За миналите години -- чакайте информация тук, в муудъл.