PAA - Listas de exercícios de 2006.2 (prof. Poggi)

Primeira lista

Exercício 1

Não tenho muita certeza em relação ao item (g). Só consegui chegar a (g) = $n\log_n{2}$. A ordem que achei foi:
f > a > j ~ d > e > g ~ h > b ~ c > i

Exercício 2

Tive que usar o teorema mestre do Cormen para fazer a complexidade do (d).

(a) $O(n^{1/2}\log{n})$
(b) $O(n^{\log_4{3}})$
(c) $O(n^{1/2}\log{n})$
(d) $O(n^{1/2})$

Exercício 3

A1: $O(\log{\log{n}})$ e $\Omega(1)$
A2: $O(\log{\sqrt{n}})$ e $\Omega(1)$. $T(n) = T(\frac{\sqrt{n}}{2})$ ou $T(n) = T(n - 2\sqrt{n})$
A3: $O(n)$ e $\Omega(\log{n})$. $T(n) = T(\frac{n}{2}) + n$
A4: $O(n)$ e $\Omega(n^{\log_5{3}})$. $T(n) = 3T(\frac{n}{5}) + n$

Exercício 6

(a)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>
 
using namespace std;
 
#define FOR(i,n) for (int i=0;i<n;i++)
#define FORA(i,a,b) for (int i=a;i<b;i++)
#define all(c) (c).begin(),(c).end()
#define sz(c) (int)((c).size())
 
vector<int> randomVector(int n) {
        //srand(time(0));
        srand(45355);
        vector<int> v(n,0);
        FOR(i,n) v[i] = rand()%(1<<5);
        return v;
}
void printVector(vector<int> &v) {
        FOR(i,sz(v)) cout << v[i] << " ";
        cout << endl;
}
 
int main() {
        int n;
        cin >> n;
        vector<int> V = randomVector(n);
 
        int numInversoes = 0;
        FOR(i,n) FORA(j,i+1,n) {
           if (V[j] < V[i]) numInversoes++;
        }
        printVector(V);
        cout << numInversoes << endl;
 
        return 0;
}

(b)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>
 
using namespace std;
 
#define FOR(i,n) for (int i=0;i<n;i++)
#define FORA(i,a,b) for (int i=a;i<b;i++)
#define all(c) (c).begin(),(c).end()
#define sz(c) (int)((c).size())
 
vector<int> randomVector(int n) {
        //srand(time(0));
        srand(45355);
        vector<int> v(n,0);
        FOR(i,n) v[i] = rand()%(1<<5);
        return v;
}
void printVector(vector<int> &v) {
        FOR(i,sz(v)) cout << v[i] << " ";
        cout << endl;
}
 
const int INF = 1000000000;
int mistura(vector<int> &v, int b, int m, int e) {
        int N1 = (m-b+1);
        int N2 = (e-m);
        vector<int> L(N1+1,INF);
        vector<int> R(N2+1,INF);
 
        FOR(i,N1) L[i] = v[b+i];
        FOR(i,N2) R[i] = v[m+1+i];
 
        // conta as inversoes O(N1 + N2) = O(N)
        int ret = 0, pL = 0, pR = 0;
        while (pR < N2) {
           while (pL < N1 && L[pL] <= R[pR]) pL++;
           ret += (N1 - pL);
           pR++;
        }
 
        // intercala e retorna ordenado
        int k = b;
        pL = pR = 0;
        while (k <= e) {
           if (L[pL] < R[pR])
                v[k] = L[pL++];
           else
                v[k] = R[pR++];
           k++;
        }
        return ret;
}
 
int numInversoes(vector<int> &v, int b, int e) {
        if (b < e) {
           int meio = (b+e)/2;
           int left = numInversoes(v,b,meio); // inversoes do lado esquerdo
           int right = numInversoes(v,meio+1,e); // inversoes do lado direito
           int mix = mistura(v,b,meio,e); // inversoes da mistura dos dois lados
           return left + right + mix;
        }
        return 0;
}
 
int main() {
        int n;
        cin >> n;
        vector<int> V = randomVector(n);
        printVector(V);
 
        cout << numInversoes(V,0,sz(V)-1) << endl;
 
        return 0;
}

(c)

$T(n) = 2T(\frac{n}{2}) + 2n$

(d)

O primeiro algoritmo é $O(n^2)$, enquanto o segundo é $O(n\log{n})$. No segundo algoritmo estamos fazendo uma ordenação igualzinha ao merge-sort, só que na hora de juntar os dois pedaços (intercalar as duas sub-listas ordenadas) nós "aproveitamos" e contamos as inversões.

Exercício 7

Semelhante a um exercício de outra lista.

Exercício 8

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>
 
using namespace std;
 
#define FOR(i,n) for (int i=0;i<n;i++)
#define FORA(i,a,b) for (int i=a;i<b;i++)
#define all(c) (c).begin(),(c).end()
#define sz(c) (int)((c).size())
 
vector<int> randomVector(int n) {
        vector<int> v(n,0);
        FOR(i,n) v[i] = rand()%(1<<5);
        return v;
}
void printVector(vector<int> &v) {
        FOR(i,sz(v)) cout << v[i] << " ";
        cout << endl;
}
 
int main() {
        srand(time(0));
        int n, k;
        cin >> n >> k;
        vector<int> S = randomVector(n), T = randomVector(k);
        sort(all(S));
        sort(all(T));
        cout << "S -> "; printVector(S);
        cout << "T -> "; printVector(T);
 
        int i = 0, j = 0;
        while (i < n && j < k) {
           if (S[i] == T[j])
                j++;
           else
                i++;
        }
        cout << (j == k ? "SIM" : "NAO") << endl;
 
        return 0;
}

Exercício 14

(ver exercício 4 da lista de 2007.1)
Complexidade do algoritmo original: $O(n^2)$ (recorrência $T(n) = 4T(\frac{n}{2}) + O(n)$).
Complexidade do algoritmo modificado: $O(n^{\log{3}})$ (recorrência $T(n) = 3T(\frac{n}{2}) + O(n)$).

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.