---
title: AiSD Lista 0
tags: aisd
author: Mateusz Reis
---
# AiDS - Lista 0

## Zadanie 3


procedure bubble(T[1..n])
    for j<-n-1 to 1 do 
        for i<-1 to j do 
            if T[i]>T[i+1] then
                x<-T[i]
                T[i]<-T[i+1]
                T[i+1]<-x

Idea: przechodzimy po tablicy od początku do końca szukając elementu największego(bąbelka) i "wypychamy" go na sam koniec tablicy.

Jednorodne kryterium:
- Złożoność czasowa - $O(n^2)$ - zawsze
- Uzasadnienie: na początku zauważmy że instrukcja **if** prowadzi do wykonania stałej liczby instrukcji, natomiast wewnętrzna pętla **for** wykona swoje instrukcje $\theta(n^2)$ razy, natomiast jej instrukcje zajmą czas stały, więc złożoność czasowa to $\theta(n^2)$

Porównanie:
- bubblesort vs selectionsort - złożoność czasowa jest taka sama, ponieważ algorytmy dla każdych danych wejściowych o tym samym rozmiarze wykonają taką samą liczbe operacji. Jednakże mamy dużo więcej operacji przypisania w select niż bubble, co na pewno wpłynie na rzeczywistą wydajność, natomiast liczba porównań jest taka sama.

- bubblesort vs insertionsort - złożoność czasowa przemawia za insertionsort, ponieważ dla niektórych przypadków wykona dużo mniej operacji niż bubblesort, natomiast jest to zdecydowanie rzadka sytuacja. Co warto zauważyć pętla while wykonuje dwa porównania przy każdym obrocie(co z punktu widzenia predykcji skoków może zaboleć, ale to chyba nie jest temat na ten przedmiot) oraz ogólna liczba przypisań jest większa niż w bubble co może spowodować że dla wybranych przypadków procedura bubble zadziała dużo szybciej niż insert.

## Zadanie 4

algorytm w pseudokodzie:

procedure russ_mult(a,b)
    out<-0
    while a>0 do 
        if a%2==1 then
          out<-out+b
        a<-a/2
        b<-b*2
    return out

Jeśli pomyślimy o $a$ w postaci binarnej to możemy zauważyć że algorytm usuwa ostatni bit i sprawdza czy kolejny jest ustawiony na 1, jeśli tak to do wyniku dodaje $b*2^i$. Jeśli binarnie pomnożymy $a$ przez $b$ w sposób pisemny
$$
a = 3,\,b=5\\
\begin{matrix}
&&0&1&0&1\\
*&&0&0&1&1\\
-&-&-&-&-&-\\
&&0&1&0&1\\
+&0&1&0&1&\\
-&-&-&-&-&-\\
&0&1&1&1&1\\
\end{matrix}
$$
otrzymamy dokładnie oczekiwany wynik, a to dokładnie robi nasz algorytm. Możemy te operacje zapisać jako
$$
\sum_{i=0}^{log(a)}a_i2^ib=b\sum_{i=0}^{log(a)}a_i2^i=ba
$$
gdzie $a_i$ to i-ty bit liczby $a$.
- Złożoność czasowa takiego algorytmu przy kryterium jednorodnym to $O(\log(a))^*$ ponieważ tyle razy wykona się pętla while.
*log to oczywiście logarytm o podstawie 2
- Złożoność pamięciowa to $O(1)$ ponieważ tworzymy tylko 1 dodatkową zmienną do której będziemy dodawać kolejne liczby $b$

- Złożoność czasowa przy kryterium logarytmicznym to $\log(a)$ obrotów pętli, w której wykonujemy maksymalnie dodawanie o koszcie $log(a*b)$ oraz zawsze $\log(a)$ mnożeń i dzieleń. Co w pesymistycznym przypadku gdzie liczba a ma zapalone wszystkie bity daje $3\log(a)*m$ operacji, gdzie $m$ to koszt operacji na dwóch liczbach wykonywanej przez maszynę RAM. Łącznie otrzymujemy złożoność $O(\log(a)\log(a)m)$
- Złożoność pamięciowa przy liczbach $a$ i $b$ to liczba bitów które musimy zapamiętać w naszej sumie czyli $O(\log(ab))$

## Zadanie 5

## Zadanie 6

Algorytm odejmuje od siebie elementy zbioru tak długo aż zostanie tylko 1 a na końcu zwraca parzystość wyniku. W takim razie wiemy że tylko rożnica jest nieparzysta tylko kiedy odejmujemy liczby o rożnej parzystości. Do tego możemy użyć operacji bitowej XOR. Tak więc algorytm może wyglądać tak:

procedure odd_even(A[1..n])
    out<-0
    for i<-1 to n do
        out<-A[i]%2^out
    return out

Jeśli tylko będzie to możliwe to nasza złożoność pamięciowa to jeden bit na wynik + rozmiar tablicy.

## Zadanie 7

Mój algorytm będzie przechodził ścieżki z wierzchołka do korzenia i sprawdzał czy nie napotkał na wierzchołek którego szukamy. Jeśli dojdzie do korzenia i nie będzie on wierzchołkiem docelowym wtedy zwróci false, jeśli wcześniej napotka żądanyt wierzchołek zwróci true.

Algorytm:
//Wejście: Q-lista par {vi,ui},T-lista par {pi,ai}
//Wyjście: lista m-elementowa z wartościami True/False, gdzie i-ty element odpowiada i-tej parze

l<-[]
dla każdej pary q z Q:
start<-q.ui
koniec<-q.vi

dopóki start != korzen oraz start != koniec:
q<-(pi,start):
start<-pi

jeśli start==korzen:
l<-l u {False}
wpp:
l<-l u {True}