====== Zadanie 1 ======
http://users.eecs.northwestern.edu/~dda902/336/hw4-sol.pdf  Problem 2.31
To jest zadanie 2
[[http://ii.yebood.com/viewtopic.php?p=21280#21280|http://ii.yebood.com/viewtopic.php?p=21280#21280]]

====== Zadanie 2 ======
http://www.ift.uni.wroc.pl/~plg/download/aisd-01.pdf

====== Zadanie 3 ======
http://www.mimuw.edu.pl/~idziaszek/zajecia/ia/drzewa.html

====== Zadanie 4 ======
http://ii.yebood.com/viewtopic.php?p=83454#83454

====== Zadanie 5 ======
a) W wektorze pamiętamy pierwszą kolumnę oraz pierwszy wiersz bez pierwszego wyrazu. Wektor ten ma rozmiar $2n - 1$, więc dodawanie dwóch takich wektorów mamy w $O(n)$.

b) Macierz Toeplitza ma następującą postać blokową:

$\displaystyle T = \left[ \matrix{A & B\\\\ C & A} \right]$

Zadanie polega na pomnożeniu macierzy $T$ przez wektor blokowy $\displaystyle T = \left[ \matrix{x \\\\ y} \right]$ w czasie mniejszym niż $n^2$.

Korzystając z dwóch (wzajemnie dualnych) obserwacji:

$Ax = A(x + y - y) = A(x+y) - Ay$

$Ay = A(x + y - x) = A(x+y) - Ax$

mamy:

$ T = \left[ \matrix{A & B\\\\ C & A} \right] \left[ \matrix{x \\\\ y} \right]
 = \left[ \matrix{Ax + By\\\\ Cx + Ay} \right] 
 = \left[ \matrix{A(x+y)-Ay + By\\\\ Cx + Ay} \right]
 = \left[ \matrix{A(x+y)+(B - A)y\\\\ Cx + Ay} \right]
 = \left[ \matrix{A(x+y)+(B - A)y\\\\ Cx + A(x+y) - Ax } \right]
 = \left[ \matrix{A(x+y)+(B - A)y\\\\ A(x+y) + (C-A)x} \right]$.

I zauważamy, że złożoność czasowa to $T(n) = 3 T(n/2) + O(n)$ gdzie $O(n)$ zamyka sumę liniowych czasów wszystkich dodawań. 

Rozwiązując typowe równanie rekurencyjne mamy $T(n) = O(n^{log_2 3}) < O(n^2)$.

====== Zadanie 6 ======
====== Zadanie 7 ======