%% LyX 1.3 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[a4paper,english]{article}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\pagestyle{plain}
\setcounter{secnumdepth}{0}
\setlength\parskip{\medskipamount}
\setlength\parindent{0pt}
\usepackage{float}
\usepackage{amsmath}
\usepackage{amssymb}

\makeatletter

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
%% Because html converters don't know tabularnewline
\providecommand{\tabularnewline}{\\}
\floatstyle{ruled}
\newfloat{algorithm}{tbp}{loa}
\floatname{algorithm}{Algorithm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{graphicx}
%\usepackage{sw20exm2}

%TCIDATA{OutputFilter=LATEX.DLL}
%TCIDATA{Created=Sat Apr 15 15:45:18 2000}
%TCIDATA{LastRevised=Sun Apr 06 21:46:28 2003}
%TCIDATA{<META NAME="ViewSettings" CONTENT="1">}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="DocumentShell" CONTENT="Exams and Syllabi\TCI Exam #1 - 8.5 x 14 Page">}
%TCIDATA{Language=Portuguese (Continental)}
%TCIDATA{CSTFile=Exam.cst}
%TCIDATA{PageSetup=72,72,72,72,0}
%TCIDATA{Counters=arabic,1}
%TCIDATA{AllPages=
%H=36
%F=36
%}


\setlength{\topmargin}{-0.75in}
\setlength{\textheight}{9.75in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\evensidemargin}{0.0in}
\setlength{\textwidth}{6.5in}
\def\labelenumi{\arabic{enumi}.}
\def\theenumi{\arabic{enumi}}
\def\labelenumii{(\alph{enumii})}
\def\theenumii{\alph{enumii}}
\def\p@enumii{\theenumi.}
\def\labelenumiii{\arabic{enumiii}.}
\def\theenumiii{\arabic{enumiii}}
\def\p@enumiii{(\theenumi)(\theenumii)}
\def\labelenumiv{\arabic{enumiv}.}
\def\theenumiv{\arabic{enumiv}}
\def\p@enumiv{\p@enumiii.\theenumiii}
\newtheorem{theorem}{Theorem}
\newtheorem{acknowledgement}[theorem]{Acknowledgement}
%\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{case}[theorem]{Case}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conclusion}[theorem]{Conclusion}
\newtheorem{condition}[theorem]{Condition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{solution}[theorem]{Solution}
\newtheorem{summary}[theorem]{Summary}
\newenvironment{proof}[1][Proof]{\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
%\input{tcilatex}

\usepackage{babel}
\makeatother
\begin{document}

\section{An\'{a}lise de Algoritmo - 2007/1}

\noindent Nome:\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad
\qquad \qquad \qquad \qquad \qquad \qquad

\begin{enumerate}
\medskip{}
\item Para cada par $\left\langle f(n),g(n)\right\rangle $ de fun\c{c}\~{o}es
abaixo, indique se $f(n)=o(g(n))$, $f(n)=\theta(g(n))$ ou $g(n)=o(f(n))$:

\begin{enumerate}
\medskip{}
\item $\left\langle n\lg(n^{3}),n(\lg n)^{3}\right\rangle $
\medskip{}
\item $\left\langle 2^{n/2},2^{n}\right\rangle $
\end{enumerate}
\medskip{}
\item Considere o problema de ordenar $n$ n\'{u}meros armazenados em um
vetor $A$ empregando o seguinte m\'{e}todo:


\medskip{}
Encontre o menor elemento de $A$, coloque-o na primeira posi\c{c}\~{a}o
de um outro vetor $B$. A seguir encontre o segundo menor elemento
de $A$ e o coloque na segunda posi\c{c}\~{a}o de $B$. Prossiga
desta maneira para os $n$ elementos de $A$. D\^{e} o tempo de execu\c{c}\~{a}o,
de forma exata, para o melhor e pior caso. (Mostre como você obteve
os resultados).%
\begin{algorithm}[H]

\caption{Sort$(A,B,n)$}

for $i\leftarrow1$ to $n$

\qquad min$\leftarrow$1

\qquad for $j\leftarrow2$ to $i$

\qquad \qquad do if $(A[j]<A[min])$

\qquad \qquad \qquad then min $\leftarrow j$

\qquad $B[n-i+1]\leftarrow A[min]$

\qquad $A[min]\leftarrow A[i]$
\end{algorithm}


\medskip{}
\item Considere algoritmo mostrado abaixo. Determine o seu tempo de execução.


\medskip{}
%
\begin{algorithm}[H]
int \textbf{function} x(int n)

\qquad if $n\leq2$

\qquad \qquad then return (1)

\qquad \qquad else return ($1+x(\sqrt{n})$)
\end{algorithm}


\medskip{}
\item Compare os seguintes pares de fun\c{c}\~{o}es em termos da sua ordem
de magnitude. Em cada caso, diga se $f(n)=O(g(n)),f(n)=\Omega(g(n)),$
e/ou $f(n)=\Theta(g(n)).$


\medskip{}
\begin{tabular}{ccc}
&
 $f(n)$&
 $g(n)$\tabularnewline
 a) &
 $n+(\log n)^{2}$&
 $2n+(\log n)^{3}$\tabularnewline
 d) &
 $n^{0.6}$&
 $(\log n)^{3}$\tabularnewline
\end{tabular}

\medskip{}
\item Compare os seguintes pares de fun\c{c}\~{o}es em termos da sua ordem
de magnitude. Em cada caso, diga se $f(n)=O(g(n)),f(n)=\Omega(g(n)),$
e/ou $f(n)=\Theta(g(n)).$


\medskip{}
\begin{tabular}{ccc}
&
 $f(n)$&
 $g(n)$\tabularnewline
 b) &
 $\log n^{2}$&
 $\log(n^{5})$\tabularnewline
 c) &
 $\frac{n^{2}}{\log^{3}n}$&
 $n(\log n)^{3}$\tabularnewline
\end{tabular}

\medskip{}
\item Para o seguinte par de fun\c{c}\~{o}es, mostre qual cresce mais
e porque:


\medskip{}
$2^{(\lg n)^{2}}$ou $(2^{\lg n})^{2}$

\medskip{}
\item Para o seguinte par de fun\c{c}\~{o}es, mostre qual cresce mais
e porque:


\medskip{}
$n\left(2+\frac{\lg n}{n^{0.5}}\right)$ou $\lg\lg n$

\medskip{}
\item Para o seguinte par de fun\c{c}\~{o}es, mostre qual cresce mais
e porque:


\medskip{}
$\underset{i=0}{\overset{n}{\sum}}0.9^{i}$ou $\underset{i=1}{\overset{n}{\sum}}\frac{1}{i}$

\medskip{}
\item Para o seguinte par de fun\c{c}\~{o}es, mostre qual cresce mais
e porque:


\medskip{}
$(1.2)^{n-1}+\sqrt{n}+\lg n$ ou $n^{1.5}$

\medskip{}
\item Prove a seguinte afirma\c{c}\~{a}o: Se $f_{1}(n)=O(g_{1}(n))$ e
$f_{2}(n)=O(g_{2}(n))$ ent\~{a}o $f_{1}(n)\cdot f_{2}(n)=O(g_{1}(n)\cdot g_{2}(n))$.
\medskip{}
\item Assuma que $f(n)$ e $g(n)$ s\~{a}o duas fun\c{c}\~{o}es assint\'{o}ticamente
positivas. Prove a verdade ou falsidade da seguinte conjectura:


\medskip{}
$f(n)=O(g(n))$ implica que $g(n)=O(f(n)).$

\medskip{}
\item Assuma que $f(n)$ e $g(n)$ s\~{a}o duas fun\c{c}\~{o}es assint\'{o}ticamente
positivas. Prove a verdade ou falsidade da seguinte conjectura:


\medskip{}
$f(n)+g(n)=\Theta(\min(f(n),g(n))).$

\medskip{}
\item Assuma que $f(n)$ e $g(n)$ s\~{a}o duas fun\c{c}\~{o}es assint\'{o}ticamente
positivas. Prove a verdade ou falsidade da seguinte conjectura:


\medskip{}
$f(n)=O(g(n))$ implica que $\lg(f(n))=O(\lg(g(n)))$, onde $\lg(g(n))>0$
e $f(n)\geq1$ para todo $n$ suficientemente grande.

\medskip{}
\item Assuma que $f(n)$ e $g(n)$ s\~{a}o duas fun\c{c}\~{o}es assint\'{o}ticamente
positivas. Prove a verdade ou falsidade da seguinte conjectura:


\medskip{}
$f(n)=O(g(n))$ implica que $2^{f(n)}=O(2^{g(n)}).$

\medskip{}
\item Assuma que $f(n)$ é uma função assint\'{o}ticamente positiva. Prove
a verdade ou falsidade da seguinte conjectura:


\medskip{}
$f(n)=O((f(n))^{2}).$

\medskip{}
\item Assuma que $f(n)$ e $g(n)$ s\~{a}o duas fun\c{c}\~{o}es assint\'{o}ticamente
positivas. Prove a verdade ou falsidade da seguinte conjectura:


\medskip{}
$f(n)=O(g(n))$ implica que $g(n)=\Omega(f(n)).$

\medskip{}
\item Assuma que $f(n)$ e $g(n)$ s\~{a}o duas fun\c{c}\~{o}es assint\'{o}ticamente
positivas. Prove a verdade ou falsidade da seguinte conjectura:


\medskip{}
$f(n)=\Theta(f(\frac{n}{2})).$

\medskip{}
\item Assuma que $f(n)$ e $g(n)$ s\~{a}o duas fun\c{c}\~{o}es assint\'{o}ticamente
positivas. Prove a verdade ou falsidade da seguinte conjectura:


\medskip{}
$f(n)=\Omega(g(n))$ implica que $g(n)^{2}=\Omega(f(n)^{2}).$

\medskip{}
\item Assuma que $f(n)$ e $g(n)$ s\~{a}o duas fun\c{c}\~{o}es assint\'{o}ticamente
positivas. Prove a verdade ou falsidade da seguinte conjectura:


\medskip{}
$f(n)+o(f(n))=\Theta(f(n)).$

\medskip{}
\item Mostre que para qualquer constante real $a$ e $b$, onde $b>0$,\[
(n+a)^{b}=\theta(n^{b})\]

\medskip{}
\item Qual das seguintes funções cresce mais rápido (justifique a sua resposta):

\begin{enumerate}
\medskip{}
\item $n^{ln\, n}$ou $(ln\, n)^{n}$
\medskip{}
\item $n^{ln\, ln\, ln\, n}$ ou $(ln\, n)!$
\end{enumerate}
\medskip{}
\item Classifique as funções abaixo como sendo \emph{uma} das seguintes:
$f(n)=\Theta(g(n))$, $f(n)=O(g(n))$, ou $f(n)=\Omega(g(n))$. Explique
cada uma das suas escolhas.

\begin{description}
\medskip{}
\item [\begin{tabular}{|c|c|c|}
\hline 
$f(n)$&
$g(n)$&
Relação\tabularnewline
\hline
\hline 
$an^{2}+bn+k$&
$n^{2}$&
\tabularnewline
\hline 
$n^{k}$&
$c^{n}$&
\tabularnewline
\hline 
$n^{lgn}$&
$n(lgn)^{2}$&
\tabularnewline
\hline 
$n^{100}$&
$2^{lgn}$&
\tabularnewline
\hline
\end{tabular}]~
\end{description}

\end{enumerate}

\end{document}
