ДАА, Инф, пролет 2019/2020

Тъй като няма да мога да покажа писмените работи на студентите преди короната да тръгне да си ходи, а не виждам признаци това да се случи скоро, ще ползвам муудъл, за да посоча някои често срещани грешки в изпитите.

Вариант C сякаш се е оказал най-лек и с упътването доста хора са се справили.  А пропо, тази задача може да се реши и по-ефикасно (не асимптотично, но практически говорейки) с едно минаване през празнините между елементите и "завъртане" на всяка двойка, която не е в правилното отношение измежду < и >. Това ми го посочи Кралчев.  Но при такова решение би трябвало да се направи и анализ на коректността, която може би не е 100% очевидна (ползва се транзитивността на релациите). 

При решението с медианата не е необходимо да се доказва коректност.  Алгоритъмът PICK (SELECT) е изучаван на лекции и може да се ползва наготово.  Но, за да се дадат точки, трябва да се спомене *как* намираме медианата, за да я сложим на първа позиция, и да спомене нещичко за сложността по време.  Ако само е казано "намираме медианата и я слагаме на първа позиция в изходния масив" -- това е нула точки.  Наивното намиране на медиана е \Omega(n lg n), защото презполага сортиране.  Тъй като задачата е проста, а с упътването е елементарна, всяко решение, което е по-лошо от линейно, дава нула точки.

Има няколко решения с предварително сортиране.  Нула точки, това е \Omega(n lg n).  Има решения с COUNTINGSORT.  Това е дори по-зле.  COUNTINGSORT върху произволен числен масив има недефинирана сложност, или сложност безкрайност, ако предпочитате.

Теоретичният въпрос в този вариант, а именно за U/F структурите, е нула в почти всички работи.  Критерият за ненулевост е, дали, ако не знам нищо за U/F, мога да науча основното за U/F от дадения отговор. От тези, които изобщо са отговорили, повечето са дали отговори, в които в най-добрия случай има коректни фрагменти, но като цяло са некохерентни.