====== AiSD Lista 6 ======
===== Zadanie 1 =====

[[http://books.google.pl/books?id=oaVq6dbw37kC&lpg=PA283&ots=VikmbLYx8z&dq=IQSort%20without%20stack&hl=fr&pg=PA283#v=onepage&q&f=false]]
===== Zadanie 2 =====
{{:aisd:aisd02.pdf|}}
===== Zadanie 3 =====
W każdym nodzie trzymać 2 wskaźniki na prev i next.

Odpowiednio aktualizować je przy insert i delete (odpowiednio od liści do korzenia $\Rightarrow$ 2 razy przechodzimy ścieżkę $\Rightarrow$ dalej $O(log n)$.

Podczas balansowania zachowujemy porzadek inorder, wiec nic nie musimy zmieniac.

===== Zadanie 4 =====
===== Zadanie 5, 6 =====
  *http://en.wikipedia.org/wiki/Longest_increasing_subsequence
  *http://en.wikipedia.org/wiki/Longest_common_subsequence_problem
  *http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence.c
<file>
#include <stdio.h>
#include <stdlib.h>

int lcs(int *a, int N) {
        int     *best,
                *prev,
                *num,
                 i,
                 j,
                 max = 0;
        best    = malloc(sizeof(int) * 3 * N);
        prev    = best + N + 1;
        num     = prev + N + 1;

        for (i = 0; i < N; i++) {
                best[i] = 1;
                prev[i] = i;
                num[i]  = 1;
        }

        for (i = 1; i < N; i++) {
                int t = 1;
                for (j = 0; j < i; j++) {
                        if (a[j] < a[i]) {
                                if (best[j] + 1 > t) {
                                        best[i] = t = best[j] + 1;
                                        prev[i] = j;
                                        num[i] = num[j];
                                } else if (best[j] + 1 == t) {
                                        num[i] += num[j];
                                }
                        }
                }
        }

        j = 0;
        for (i = 0; i < N; i++) {
                if (best[j] < best[i]) {
                        j = i;
                        max = num[j];
                } else if (best[j] == best[i]) {
                        max += num[j];
                }
        }

        free(best);

        return max;
}
 
int main(){
        int b[] = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 };
        printf("%d\n", lcs(b, sizeof(b)/sizeof(int)));
        return 0;
}

</file>

===== Zadanie 7 =====
[[http://sourceforge.net/projects/pyavl/|PyAVL]] \\
Procedura split tam jest, wlepiłbym plik, ale nie można uploadować plików bez rozszerzeń, z rozszerzeniami .txt albo .c