1)  В задача 2 отсечките се заменят интервали и се търсят пресичания на интервали.  Лесно се измисля контпрапример, в който непресичащи се отсечки стават пресичащи се интервали. Да кажем, a1=3, b1=1, a2=5, b2=2

2) В задача 3 се казва, че замяната на приор опашка с FIFO прави алгоритъма бавен.  Това би било така, ако освен смяната на вида опашка се добави и код, който осигурява коректността.  Само смяната на PQ с FIFO чупи алгоритъма.  Естествената интерпретация на условието е, че се прави САМО тази смяна -- другото не е казано.  Правилният отговор тогава е, че алг престава да работи (винаги), а не че става бавен.




Последно модифициране: сряда, 31 август 2022, 11:43