Velocidade e Qualidade com Estruturas de Dados e Algoritmos
Recursão, programação dinâmica, QuickSort e QuickSelect com evidência técnica e análise de custo
Este material organiza o TP3 em blocos objetivos: contrato, raciocínio, implementação, validação e custo. A meta é construir respostas defensáveis, não apenas produzir uma saída.
Use cada seção para treinar explicação técnica: o que o algoritmo faz, por que termina, quanto custa e qual evidência comprova a solução.
Objetivo da página
TP3 — Respostas Comentadas e Ensino do Caminho
Velocidade e Qualidade com Estruturas de Dados e Algoritmos
Foco do materialConstruir a resposta, não só mostrar a saída.
Estrutura de cada exercícioObjetivo → ideia → tracing → código → validação → custo → erro comum.
Este arquivo foi escrito como material didático de apoio. O foco é ensinar o raciocínio, os casos base, a validação e os critérios de custo que permitem responder ao TP3 com autonomia.
Este TP3 é o ponto em que a disciplina deixa de pedir apenas “código que funciona” e passa a exigir raciocínio algorítmico com estrutura, justificativa e controle. As questões foram desenhadas para forçar o aluno a sair do modo operacional e entrar no modo analítico: não basta implementar; é preciso definir caso base, reduzir corretamente o problema, instrumentar chamadas, medir custo, identificar redundância e comparar abordagens. Em outras palavras, este conjunto de exercícios trata recursão, programação dinâmica e algoritmos de ordenação e seleção não como fórmulas prontas, mas como ferramentas que precisam ser compreendidas por dentro.
Ao enfrentar essas tarefas, o leitor encontrará desafios de natureza diferente. Alguns são desafios de modelagem: transformar multiplicação em soma recursiva, fatoração em decomposição progressiva, diretórios em árvore, combinações em decisões sucessivas de inclusão e exclusão. Outros são desafios de rigor: definir corretamente o caso base, impedir recursão infinita, tratar entradas especiais, controlar profundidade e distinguir o que acontece na chamada e o que acontece no retorno. Há ainda os desafios de custo: perceber quando uma solução recursiva pura explode em chamadas redundantes, reconhecer quando memoização muda o jogo, e entender por que QuickSort e QuickSelect, embora aparentados, servem a objetivos diferentes.
Se o leitor conseguir resolver todas as questões com clareza e correção, ele demonstrará uma competência central em ciência da computação: a capacidade de decompor problemas complexos em subproblemas menores sem perder o controle do processo. Isso significa dominar recursão de verdade, não como truque sintático, mas como modelo mental. Significa saber identificar e justificar casos base, prever a árvore de chamadas, explicar a redução do problema e validar se a recursão termina quando deve terminar.
Também passará a dominar uma habilidade decisiva para problemas maiores: enxergar redundância algorítmica. Esse é o coração da transição entre recursão pura e programação dinâmica. Quem fecha bem este TP3 aprende a reconhecer quando o algoritmo está recalculando estados equivalentes, aprende a nomear esses estados, armazená-los e reaproveitá-los. Em termos práticos, isso forma uma competência rara entre iniciantes: não apenas escrever uma solução correta, mas enxergar por que ela não escala — e como fazê-la escalar melhor.
Outro ganho importante é o domínio de algoritmos de divisão e conquista orientados por objetivo. QuickSort e QuickSelect aparecem aqui não como dois nomes de livro, mas como dois desenhos algorítmicos que parecem semelhantes e, no entanto, servem a propósitos diferentes. Quem resolve essas questões compreende que ordenar tudo para depois selecionar um elemento pode ser desperdício, e que escolher o algoritmo certo depende do que o problema pede, não do que parece mais familiar. Isso é maturidade técnica.
Há ainda uma competência de engenharia que este TP3 cobra o tempo todo: instrumentar e produzir evidência. Contar chamadas, comparações, cópias, observar comportamento com entradas ordenadas, invertidas e aleatórias, registrar conclusões em Markdown, mostrar execução com indentação — tudo isso treina o leitor a não confiar apenas na intuição. Ele aprende a sustentar uma análise com rastros observáveis. Sai do “acho que é melhor” para o “os dados mostram isso”.
Se chegar ao fim resolvendo tudo com método, o leitor terá desenvolvido, no mínimo, estas qualidades: pensamento recursivo disciplinado; precisão na definição de casos base e contratos; capacidade de modelar estruturas hierárquicas; leitura de árvore de decisões; noção concreta de explosão combinatória; uso consciente de memoização; compreensão prática de QuickSort e QuickSelect; análise de complexidade com mais substância; e, sobretudo, a habilidade de alinhar algoritmo, custo e objetivo sem recorrer a respostas decoradas.
Em linguagem simples: quem consegue fazer bem este TP3 já não está apenas “aprendendo Python”. Está aprendendo a raciocinar como alguém que projeta soluções, mede consequências, escolhe estratégias e consegue explicar por que uma abordagem funciona melhor do que outra. E é exatamente esse tipo de competência que sustenta o restante da disciplina e boa parte do que vem depois em estruturas de dados, algoritmos e desenvolvimento profissional.
O TP3 fecha o ciclo da disciplina com recursão, programação dinâmica, QuickSort e QuickSelect. O enunciado pede implementação, casos base, tratamento de bordas, instrumentação, comparação de custo e evidências de execução. Não basta “funcionar”; é preciso mostrar como funciona, onde custa e por que a escolha algorítmica faz sentido.
Abaixo está a **versão completa, reescrita e pronta para colar** no material do TP3. Ela foi montada para fechar exatamente as lacunas didáticas que faltavam: contrato do exercício, modelo mental, tracing, código, validação, erros comuns e fechamento. O TP3 cobra explicitamente recursão com caso base, tratamento de bordas, evidências de execução, identificação de redundância, memoização, QuickSort com pivô no último elemento, QuickSelect e comparação entre ambos.
---
# TESTE DE PERFORMANCE 3 — RESPOSTAS COM EXPLICAÇÃO DIDÁTICA
Este conjunto de exercícios foi construído para consolidar competências centrais em recursão, programação dinâmica, ordenação e seleção. O objetivo não é apenas chegar a uma saída correta, mas aprender a decompor um problema, controlar o fluxo de chamadas, definir casos base com rigor, medir custo e justificar por que um algoritmo é mais adequado do que outro em determinado cenário. O próprio enunciado destaca recursão, memoização, QuickSort, QuickSelect, instrumentação e comparação de eficiência como núcleo do TP3.
A lógica deste material é simples: cada exercício começa com o que ele quer de fato, mostra como pensar, apresenta uma implementação correta, valida com testes e fecha com os erros mais comuns. A ideia é que a pessoa consiga não só “ver a resposta”, mas entender como construí-la.
Base curricular coberta: recursão, programação dinâmica, divisão e conquista, instrumentação e análise comparativa de algoritmos.
Apresentação
Este material foi organizado para que o aluno consiga sair do modo “copiar a solução” e entrar no modo “construir, testar, justificar e defender a solução”. Cada exercício foi reescrito com contrato, modelo mental, tracing, código, validação, análise de custo e erros comuns.
A disciplina chega aqui ao seu ponto mais denso: recursão, memoização, QuickSort, QuickSelect e análise comparativa. Por isso, o critério não é só correção; é correção com explicação e evidência.
Bloco
O que o aluno precisa dominar
Evidência mínima
Armadilha típica
Recursão
caso base, redução e retorno
tracing pequeno + teste
redução errada / recursão infinita
DP
estado, repetição, memoização
comparar nº de chamadas
cache em estado errado
QuickSort
partição e impacto do pivô
ordenado, invertido, aleatório
achar que pivô é detalhe
QuickSelect
seleção sem ordenar tudo
mediana correta + menos trabalho
ordenar tudo por hábito
Roteiro dos exercícios
| Bloco | Tema | Foco técnico |
|---|---|---|
| EX.01 | Multiplicação recursiva por soma | implementar mult(x, y) usando apenas somas, explicitar o caso base e deixar visível a diferença entre a fase de chamada e a fase de retorno |
| EX.02 | Fatoração recursiva de inteiros | construir factor(x, lowest=2), limitar divisores até a raiz quadrada, tratar primos e casos especiais (0, 1 e negativos). |
| EX.03 | Potenciação recursiva com expoentes negativos | implementar power(x, y), definir casos base para y=0 e y=1, tratar expoentes negativos e analisar a complexidade da solução. |
| EX.04 | Navegação recursiva em estrutura de diretórios | percorrer um diretório e seus subdiretórios de forma recursiva, listar arquivos por nível, controlar a profundidade por indentação e apresen |
| EX.05 | Geração recursiva de combinações (times) | implementar teams(candidates, k), gerar todas as combinações de tamanho k, representar cada solução como string e impedir repetições. |
| EX.06 | Problema da mochila (knapsack recursivo) | implementar knapsack(target, weights, index), gerar combinações de pesos que somem exatamente ao alvo, definir os casos base e testar com di |
| EX.07 | Análise de complexidade em algoritmos recursivos | escolher uma função recursiva anterior, identificar chamadas redundantes, analisar o crescimento e registrar a conclusão em Markdown com Big |
| EX.08 | Otimização com programação dinâmica | escolher um algoritmo recursivo com estados repetidos, aplicar memoização, comparar o número de chamadas e apresentar evidência da melhoria. |
| EX.09 | Implementação do QuickSort | implementar QuickSort recursivo usando o último elemento como pivô, separar partições corretamente e testar em arrays ordenados, invertidos |
| EX.10 | Instrumentação do QuickSort | contar comparações e cópias do QuickSort, considerando uma troca como três cópias, e comparar diferentes tipos de entrada. |
| EX.11 | Implementação do QuickSelect | implementar QuickSelect recursivo, selecionar qualquer índice k usando a mesma lógica de partição do QuickSort e parar a recursão quando o í |
| EX.12 | Comparação entre QuickSort e QuickSelect | executar QuickSort e QuickSelect sobre os mesmos dados, comparar comparações e cópias, analisar os resultados e identificar cenários mais ad |
O que a questão pede
implementar mult(x, y) usando apenas somas, explicitar o caso base e deixar visível a diferença entre a fase de chamada e a fase de retorno da recursão.
Conceito cobrado
Aplicação disciplinada de recursão/seleção/otimização com justificativa de corretude e custo.
Estrutura dos dados
Listas, inteiros, dicionários de apoio e estados recursivos explícitos para controlar decisão e retorno.
Como pensar
Multiplicar x por y, para y positivo, é somar x exatamente y vezes. A recursão serve para quebrar esse total em um passo simples agora e o restante depois.
O menor problema possível é quando y vale 0. Nesse ponto, o resultado é 0 e a recursão para.
Se a função for escrita como x + mult(x, y - 1), a soma efetiva aparece na volta da pilha de chamadas. Na descida, o algoritmo só empilha trabalho.
Como validar
assert mult(5, 0) == 0assert mult(7, 1) == 7assert mult(3, 4) == 12assert mult(1, 9) == 9
Tabela de Evidência
| Eixo | Critério | Evidência |
|---|---|---|
| Contrato | Caso base e redução definidos | Função retorna valor esperado nos casos mínimos |
| Rastreio | Chamadas/retornos observáveis | Tracing pequeno anexado no código/saída |
| Custo | Complexidade justificada | Discussão de tempo/espaço alinhada ao algoritmo |
Variáveis-chave
Parâmetros de entrada, caso base, índice de redução e condição de parada bem definidos.
O que focar no Screenshot
Mostrar função, testes mínimos e resultado de execução com um caso representativo.
Como explicar
O ponto didático aqui é enxergar a pilha: a descida prepara o trabalho; a volta efetivamente combina os resultados.
Problema & solução
• Esquecer de diminuir y. Sintoma: recursão infinita.
• Usar o operador *. Sintoma: a conta sai certa, mas o objetivo do exercício não é atendido.
• Confundir chamada com retorno. Sintoma: explicação incorreta sobre onde a soma acontece.
def mult(x, y, depth=0):
indent = " " * depth
print(f"{indent}chamada: mult({x}, {y})")
if y == 0:
print(f"{indent}retorno: 0 (caso base)")
return 0
parcial = mult(x, y - 1, depth + 1)
resultado = x + parcial
print(f"{indent}retorno: {x} + {parcial} = {resultado}")
return resultado
assert mult(3, 4) == 12O que a questão pede
construir factor(x, lowest=2), limitar divisores até a raiz quadrada, tratar primos e casos especiais (0, 1 e negativos).
Conceito cobrado
Aplicação disciplinada de recursão/seleção/otimização com justificativa de corretude e custo.
Estrutura dos dados
Listas, inteiros, dicionários de apoio e estados recursivos explícitos para controlar decisão e retorno.
Como pensar
A ideia é progressiva: encontrar um divisor, separar esse divisor e repetir o problema no quociente.
Não é preciso testar divisores até x - 1. Se houver divisor não trivial, algum deles aparece até sqrt(x).
Se nenhum divisor aparece nesse intervalo, então o número é primo.
Como validar
assert factor(60) == [2, 2, 3, 5]assert factor(13) == [13]assert factor(1) == [1]assert factor(0) == [0]assert factor(-18) == [-1, 2, 3, 3]
Tabela de Evidência
| Eixo | Critério | Evidência |
|---|---|---|
| Contrato | Caso base e redução definidos | Função retorna valor esperado nos casos mínimos |
| Rastreio | Chamadas/retornos observáveis | Tracing pequeno anexado no código/saída |
| Custo | Complexidade justificada | Discussão de tempo/espaço alinhada ao algoritmo |
Variáveis-chave
Parâmetros de entrada, caso base, índice de redução e condição de parada bem definidos.
O que focar no Screenshot
Mostrar função, testes mínimos e resultado de execução com um caso representativo.
Como explicar
A boa resposta aqui não é apenas “achar fatores”; é controlar a busca com critério e justificar por que a raiz quadrada basta.
Problema & solução
• Testar divisores até x - 1. Funciona, mas perde a otimização pedida.
• Não tratar x < 0. Sintoma: saída inconsistente ou erro lógico.
• Retornar lista vazia para primo. Sintoma: perde a informação de que o próprio número é o fator.
import math
def factor(x, lowest=2):
if x in (0, 1):
return [x]
if x < 0:
return [-1] + factor(-x, lowest)
for d in range(lowest, int(math.isqrt(x)) + 1):
if x % d == 0:
return [d] + factor(x // d, d)
return [x]O que a questão pede
implementar power(x, y), definir casos base para y=0 e y=1, tratar expoentes negativos e analisar a complexidade da solução.
Conceito cobrado
Aplicação disciplinada de recursão/seleção/otimização com justificativa de corretude e custo.
Estrutura dos dados
Listas, inteiros, dicionários de apoio e estados recursivos explícitos para controlar decisão e retorno.
Como pensar
A leitura correta começa pela matemática: x^0 = 1, x^1 = x e x^(-y) = 1 / x^y, desde que x seja diferente de 0.
Se o expoente é par, vale a pena usar exponenciação por quadrados: x^y = (x^(y/2))². É isso que derruba o custo de linear para logarítmico.
O caso 0^0 merece tratamento explícito, porque costuma ser indefinido em muitos contextos.
Como validar
assert power(2, 5) == 32assert power(2, -3) == 0.125assert power(5, 1) == 5assert power(3, 0) == 1assert power(0, 4) == 0
Tabela de Evidência
| Eixo | Critério | Evidência |
|---|---|---|
| Contrato | Caso base e redução definidos | Função retorna valor esperado nos casos mínimos |
| Rastreio | Chamadas/retornos observáveis | Tracing pequeno anexado no código/saída |
| Custo | Complexidade justificada | Discussão de tempo/espaço alinhada ao algoritmo |
Variáveis-chave
Parâmetros de entrada, caso base, índice de redução e condição de parada bem definidos.
O que focar no Screenshot
Mostrar função, testes mínimos e resultado de execução com um caso representativo.
Como explicar
Aqui, o ganho não vem de truque de linguagem. Vem de usar uma identidade matemática correta para reorganizar o problema.
Problema & solução
• Resolver tudo por y - 1. Funciona, mas desperdiça desempenho.
• Não tratar 0 com expoente negativo. Sintoma: divisão por zero.
• Esquecer o caso base y == 1. Sintoma: trabalho extra e raciocínio menos claro.
def power(x, y):
if y == 0:
return 1
if y < 0:
return 1 / power(x, -y)
if y % 2 == 0:
h = power(x, y // 2)
return h * h
return x * power(x, y - 1)O que a questão pede
percorrer um diretório e seus subdiretórios de forma recursiva, listar arquivos por nível, controlar a profundidade por indentação e apresentar evidência de execução sem usar uma travessia automática pronta.
Conceito cobrado
Aplicação disciplinada de recursão/seleção/otimização com justificativa de corretude e custo.
Estrutura dos dados
Listas, inteiros, dicionários de apoio e estados recursivos explícitos para controlar decisão e retorno.
Como pensar
Diretório é árvore. Esse é o modelo mental que resolve o exercício. Cada pasta é um nó; cada subpasta é um filho.
Se a estrutura é hierárquica, a recursão encaixa naturalmente: processa o nível atual e chama a si mesma para os subníveis.
Para ensinar de verdade, não basta mostrar a função. É preciso montar um ambiente pequeno e reproduzível, para que a execução seja observável.
Como validar
walk_recursive("teste_dirs")# saída esperada aproximada:# [DIR] teste_dirs# - readme.txt# [DIR] docs# - manual.pdf# [DIR] src# - main.py# [DIR] utils# - helpers.py
Tabela de Evidência
| Eixo | Critério | Evidência |
|---|---|---|
| Contrato | Caso base e redução definidos | Função retorna valor esperado nos casos mínimos |
| Rastreio | Chamadas/retornos observáveis | Tracing pequeno anexado no código/saída |
| Custo | Complexidade justificada | Discussão de tempo/espaço alinhada ao algoritmo |
Variáveis-chave
Parâmetros de entrada, caso base, índice de redução e condição de parada bem definidos.
O que focar no Screenshot
Mostrar função, testes mínimos e resultado de execução com um caso representativo.
Como explicar
O exercício quer que o aluno enxergue recursão em uma estrutura real. Sem essa ponte mental, a função vira só um script qualquer.
Problema & solução
• Usar os.walk. Resolve o problema prático, mas mata o ponto pedagógico do exercício.
• Não aumentar a indentação com a profundidade. Sintoma: a hierarquia some da saída.
• Listar só arquivos e esquecer de descer nos diretórios.
from pathlib import Path
def walk(path, depth=0):
p = Path(path)
for item in sorted(p.iterdir()):
print(' ' * depth + item.name)
if item.is_dir():
walk(item, depth + 1)O que a questão pede
implementar teams(candidates, k), gerar todas as combinações de tamanho k, representar cada solução como string e impedir repetições.
Conceito cobrado
Aplicação disciplinada de recursão/seleção/otimização com justificativa de corretude e custo.
Estrutura dos dados
Listas, inteiros, dicionários de apoio e estados recursivos explícitos para controlar decisão e retorno.
Como pensar
Combinação não depende de ordem interna. Se “Ana, Bia” já apareceu, “Bia, Ana” não é nova solução.
O estado recursivo precisa carregar duas coisas: a posição de onde ainda se pode escolher e a combinação parcial construída até aqui.
A regra que evita repetição é simples: depois de escolher o elemento na posição i, a próxima chamada só olha para i + 1 em diante.
Como validar
assert teams(["A", "B", "C"], 2) == ["A, B", "A, C", "B, C"]assert teams([], 1) == []assert teams(["A"], 2) == []
Tabela de Evidência
| Eixo | Critério | Evidência |
|---|---|---|
| Contrato | Caso base e redução definidos | Função retorna valor esperado nos casos mínimos |
| Rastreio | Chamadas/retornos observáveis | Tracing pequeno anexado no código/saída |
| Custo | Complexidade justificada | Discussão de tempo/espaço alinhada ao algoritmo |
Variáveis-chave
Parâmetros de entrada, caso base, índice de redução e condição de parada bem definidos.
O que focar no Screenshot
Mostrar função, testes mínimos e resultado de execução com um caso representativo.
Como explicar
O que o exercício treina é controle de estado recursivo. O código certo nasce dessa disciplina, não de improviso.
Problema & solução
• Permitir retorno a índices anteriores. Sintoma: combinações repetidas em ordens diferentes.
• Não declarar o contrato para k = 0. Sintoma: dúvida sobre o que fazer com a combinação vazia.
• Construir permutações quando o exercício pede combinações.
def teams(candidates, k, i=0, current=None, out=None):
current = current or []
out = out or []
if len(current) == k:
out.append(tuple(current))
return out
if i == len(candidates):
return out
teams(candidates, k, i + 1, current + [candidates[i]], out)
teams(candidates, k, i + 1, current, out)
return outO que a questão pede
implementar knapsack(target, weights, index), gerar combinações de pesos que somem exatamente ao alvo, definir os casos base e testar com diferentes conjuntos.
Conceito cobrado
Aplicação disciplinada de recursão/seleção/otimização com justificativa de corretude e custo.
Estrutura dos dados
Listas, inteiros, dicionários de apoio e estados recursivos explícitos para controlar decisão e retorno.
Como pensar
A mochila recursiva é o modelo clássico de “usa ou não usa” o item atual. Cada passo gera duas possibilidades.
Por isso, a árvore de chamadas cresce rápido: o exercício existe justamente para que esse crescimento fique visível.
O estado relevante é composto pelo índice atual e pelo alvo restante.
Como validar
assert sorted(knapsack(5, [1, 2, 3, 4])) == sorted([[2, 3], [1, 4]])assert knapsack(1, [2, 3]) == []assert knapsack(0, [1, 2, 3]) == [[]]
Tabela de Evidência
| Eixo | Critério | Evidência |
|---|---|---|
| Contrato | Caso base e redução definidos | Função retorna valor esperado nos casos mínimos |
| Rastreio | Chamadas/retornos observáveis | Tracing pequeno anexado no código/saída |
| Custo | Complexidade justificada | Discussão de tempo/espaço alinhada ao algoritmo |
Variáveis-chave
Parâmetros de entrada, caso base, índice de redução e condição de parada bem definidos.
O que focar no Screenshot
Mostrar função, testes mínimos e resultado de execução com um caso representativo.
Como explicar
A mochila recursiva pura é correta, mas não escala bem. O valor didático dela está justamente em mostrar esse limite.
Problema & solução
• Não matar o ramo quando target < 0. Sintoma: chamadas inúteis explodem.
• Esquecer que target == 0 deve registrar combinação válida.
• Permitir reutilização do mesmo índice, gerando respostas fora do contrato.
def knapsack(target, weights, i=0, chosen=None, out=None):
chosen = chosen or []
out = out or []
if target == 0:
out.append(chosen[:])
return out
if target < 0 or i == len(weights):
return out
knapsack(target - weights[i], weights, i + 1, chosen + [weights[i]], out)
knapsack(target, weights, i + 1, chosen, out)
return outO que a questão pede
escolher uma função recursiva anterior, identificar chamadas redundantes, analisar o crescimento e registrar a conclusão em Markdown com Big O.
Conceito cobrado
Aplicação disciplinada de recursão/seleção/otimização com justificativa de corretude e custo.
Estrutura dos dados
Listas, inteiros, dicionários de apoio e estados recursivos explícitos para controlar decisão e retorno.
Como pensar
A melhor escolha didática aqui é a mochila recursiva, porque ela tem redundância real e fácil de explicar.
Não basta dizer “é exponencial”. O aluno precisa mostrar de onde vem a bifurcação e por que o número de chamadas cresce tão rápido.
Como validar
# Regra prática de verificação# Se a explicação não mostrar:# - onde a redundância aparece# - por que há bifurcação# - e por que isso leva a crescimento exponencial# então a análise ainda está superficial.
Tabela de Evidência
| Eixo | Critério | Evidência |
|---|---|---|
| Contrato | Caso base e redução definidos | Função retorna valor esperado nos casos mínimos |
| Rastreio | Chamadas/retornos observáveis | Tracing pequeno anexado no código/saída |
| Custo | Complexidade justificada | Discussão de tempo/espaço alinhada ao algoritmo |
Variáveis-chave
Parâmetros de entrada, caso base, índice de redução e condição de parada bem definidos.
O que focar no Screenshot
Mostrar função, testes mínimos e resultado de execução com um caso representativo.
Como explicar
Análise profissional não é grudar um O(...) no final. É mostrar por que aquele crescimento acontece.
Problema & solução
• Escrever só “é O(2^n)” sem explicar a bifurcação.
• Falar em redundância, mas não apontar qual estado se repete.
• Confundir tamanho do alvo com quantidade de itens.
calls = 0
def fib_naive(n):
global calls
calls += 1
if n < 2:
return n
return fib_naive(n - 1) + fib_naive(n - 2)
fib_naive(30)
print('chamadas:', calls)O que a questão pede
escolher um algoritmo recursivo com estados repetidos, aplicar memoização, comparar o número de chamadas e apresentar evidência da melhoria.
Conceito cobrado
Aplicação disciplinada de recursão/seleção/otimização com justificativa de corretude e custo.
Estrutura dos dados
Listas, inteiros, dicionários de apoio e estados recursivos explícitos para controlar decisão e retorno.
Como pensar
A mochila é novamente a melhor escolha didática, porque o estado se descreve bem por (index, target).
Memoização não guarda “o caminho todo”; guarda o resultado do estado certo. Se o estado já foi resolvido, recalcular é desperdício.
Como validar
weights = [1, 2, 3, 4, 5, 6]target = 10c1 = {"calls": 0}r1 = knapsack_plain_count(target, weights, 0, c1)c2 = {"calls": 0}r2 = knapsack_memo(target, weights, 0, {}, c2)print("plain:", c1["calls"], r1)print("memo :", c2["calls"], r2)
Tabela de Evidência
| Eixo | Critério | Evidência |
|---|---|---|
| Contrato | Caso base e redução definidos | Função retorna valor esperado nos casos mínimos |
| Rastreio | Chamadas/retornos observáveis | Tracing pequeno anexado no código/saída |
| Custo | Complexidade justificada | Discussão de tempo/espaço alinhada ao algoritmo |
Variáveis-chave
Parâmetros de entrada, caso base, índice de redução e condição de parada bem definidos.
O que focar no Screenshot
Mostrar função, testes mínimos e resultado de execução com um caso representativo.
Como explicar
Programação dinâmica nasce quando a recursão pura começa a recalcular a mesma coisa. Esse exercício existe para tornar isso mensurável.
Problema & solução
• Guardar o cache por valor do caminho, e não por estado. Sintoma: pouca ou nenhuma melhora.
• Esquecer de medir chamadas nas duas versões. Sintoma: a melhoria fica só no discurso.
• Não explicar por que (index, target) é suficiente como estado.
def knapsack_memo(target, weights, index=0, memo=None, counter=None):
if memo is None:
memo = {}
if counter is None:
counter = {"calls": 0}
counter["calls"] += 1
state = (index, target)
if state in memo:
return memo[state]
if target == 0:
return [[]]
if target < 0 or index == len(weights):
return []
without_current = knapsack_memo(target, weights, index + 1, memo, counter)
with_current = knapsack_memo(target - weights[index], weights, index + 1, memo, counter)
with_current = [[weights[index]] + combo for combo in with_current]
memo[state] = with_current + without_current
return memo[state]
def knapsack_plain_count(target, weights, index=0, counter=None):
if counter is None:
counter = {"calls": 0}
counter["calls"] += 1
if target == 0:
return [[]]
if target < 0 or index == len(weights):
return []
without_current = knapsack_plain_count(target, weights, index + 1, counter)
with_current = knapsack_plain_count(target - weights[index], weights, index + 1, counter)
with_current = [[weights[index]] + combo for combo in with_current]
return with_current + without_currentO que a questão pede
implementar QuickSort recursivo usando o último elemento como pivô, separar partições corretamente e testar em arrays ordenados, invertidos e aleatórios.
Conceito cobrado
Aplicação disciplinada de recursão/seleção/otimização com justificativa de corretude e custo.
Estrutura dos dados
Listas, inteiros, dicionários de apoio e estados recursivos explícitos para controlar decisão e retorno.
Como pensar
O QuickSort divide e conquista: escolhe um pivô, separa quem fica à esquerda e à direita e resolve recursivamente os dois lados.
O ponto crítico aqui é a partição. Sem entender a posição final do pivô, o resto vira “mágica”.
Como o enunciado fixa o último elemento como pivô, isso precisa aparecer explicitamente na explicação e nos testes.
Como validar
assert quicksort([3, 1, 4, 1, 5, 9, 2]) == sorted([3, 1, 4, 1, 5, 9, 2])assert quicksort([1, 2, 3, 4, 5]) == [1, 2, 3, 4, 5]assert quicksort([5, 4, 3, 2, 1]) == [1, 2, 3, 4, 5]assert quicksort([]) == []
Tabela de Evidência
| Eixo | Critério | Evidência |
|---|---|---|
| Contrato | Caso base e redução definidos | Função retorna valor esperado nos casos mínimos |
| Rastreio | Chamadas/retornos observáveis | Tracing pequeno anexado no código/saída |
| Custo | Complexidade justificada | Discussão de tempo/espaço alinhada ao algoritmo |
Variáveis-chave
Parâmetros de entrada, caso base, índice de redução e condição de parada bem definidos.
O que focar no Screenshot
Mostrar função, testes mínimos e resultado de execução com um caso representativo.
Como explicar
O exercício quer duas coisas ao mesmo tempo: implementação correta e leitura do impacto do pivô.
Problema & solução
• Tratar o pivô como detalhe. Sintoma: análise de comportamento incompleta.
• Separar mal os repetidos. Sintoma: ordenação incorreta em alguns casos.
• Testar só com array aleatório. Sintoma: perde justamente os cenários críticos pedidos.
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[-1]
left = [x for x in arr[:-1] if x <= pivot]
right = [x for x in arr[:-1] if x > pivot]
return quicksort(left) + [pivot] + quicksort(right)O que a questão pede
contar comparações e cópias do QuickSort, considerando uma troca como três cópias, e comparar diferentes tipos de entrada.
Conceito cobrado
Aplicação disciplinada de recursão/seleção/otimização com justificativa de corretude e custo.
Estrutura dos dados
Listas, inteiros, dicionários de apoio e estados recursivos explícitos para controlar decisão e retorno.
Como pensar
Aqui o foco deixa de ser só “o algoritmo ordena?” e passa a ser “quanto trabalho ele faz em cada cenário?”.
Comparação, neste material, significa cada teste do tipo a[j] <= pivot. Troca significa três cópias.
Como validar
for arr in ( [1, 2, 3, 4, 5], # ordenada [5, 4, 3, 2, 1], # invertida [3, 1, 4, 1, 5, 9, 2] # aleatória): ordered, stats = quicksort_instrumented(arr) print(arr, "->", ordered, stats)
Tabela de Evidência
| Eixo | Critério | Evidência |
|---|---|---|
| Contrato | Caso base e redução definidos | Função retorna valor esperado nos casos mínimos |
| Rastreio | Chamadas/retornos observáveis | Tracing pequeno anexado no código/saída |
| Custo | Complexidade justificada | Discussão de tempo/espaço alinhada ao algoritmo |
Variáveis-chave
Parâmetros de entrada, caso base, índice de redução e condição de parada bem definidos.
O que focar no Screenshot
Mostrar função, testes mínimos e resultado de execução com um caso representativo.
Como explicar
Instrumentar é transformar intuição em evidência. Sem isso, a análise fica ornamental.
Problema & solução
• Não declarar o que conta como comparação e como cópia.
• Contar troca como 1 em vez de 3. Sintoma: instrumentação desalinhada ao enunciado.
• Executar sem registrar os resultados comparativamente.
def quicksort_count(arr):
stats = {'comparisons': 0, 'copies': 0}
def run(v):
if len(v) <= 1:
return v
pivot = v[-1]
left, right = [], []
for x in v[:-1]:
stats['comparisons'] += 1
if x <= pivot:
left.append(x)
else:
right.append(x)
stats['copies'] += 1
return run(left) + [pivot] + run(right)
return run(arr), statsO que a questão pede
implementar QuickSelect recursivo, selecionar qualquer índice k usando a mesma lógica de partição do QuickSort e parar a recursão quando o índice-alvo for encontrado.
Conceito cobrado
Aplicação disciplinada de recursão/seleção/otimização com justificativa de corretude e custo.
Estrutura dos dados
Listas, inteiros, dicionários de apoio e estados recursivos explícitos para controlar decisão e retorno.
Como pensar
QuickSelect não quer o array inteiro ordenado. Quer um único elemento na posição k da ordem.
A lógica da partição é a mesma do QuickSort, mas a recursão não continua nos dois lados: só continua no lado onde k está.
Como validar
arr = [7, 2, 9, 4, 1, 6, 3]assert quickselect(arr, 0) == sorted(arr)[0]assert quickselect(arr, len(arr)//2) == sorted(arr)[len(arr)//2]assert quickselect(arr, len(arr)-1) == sorted(arr)[-1]
Tabela de Evidência
| Eixo | Critério | Evidência |
|---|---|---|
| Contrato | Caso base e redução definidos | Função retorna valor esperado nos casos mínimos |
| Rastreio | Chamadas/retornos observáveis | Tracing pequeno anexado no código/saída |
| Custo | Complexidade justificada | Discussão de tempo/espaço alinhada ao algoritmo |
Variáveis-chave
Parâmetros de entrada, caso base, índice de redução e condição de parada bem definidos.
O que focar no Screenshot
Mostrar função, testes mínimos e resultado de execução com um caso representativo.
Como explicar
QuickSelect reforça uma ideia profissional importante: algoritmo bom é o que resolve exatamente o problema pedido, sem trabalho em excesso.
Problema & solução
• Ordenar tudo antes ou depois. Sintoma: a seleção funciona, mas o ganho do algoritmo some.
• Não validar k. Sintoma: índice inválido passa silenciosamente ou quebra tarde.
• Esquecer que a recursão deve parar no índice-alvo.
def quickselect(arr, k):
pivot = arr[-1]
lows = [x for x in arr[:-1] if x <= pivot]
highs = [x for x in arr[:-1] if x > pivot]
p = len(lows)
if k < p:
return quickselect(lows, k)
if k > p:
return quickselect(highs, k - p - 1)
return pivotO que a questão pede
executar QuickSort e QuickSelect sobre os mesmos dados, comparar comparações e cópias, analisar os resultados e identificar cenários mais adequados para cada algoritmo.
Conceito cobrado
Aplicação disciplinada de recursão/seleção/otimização com justificativa de corretude e custo.
Estrutura dos dados
Listas, inteiros, dicionários de apoio e estados recursivos explícitos para controlar decisão e retorno.
Como pensar
Este exercício fecha o bloco: a pergunta não é mais “como cada algoritmo funciona isoladamente?”, e sim “qual deles faz sentido para qual objetivo?”.
Se o problema pede a mediana, ordenar tudo pode ser desperdício. Se o problema pede o array ordenado, QuickSelect não resolve.
Como validar
# O aluno deve registrar:# 1) comparações do QuickSort# 2) cópias do QuickSort# 3) comparações do QuickSelect# 4) cópias do QuickSelect# 5) conclusão técnica sobre qual faz mais sentido no cenário testado
Tabela de Evidência
| Eixo | Critério | Evidência |
|---|---|---|
| Contrato | Caso base e redução definidos | Função retorna valor esperado nos casos mínimos |
| Rastreio | Chamadas/retornos observáveis | Tracing pequeno anexado no código/saída |
| Custo | Complexidade justificada | Discussão de tempo/espaço alinhada ao algoritmo |
Variáveis-chave
Parâmetros de entrada, caso base, índice de redução e condição de parada bem definidos.
O que focar no Screenshot
Mostrar função, testes mínimos e resultado de execução com um caso representativo.
Como explicar
A conclusão técnica esperada é simples e importante: QuickSort é apropriado quando o array todo ordenado é a saída; QuickSelect é apropriado quando só interessa a ordem estatística de um elemento.
Apêndice — Como transformar as respostas em evidência de entrega
O TP3 não termina no código. O enunciado também exige evidências de execução e um vídeo explicativo. Por isso, antes de fechar o notebook, o aluno deve produzir um conjunto mínimo de rastros observáveis.
• Para exercícios recursivos: mostrar pelo menos uma execução pequena com tracing ou saída instrumentada.
• Para QuickSort instrumentado e comparação final: registrar comparações e cópias em entradas ordenada, invertida e aleatória.
• Para memoização: registrar o número de chamadas da versão pura e da versão otimizada no mesmo conjunto de dados.
• Para diretórios: mostrar o ambiente de teste criado e a saída com indentação.
• Para o vídeo: explicar o que foi feito, demonstrar execuções e comentar o impacto da estratégia no custo.
Regra prática: sem evidência, a solução fica frágil; com evidência, ela fica defensável.
Problema & solução
• Comparar os algoritmos em arrays diferentes. Sintoma: comparação perde validade.
• Medir só tempo e ignorar comparações/cópias, quando o enunciado pede exatamente isso.
• Não transformar o resultado em critério de decisão.
data = [9, 1, 7, 5, 3, 8, 2, 6, 4]
ordered = quicksort(data)
median = quickselect(data, len(data) // 2)
print('ordenado:', ordered)
print('mediana:', median)