Dúvida sobre análise de algoritimos

Boa noite, não estou conseguindo resolver o exercício abaixo.

Considere o problema de troca para n centavos de Real usando o menor número de moedas possível. Suponha que o valor de cada moeda é um inteiro. 

1. Suponha que as moedas disponíveis tem as denominações 1, 5, 10, 25. Forneça um algoritmo guloso para este caso e prove sua correção. 

1. Suponha que as moedas disponíveis têm denominações que são potências de c: c0 , c1, ..., ck , para inteiros c > 1 e K ≥ 1. Mostre que o algoritmo guloso sempre encontra uma solução ótima neste caso. 

1. Forneça um conjunto de denominação de moedas para o qual o algoritmo guloso não garante que a solução devolvida seja ótima. Inclua a moeda de 1 centavo no seu conjunto para que a troca seja possível para qualquer valor de n. 

1. Forneça um algoritmo com consumo de tempo O(nk) que faça a troca para qualquer conjunto com k denominações diferentes de moedas, assumindo que uma delas é a de 1 centavo. 

Mostre como resolver o problema da mochila fracionaria em tempo O(n), sem supor que os inteiros em v[1..n] e w[1..n] são limitados (i.e o uso de RADIXSORT não é uma solução apropriada). 

Seja S[1..n] uma sequência (de inteiros). Uma sequência T[1..m] é subsequência de S se existem índices i1, i2, ..., im com 1 ≤ i1 < i2 < ... < im ≤ n tais que T[j] = S[ij]. Uma sequência T de S é crescente se T[1] ≤ T[2] ≤ ... ≤ T[m]. Uma subsequência crescente T é máxima (= mais longa) se o valor de m é o maior possível. Denote por (LIS) o problema de determinar uma subsequência crescente máxima para S. 

1. Descreva e prove a subestrutura ótima dos subproblemas de (LIS). 

1. Obtenha uma recorrência para uma solução recursiva simples  de (LIS) e analise o tempo requerido por ela.  

1. Forneça um algoritmo em programação dinâmica que resolve (LIS) em tempo O(n2) . 

Continuando o exercício anterior, forneça um algoritmo em programação dinâmica que resolve (LIS) em tempo O(n log n).