Material da aula de análise de algoritmos

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:

Códigos errados (e o resultado do judge):

(nenhum, por enquanto)

102 - Ecological Bin Packing

Soluções AC:

Códigos errados (e o resultado do judge):

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)

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License