Dowód poprawności:

• a_1 = a, a_k = 1, a_{i+1} = floor(a_i/2). Niech a = \sum_{i=1}^{k}2^{i-1}\overline a_i, \overline a_k \in \{0,1\}, czyli zapis a w postaci binarnej. Wtedy a_n = \sum_{i=1}^{n}2^{i-1}\overline a_{i+(k-n)}, czyli a_n = \overline a_k \overline a_{k-1} … \overline a_{n}.
• b_1 = b, b_{i+1} = 2b_i \Rightarrow b_i = 2^ib
• Dowod: \sum_{i=1, nieparzyste(a_i)}^kb_i = \sum_{i=1}^k \overline a_i 2^i b = b \sum_{i=1}^k 2^i \overline a_i = ab.

• kryterium jednorodne - koszt każdej operacji maszyny RAM jest jednostkowy.
• kryterium logarytmicznym - koszt operacji maszyny RAM jest równy sumie długości operandów.

Mnożymy: a*b:

• Kryterium jednorodne: Tyle dodawań, ile jedynek w zapisie binarnym liczby b: O(ceil(log_2(b)))
• Kryterium logarytmiczne: Tyle samo dodawań. Długość operandów: conajmniej ceil(log_2(a)), conajwyżej: ceil(log_2(a*b)). O(ceil(log_2(b)) * ceil(log_2(a*b)).

Liniowa kombinacja skończonej liczby poprzednich (liczba = b). Niech f_n = a_bf_{n-b} + a_{b-1}f_{n-b+1} + … + a_1f_{n-1}. a_i mogą być zerowe lub ujemne. Mając ciąg (f_{n-1}, f_{n-2}, …, f_{n-b}), chcąc otrzymać element f_n oraz móc obliczać kolejne elementy musimy wyliczyć f_n ze wzoru i przeshiftować nasz ciąg.

Macierz:

• m_{yx} = 1 if x == y + 1 else
• m_{yx} = 0 if y < n else
• m_{nx} = a_{n-x+1} indeksy jakos tak

Przykład dla b == 3: \left[\begin{array}{ccc}0&1&0\\0&0&1\\a_3&a_2&a_1\end{array}\right]

Macierz jest rozmiaru (n+m) na (n+m), n - ilosc poprzednich wyrazow ciagu rekurencyjnego, m - stopien wielomianu. Podzielmy macierz na cztery prostokaty. Lewy gorny jest taki sam jak w poprzednim zadaniu. Prawy gorny jest zerami, oprocz ostatniego wiersza, ktory jest wspolczynnikami wielomianu. Lewy dolny to zera. Prawy dolny to glowna trudnosc zadania.

Argument i wynik to macierz (f_1, f_2, \dots, f_n, n^m, n^{m-1}, \dots, 1)^T - f_i - wspolczynnik przy wyrazie w wyrazeniu rekurencyjnym (to co w poprzednim zadaniu). Jak uzyskac (n+1)^i? Przyklad dla i = 2:

(n+1)^2 = n^2 + 2n + 1. Czym sa 1, 2 i 1? Kolejnymi wartosciami dwumianu newtona. Dolna prawa czesc macierzy ma takie wiersze:

\left[\begin{array}{ccc}{n \choose n}&{n \choose n-1}&{n \choose n-2}&\dots&{n \choose 0}\\0&{n-1 \choose n-1}&{n-1 \choose n-2}&\dots&{n-1 \choose 0}\\\dots\\0&0&\dots&0&1 \end{array}\right]

Pesymistyczny koszt dodania to O(2*sqrt(n)), i ewentualnie przesuniecie kilku wskaznikow o jeden w przod, +jakies obliczenia +O(sqrt(n)). To jest lista, nie tablica

Mamy liste L. Wizualizujemy w glowie liste jako kwadrat, o boku sqrt(n). Wtedy mozemy zrobic dodatkowa liste o dlugosci sqrt(n) ze wskaznikami na pierwsze elementy kazdej kolumny tego kwadratu. Przy insertowaniu nowego elementu najpierw przechodzimy liste ze wzkaznikami, a potem liste L od wskazywanego miejsca. Maksymalna ilosc przejsc to 2*sqrt(n), jesli insertujemy na koniec. Po wstawieniu nowego elementu musimy odswiezyc liste wskaznikow, co ma koszt sqrt(n).

http://en.wikipedia.org/wiki/Longest_path_problem

algorithm dag-longest-path is
    input: 
         Directed acyclic graph G
    output: 
         Length of the longest path

    length_to = array with |V(G)| elements of type int with default value 0

    for each vertex v in topOrder(G) do
        for each edge (v, w) in E(G) do
            if length_to[w] <= length_to[v] + weight(G,(v,w)) then
                length_to[w] = length_to[v] + weight(G, (v,w))
 
    return max(length_to[v] for v in V(G))