Prima Provetta

ASD1 2002-2003

Exercise 1   Dire quali delle seguenti affermazioni sono vere. Ove false, fornire un controesempio.

1.

$f(n)=o(g(n))$ implica $f(n) = O(g(n))$.

2.

$f(n) = O(g(n))$ implica $f(n)=o(g(n))$.

3.

$f(n)=O(f(2n))$.

4.

$f(n) = O(g(n))$ implica $2^{f(n) + 3} = O(2^{g(n) + 2})$.

Exercise 2   Si assuma $f(n) = O(g(n))$. Dimostrare che $f(n) + g(n) = \Theta(g(n))$.

Exercise 3   Ordinare le seguenti funzioni per ordine di crescita asintotico non decrescente. Ve ne sono alcune che presentano lo stesso ordine di crescita? $f(n)=3^{\log_2 n}$, $f(n)=3^{\log_3 n}$, $f(n)=3^{\log_4 n}$, $f(n)=\log_2 n$, $f(n)=\log_3 n$,

Exercise 4   Si dimostri che $\log [(n+1)!] = \Theta(n\log n)$.

Exercise 5   Allo scopo di tabulare i valori della seguente ricorrenza

$$C_n = C_{n-1} + C_{n-1} \mbox{\hspace{1cm} per $n\geq 1$, con $C_0=1$}$$

si consideri la seguente procedura iterativa.

#include<iostream.h>

int main() {
  int n; cout << "Dammi n: "; cin >> n; cout << endl;
  long long int T[n +1];   T[0] = 1;
  cout << "T[0] = "  << T[0] << endl;
  for(int k=1; k<=n; k++) {
    T[k] = T[k-1]+T[k-1];
    cout << "T[" << n << "] = "  << T[n] << endl;
  }
}

Si stabilisca l'ordine di crescita del tempo di calcolo della procedura proposta. Si stabilisca l'ordine di crescita della memoria impiegata dalla procedura proposta.

Exercise 6   Il professor Tortoise, propone di utilizzare la seguente procedura ricorsiva allo scopo di tabulare la stessa ricorrenza ( $C_n = C_{n-1} + C_{n-1}$).

#include<iostream.h>

long long int T(int n) {
  if(n==0) return 1;
  return T(n-1) + T(n-1);
}

int main() {
  int n; cout << "Dammi n: "; cin >> n; cout << endl;
  cout << "T[" << n << "] = "  << T(n) << endl;
}

Si stabilisca l'ordine asintotico di crescita per il tempo di calcolo della procedura proposta dal professor Tortoise. Si stabilisca l'ordine di crescita della memoria impiegata dalla procedura di Tortoise.

Complemento 6+ Per questa particolare ricorrenza ( $C_n = C_{n-1} + C_{n-1}$), è possibile pensare ad un accorgimento che consenta di ottenere un buon tempo di calcolo anche per la procedura ricorsiva. Sapresti indicare quale?