АСП2/К3 2017

Трећи колоквијум 2017. године одржан је 20. јануара. Поставка задатака је доступна са странице предмета.

1. задатак

Поставка

Како изгледа низ са слике након првих пет итерација схакерсорт алгоритма?

Решење

Низ након пет итерација схакерсорт алгоритма

12	3	34	83	21	95	34	1	18	20	83	17	44	39
3	12	34	21	83	34	1	18	20	83	17	44	39	95
1	3	12	34	21	83	34	17	18	20	83	39	44	95
1	3	12	21	34	34	17	18	20	83	39	44	83	95
1	3	12	17	21	34	34	18	20	39	83	44	83	95
1	3	12	17	21	34	18	20	34	39	44	83	83	95

2. задатак

Поставка

Дата је хеш табела са 10 улаза. У табелу се уносе кључеви које се могу састојати од великих и малих слова. Примарна хеш функција је Х₁(К) = (1 + лен(К)) мод 10, где лен(К) враћа број слова у прослеђеном кључу К. Временска локалност је веома изражена, јер се након уметања сваког кључа јавља велики број претраживања на тај кључ пре него што се уметне следећи. Колизије се разрешавају нестандардном применом двоструког хеширања код кога је секундарна функција Х₂(К) = 3 + уп_цасе_цнт(К), где уп_цасе_цнт(К) враћа укупан број великих слова у кључу К.

1. Предложити модификацију начина за разрешавање колизије тако да се минимизује време успешног претраживања у датим условима.
2. Применом предложеног решења у доњу табелу уметнути следеће кључеве:

   ЧоКоЛаДа, ПалАчИНка, кафА, ТОРтА, РоЛаТ, СЛадолед, коЛАЧ

   Приказати финално стање хеш табеле и целокупан поступак применом технике описане у решењу под а).

Решење

1. Приликом разрешавања колизије, постојеће кључеве можемо померити да буду ниже у испитном низу дуплим хеширањем а новоуметнути кључ ставити на његов почетак како би се са што мањим бројем колизија долазило до најскорије уметнутих кључева.
2. Уметање у табелу иде овако:
   1. ЧоКоЛаДа се умеће на место 9
   2. ПалАчИНка се умеће на место 0
   3. кафА се умеће на место 5
   4. ТОРтА се умеће на место 6
   5. РоЛаТ се умеће на место 6, ТОРтА се помера на место 3
   6. СЛадолед се умеће на место 9, ЧоКоЛаДа се помера на место 6, РоЛаТ се помера на место 2
   7. коЛАЧ се умеће на место 6, ЧоКоЛаДа се помера на место 3, ТОРтА се помера на место 0, ПалАчИНка се помера на место 7

Коначни изглед хеш табеле након уметања

0	ТОРтА
1
2	РоЛаТ
3	ЧоКоЛаДа
4
5	кафА
6	коЛАЧ
7	ПалАчИНка
8
9	СЛадолед

3. задатак

Поставка

Написати итеративну имплементацију qуицксорт алгоритма. У телу функције QУИЦКСОРТ која ће представљати ову имплементацију, након избора пивота, позивати функцију ПАРТИТИОН која враћа коначну позицију пивота у низу. Алгоритам реализовати што ефикасније, а за пивот узети елемент низа који је средњи по вредности у избору између елемената са прве три позиције у партицији.

Решење

Пошто се помиње велика ефикасност, битно је да на стек гурамо веће партиције а директно обилазимо мање како би дубина стека била што мања.

QUICKSORT(arr, n)
STACK_INIT(S_down)
STACK_INIT(S_up)
down = 1
up = n
from_stack = false
while (not STACK_EMPTY(S_down)) or (not from_stack) do
    if from_stack then
        down = POP(S_down)
        up = POP(S_up)
    end_if
    if (up - down = 0) or (up - down = 1) then
        if (up - down = 1) and (arr[up] < arr[down]) then
            arr[up] ↔ arr[down]
        end_if
        from_stack = true
        continue
    end_if
    first = arr[down]
    second = arr[down+1]
    third = arr[down+2]
    if (first ≤ second ≤ third) or (third ≤ second ≤ first) then
        pivot = 2
    else if (second ≤ first ≤ third) or (third ≤ first ≤ second) then
        pivot = 1
    else
        pivot = 3
    end_if
    pivot_pos = PARTITION(arr, down, up, pivot)
    lower_down = down
    lower_up = pivot_pos-1
    higher_down = pivot_pos+1
    higher_up = up
    if (lower_up - lower_down < 1) and (higher_up - higher_down < 1) then
        from_stack = true
    else if lower_up - lower_down < higher_up - higher_down then
        up = lower_up
        down = lower_down
        from_stack = false
        PUSH(S_down, higher_down)
        PUSH(S_up, higher_up)
    else
        up = higher_up
        down = higher_down
        from_stack = false
        PUSH(S_down, lower_down)
        PUSH(S_up, lower_up)
    end_if
end_while

Пошто је речено да се избор пивота ради у QУИЦКСОРТ, претпоставићемо да се тај пивот затим прослеђује ПАРТИТИОН као параметар.

PARTITION(arr, down, up, pivot_pos)
i = down
j = up
pivot = arr[pivot_pos]
while i < j do
    while (arr[i] ≤ pivot) and (i < j) do
        i = i + 1
    end_while
    while arr[j] > pivot do
        j = j - 1
    end_while
    if i < j then
        if j == pivot_pos then
            pivot_pos = i
        end_if
        arr[i] ↔ arr[j]
    end_while
end_while
arr[pivot_pos] ↔ arr[j]
return j

4. задатак

Поставка

Написати у псеудокоду функцију за декрементирање кључа који се налази у бинарном нерастућем (маx) хипу. Сматрати да је хип смештен у низу чији индекси почињу од 0. Функција као свој параметар добија индекс кључа у низу кога треба декрементирати.

Решење

HEAP KEY DEC(i)
arr[i] = arr[i]-1
left = 2 * i + 1
right = 2 * i + 2
while ((left ≤ n) and (arr[left] > arr[i])) or ((right ≤ n) and (arr[right] > arr[i])) do
    if right ≤ n then
        if arr[right] > arr[left] then
            high = right
        else
            high = left
        end_if
    else
        high = left
    end_if
    arr[i] ↔ arr[high]
    i = high
    left = 2 * i + 1
    right = 2 * i + 2
end_while

5. задатак

Поставка

Подаци се смештају у хеш табелу са 7 улаза применом хеш функције х_п(К) = К мод 7. За разрешавање колизија се користи метода двоструког хеширања са секундарном хеш функцијом х_с(К) = 4 + К мод 2. Образложити на који начин у овом случају може доћи до секундарног груписања и навести секвенцу од три кључа која производи овај ефекат у конкретном случају. Наведене кључеве унети у табелу.

Решење

У овом случају може доћи до секундарног груписања када унети кључеви дају исти остатак при дељењу са 7 и при дељењу са 2. Такви су рецимо кључеви 0, 14 и 28.

Табела са унетим кључевима

0	0
1
2
3
4	14
5
6
7
8	28

6. задатак

Поставка

Фибоначијев хип

1. Која је разлика између додавања у биномни хип и Фибоначијев хип? Објаснити кратко и прецизно, у једној до две реченице.
2. У празан Фибоначијев хип додају се елементи 10, 5, 17, 3, 12, 11, 1, потом се брише елемент са вредношћу 1, након чега се додају елементи 7 и 2. Нацртати изглед хипа након првих седам уметања и након сваке наредне измене хипа.

Решење

1. При додавању у Фибоначијев хип унети чвор се само уланчава, а груписање слично биномном хипу се дешава тек код избацивања најмањег елемента.
2. Испод су дати изгледи хипа након дате четири операције.

• 

  Изглед хипа након уметања 10, 5, 17, 3, 12, 11, 1.

• 

  Изглед хипа након брисања 1.

• 

  Изглед хипа након уметања 7.

• 

  Изглед хипа након уметања 2.

7. задатак

Поставка

Подаци се смештају у хеш табелу са н улаза применом хеш функције х(К) = К мод н. За разрешавање колизија се користи метода квадратног претраживања, али није дозвољено користити операцију множења (квадрирања). Предложити метод брисања и написати псеудокодове операција брисања и уметања.

Решење

Можемо приметити да $2^2 - 1^2 = 3, 3^2 - 2^2 = 5, 4^2 - 3^2 = 7, ...$ што значи да уместо квадрирања можемо да радимо само сабирање са следећим непарним бројем.

DELETE(H, key)
i = init = H(key)
step = 3
while (T[i] ≠ key) and (T[i] ≠ empty) do
    if (step ≠ 3) and (i = init) then
        return
    end_if
    i = i + step
    step = step + 2
end_while
if T[i] ≠ empty then
    T[i] = deleted
end_if
INSERT(H, key)
i = init = H(key)
step = 3
while (T[i] ≠ empty) and (T[i] ≠ deleted) do
    if (step ≠ 3) and (i = init) then
        ERROR(Tabela puna)
    end_if
    i = i + step
    step = step + 2
end_while
T[i] = key

8. задатак

Поставка

Објаснити како се може моделирати понашање алгоритама сортирања поређењем. За дати модел извести теоријску границу сложености у најгорем случају.

Решење

Понашање алгоритма се може моделирати стаблом одлучивања. Свако одлучивање се моделује унутрашњим чвором а сваки исход листом, тако да сложеност у најгорем случају добијамо као висину тог стабла. Пошто је број исхода оваквог стабла одлучивања једнак $n!$, а највећи број листова у стаблу висине $h$ једнак $2^h$, можемо да изједначимо $n! = 2^h$. Кад логаритмујемо обе стране једначине и применимо Стирлингову апроксимацију ($n! > \left(\frac{n}{e}\right)^n$) добијамо $h = \log(n!) > n \log\left(\frac{n}{e}\right) > n \log n - n \log e = O(n \log n)$.