1. Klasówka 2012/13

Zadanie 1

Słowa kluczowe: optymalne porównania

Udowodnij, że do scalania dwóch ciągów uporządkowanych długości \(2\) i \(5\) potrzeba i wystarcza \(5\) porównań.

Zadanie 2

Słowa kluczowe: teksty

Powiemy, że dwa napisy są podobne wtedy i tylko wtedy, gdy zawierają jednakowe liczby wystąpień tych samych znaków. Danych jest \(n\) napisów nad alfabetem \(m\)-znakowym \(\{1, 2, \cdots, m\}\). Zaproponuj algorytm, który stwierdza, ile jest wśród nich różnych klas napisów podobnych. Twój algorytm powinien działać w czasie \(O(R + m)\), gdzie \(R\) jest sumą długości wszystkich napisów.

Zadanie 3

Słowa kluczowe: sortowanie, w miejscu, stabilnie

Dana jest \(2n\)-elementowa tablica zawierająca \(n\) zer i \(n\) jedynek. Chcemy ją uporządkować tak, żeby zera i jedynki były ułożone na przemian, począwszy od zera, tj. \(010101...\). Zaproponuj efektywny algorytm, który wykona to w miejscu i stabilnie (tj. kolejność zer i kolejność jedynek z wejścia muszą być zachowane).

Podpowiedź

Rozwiązanie o złożoności \(O(n\log n)\). Krok pierwszy to posortowanie (stabilnie) ciągu za pomocą MergeSort (ciągi 0/1 łatwo stabilnie scalić). Następnie musimy rozrzucić 1 w odpowiednie pozycje co również robimy rekurencyjnie.

Aby uniknąć dodatkowej pamięci na utrzymywanie rekurencji, może ją zastąpić przez iterację. Dla MergeSort scalamy fragmenty o długości kolejnych potęg dwójek. Natomiast przy rozrzucaniu jedynek kolejność jest odwrotna (zaczynamy od najdłuższych przedziałów a kończymy na przedziałach długości 2).

def merge01(a, i, j, k):
    """merge sorted intervals a[i..j) and a[j..k)"""
    assert 0 <= i < j < k <= len(a)
    c_left_1 = a[i:j].count(1)
    c_right_0 = a[j:k].count(0)
    if c_left_1 > 0 and c_right_0 > 0:
        transpose(a, j - c_left_1, j, j + c_right_0)


def sort01(a):
    n = len(a)
    p = 1
    while p < n:
        for i in range(0, n - p, 2 * p):
            merge01(a, i, i + p, min(n, i + 2 * p))
        p *= 2
    return a


def interleave01(a):
    assert a.count(0) == a.count(1)
    n = len(a)
    a = sort01(a)
    p = 2 ** (log2(n - 1))
    while p >= 2:
        for i in range(0, n - p, 2 * p):
            left, middle, right = i, i + p, min(n, i + 2 * p)
            c0 = (right - left) // 2
            assert c0 == a[left:right].count(0) == a[left:right].count(1)
            l0 = (middle - left) // 2
            r0 = (right - middle) // 2

            transpose(a, left + l0, left + c0, right - r0)

            assert a[left:middle] == ([0] * l0 + [1] * l0)
            assert a[middle:right] == ([0] * r0 + [1] * r0)
        p = p // 2
    return a