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

във втората задача няма асимпт. еквивалентни функции.  Подредбата е:

f4 > f3 > f2 > f1 > f9 > f8 > f6 > f7 > f5 > f10

Оценяването е такова: по две точки за всяко коректно ЕКСПЛИЦИТНО сравнение на функции, които са НЕПОСРЕДСТВЕНИ СЪСЕДИ в наредбата.  Трябва да е кристално ясно къде точно се сравняват две от ДАДЕНИТЕ функции (които се явяват съседни).  Ако отговорът започва с опроставяния на ф-иите, това е ОК, но когато се правят сравнения, трябва да се казва кои две ф-ии измежду десетте биват сравнявани в момента.  Не е достатъчно да се вземат ф-ии измежду опростените, ако не се казва те точно на кои от оригиналните отговарят.

В степенните показатели мултипликативните константи ИМАТ значение и не може да се пренебрегват.

в първата задача инвар. трябва да е нещо такова: "при всяко достигане на ред 3, числото к, ако изобщо се съдържа в масива, се намира в подмасива A[p .. q]".  Или, алтернативно, "при всяко дост. на ред 3, числото к със сигурност не е в никой от подмасивите A[1 .. p-1] или A[q+1 .. n]".  Следното обаче не става за инварианта "при всяко достигане на ред 3, търсим числото к в подмасива едикойси".  От това, че ние търсим нещо някъде изобщо не следва, че то е там или че не може да е другаде.

В зад 1, груба грешка е да се прави индукция по n, ако се твърди, че д-вото е с инварианта.  При д-во с инварианта, индукцията е по броя на изпълненията, при ФИКСИРАНО n.