Resumo de aula
Notação O(f(x)) -> f(x) é um upper bound
Um pouco de notação omega e theta pra vocês não se confundirem em análise de algoritmo
Análise de complexidade de preencher uma matriz
Complexidade da multiplicação de matrizes (não é Strassen, é a normal)
Complexidade da busca binária (binary search)
Complexidade do algoritmo de verificar se um número é primo (primality test)
Complexidade do crivo (Sieve of Eratosthenes)
Complexidade do TSP burro (Traveling Salesman Problem)
Classificações de problemas:
NP, P, NP-complete, NP-hard
Merge sort
Bogosort
Bubblesort
Quicksort
Os vídeos para essa semana:
Do curso Algorithms: Design and Analysis, Part I (https://class.coursera.org/algo-2012-002/lecture/index)
Entrem na parte de Video Lectures e vejam TODOS os vídeos do Introduction e os dois primeiros do Asymptotic Analysis (Big-Oh Notation e Basic Examples) – Os outros dois dessa parte são opcionais para a maratona mas serão úteis para Análise de Algoritmos e pros curiosos, claro!
Qualquer dúvida sobre os vídeos escrevam para a lista! Sério! Compartilhem suas dúvidas!
Acabados os vídeos, vocês podem tentar fazer o Problem Set-1, mas lembrem-se que ele vai incluir todo conteúdo da Week 1 (se vocês tiverem vontade, encorajo muito, os Problem Sets são super bem feitos)
Os problemas para essa semana:
100 - The 3n + 1 Problem
102 - Ecological Bin Packing
484 - The Department of Redundancy Department
494 - Kindergarten Counting Game
10055 - Hashmat the brave warrior
10370 - Above Average
100 - The 3n + 1 Problem
Soluções AC:
- http://pastebin.com/fQnSKsbC (Luiza - novo)
- http://pastebin.com/rfCnxYfp (Luiza - antigo)
Códigos errados (e o resultado do judge):
(nenhum, por enquanto)
102 - Ecological Bin Packing
Soluções AC:
- http://pastebin.com/twE4mcT4 (Luiza - novo)
- http://pastebin.com/Srh9Nhpm (Luiza - antigo e mais esperto!)
Códigos errados (e o resultado do judge):
- http://pastebin.com/6VDpUcQP (Luiza - CE)
484 - The Department of Redundancy Department
Soluções AC:
Códigos errados (e o resultado do judge):
(nenhum, por enquanto)
494 - Kindergarten Counting Game
Soluções AC:
Códigos errados (e o resultado do judge):
10055 - Hashmat the brave warrior
Soluções AC:
Códigos errados (e o resultado do judge):
10370 - Above Average
Soluções AC:
Códigos errados (e o resultado do judge):
(nenhum, por enquanto)
