---
title: AiSD Lista 1
tags: aisd
author: Mateusz Reis
---
# AiSD Lista 1

## Zadanie 1

Przyjmujemy reprezentacje drzewa w postaci listowej to znaczy $T[i]=\{l,r\}$
co oznaczna że wierzchołek $i$ ma dzieci $l$ oraz $r$. Dodatkowo jeśli $l=0$ lub $r=0$ to wierzchołek $i$ nie ma dziecka $l$ lub $r$.

- a

Idea: pytamy każdego dziecka ile ma dzieci(inaczej dla każdego wierzchołka sprawdzamy ile ma wierzchołków pod sobą)
Procedurę odplalamy podając jej na wejściu argumenty w postaci tablicy T i indeksu początkowego $i=1$

procedure count_nodes(T[1..n],i):
    sum<-1
    if(T[i].l!=0):
        sum<-sum+count_nodes(T,T[i].l)
    if(T[i].r!=0)
        sum<-sum+count_nodes(T,T[i].r)
    return sum

Złożoność to $O(n)$ ponieważ w każdym przypadku odwiedzimy wszystkie wierzchołki i zrobimy to raz.

- b

Idea: Zaczynamy od korzenia i sprawdzamy długość każdego poddrzewa następnie wybieramy większą długość i dodajemy 1 za nasz wierzchołek.

procedure longest_path(T[1..n],v)
    res<-1
    if T[1].l!=0 do:
        res<-res+longest_path(T,T[1].l)
    if T[1].r!=0 do:
        res<-max(res,1+longest_path(T,T[1].r))
    return res
        
procedure path(T[1..n])
    res<-0
    if T[1].l!=0 do:
        res<-res+longest_path(T,T[1].l)
    if T[1].r!=0 do:
        res<-res+longest_path(T,T[1].r)
    return res

## Zadanie 2

Kopiec minmaksowy to kopiec w którym poziomy przeplatają się nawzajem raz poziom-min raz poziom-maks. W najwyższym wierzchołku (czyt. roocie), czyli na zerowym poziomie jest element najmniejszy w całym kopcu, zaś na pierwszym poziomie, czyli tam gdzie synowie korzenia, jest element największy.

* ```c=
procedure push_down(K[1..n], i)
if log(i)%2 == 1 then:
push_down_max(K[1..n], i)
else:
push_down_min(K[1..n], i)

procedure push_down_min(K[1..n], i)
if 4*i<=n then:
m <- min(K[4*i..8*i-1])
if K[m] < K[i] then:
swap K[m] and K[i]
push_down_min(K[1..n], m)
else if 2*i<=n then:
m <- min(K[2*i..4*i-1])
if K[m] < K[i] then:
swap K[m] and K[i]

procedure push_down_max(K[1..n], i):
if 4*i<=n then:
m <- max(K[4*i..8*i-1])
if K[m] > K[i] then:
swap K[m] and K[i]
push_down_min(K[1..n], m)
else if 2*i<=n then:
m <- max(K[2*i..4*i-1])
if K[m] > K[i] then:
swap K[m] and K[i]

* ```c=
procedure min_del(K[1..n])
K[1] <- K[n]
push_down(K[1..n − 1], 1)

* ```c=
procedure max_del(K[1..n])
if K[2] >= K[3] then:
K[2] <- K[n]
push_down(K[1..n − 1], 2)
else:
K[3] <- K[n]
push_down(K[1..n − 1], 3)
Procedury `push_up` i jej podprocedury `push_up_min` oraz `push_up_max` są tylko wtedy wykorzystywane, gdy insertujemy jakieś elementy, w przypadku porządkowania przy usuwaniu działa tylko `push_down`
## Zadanie 3


Przyjmujemy że reprezentujemy graf za pomocą macierzy sądziedztwa. Na początku znajdziemy wierzchołki o stopniu wejściowym 0. Następnie na tych wierzchołkach odpalimy DFS-a który przejdzie wszystkie kolejne wierzchołki zawsze zaczynając od najwiekszego. W naszej macierzy $G$ mamy $G[v][u]=1$ jeśli istnieje krawędź z $v$ do $u$ wpp $G[v][u]=0$.

out<-[]
visited<-[]

procedure DFS_visit(G[1..n][1..n],v)
    if visited[v]==true do:
        return 
    else 
        visited[v]<-true
    
    for i<-n to 1 do:
        if G[v][i]==1 do:
            DFS_visit(G,i)
    //dodajemy na początek listy wyjściowej
    out<-v+out
    


procedure top_sort(G[1..n][1..n])
    //znajdujemy wierzchołki, które mają stopień wejściowy 0
    origins<-[]
    for i<-1 to n do:
        has_inc<-false
        for k<-1 to n do:
            if G[k][i]==1:
                has_inc<-true
        if has_inc==false:
            origins<-origins+i
            
    //następnie odwiedzamy wierzchołki o stopniu 0 
    //a następnie przechodzimy do ich sąsiadów
    for i<-origins.size to 1 do:
        DFS_visit(G,origins[i])

Złożoność czasowa to $O(n^2)$ ponieważ za każdym razem przeglądamy całą macierz. Jeśli przyjmiemy że na początku dostajemy graf w postaci listowej oraz listę wierzchołków o stopniu 0 złożoność spadnie do $O(n+m)$.

Przykład:
:red_circle: - kolejność odwiedzania wierzchołków
:large_blue_circle: - kolejność dodawania wierzchołków


Wynik
:::success
4 5 0 2 3 1
:::

## Zadanie 4

Idea : Wywołujemy algorytm Djikstry dla wierzchołka $v$ i zapisujemy minimalne ścieżki dla każdego wierzchołka. Następnie przechodzimy od $u$ do jego sąsiadów którzy mają krótsze ścieżki do $v$.

procedure djikstra(G[1..n],c,s,e)
    d<-[]
    prev<-[]
    
    for i<-1 to n do:
        d[i]<-inf
        prev[i]<-(-1)
    
    d[s]=0    
    Q<-[1..n]
    
    while not Q.empty() do:
    
        //wierzchołek najbliżej s, który nie został jeszcze rozważony
        u<-min(Q)
        for i in G[u] do:
            if d[i]>d[i]+c[u,i] do:
                d[i]=d[u]+c[u,i]
                prev[i]<-u
                
        return d

procedure count_paths(G[1..n],d[1..n],s,e)
    if s==e do:
        return 1
    
    ans<-0
    for i in G[s] do:
        if d[i]<d[s] do:
            ans<-ans+count_paths(G,d,,i,e)
    return ans

procedure good_path(G,c,u,v)
    
    d=djikstra(G,c,v,u)
    return count_paths(G,d,u,v)

## Zadanie 5

Tworzymy tablicę długości ścieżek którą uzupełniamy za pomocą DFS-a, sprawdzając wszytskie możliwe ścieżki. Ostania największa ścieżka będzie prowadziła przez ostatniego sąsiada aktualnie odwiedzanego wierzchołka dla którego istnieje ścieżka o tej samej długości. Aby wypisać ścieżki Przechodzimy do kolejnych wierzchołków sprawdzając największe ścieżki dla naszych sąsiadów od ostaniego gwarantuje to nam wypisanie dokładnie najdłuższej ścieżki.

procedure dfs(node, adj[1..n], dp[1..n]) 
     
    for i<-1 to adj[node].size() do:
        dfs(adj[node][i], adj, dp)
        dp[node] = max(dp[node], 1 + dp[adj[node][i]])
 
procedure dfs_print(node,adj[1..n],dp[1..n],length)
    if length==0 do:
        print(node)
    i<-adj.size()
    found<-false
    next<-0
    while not found:
        if dp[adj[node][i]]==length do:
            found=true
            next<-i
        i<-i+1
    print(node+"->")
    dfs_print(next,adj,dp,length-1)

procedure findLongestPath(adj[], n)  
    dp[] 
    
    for i<-1 to n do: 
        dfs(i, adj, dp) 

    int ans = 0 
    for i<-1 to n do:
        if dp[i]>ans do:
            ans = dp[i]
            start=i
    dfs_print(start,adj,dp,ans)

Złożoność czasowa $O(m+n)$ tyle potrwa nasz DFS który będzie szukał najdłuższej ściezki ponieważ odwiedzi wszystkie krawędzie i wszystkie wierzchołki. Wypisanie to kwestia $O(n)$ ponieważ tyle potrwa w najgorszym wypadku odwiedzenie wszystkich wierzchołków na ścieżce.

## Zadanie 6

Dzielimy wejściowy ciąg $a_n$ na dwa podciągi. Jeden o długości $\lceil\frac{n}{2} \rceil$, a drugi o długości $\lfloor\frac{n}{2} \rfloor$. Nazwijmy je odpowiednio $L$, jako lewy podciąg i $P$, jako prawy podciąg.
Teraz będziemy chcieli łączyć w pary każdy element $l_i \in L$ z odpowiadającym mu elementem $p_i \in P$ dla $i \in \text{[ }\lfloor\frac{n}{2} ... n\rfloor \text{]}$. Dla n parzystych będziemy mogli usunąć nawet wszystkie elementy, a dla $2\not| \,\,\,\, n$ przynajmniej jeden zostanie nieusunięty.

procedure delete_elems(A[1..n], n)
    count <- 0
    i<-0
    for k<- 1 to n/2 do:
        deleted<-false
        while not deleted and i<=n do:
            if(2 * A[k] <= A[n/2+k+i]) then:
                count <- count + 2
                deleted<-true
            i<-i+1
    return count