MAC5711 é disciplina de pós-graduação em Ciência da Computação da USP.  Segundo o programa oficial, o objetivo da disciplina MAC5711 é

Introduzir as técnicas básicas de análise de eficiência de algoritmos, com cálculo de tempo de pior caso e tempo médio. Isso é feito simultaneamente com a formação de um grande repertório de algoritmos eficientes, que ilustram as técnicas de análise e servem como ponto de partida para o desenvolvimento de novos algoritmos.

A justificativa oficial da disciplina é a seguinte:  O desenvolvimento de algoritmos é uma atividade fundamental na Computação, e a análise é parte indispensável nesse desenvolvimento. Tipicamente o aluno dessa disciplina já está familiarizado com os outros aspectos do projeto de algoritmos, e essa disciplina complementa a formação nessa atividade.

Ainda segundo o programa oficial, o conteúdo de MAC5711 é o seguinte:

• Noções sobre modelos de computação e eficiência de algoritmos.
• Técnicas de estruturação de algoritmos.
• Algoritmos de classificação e busca.
• Algoritmos de manipulação de conjuntos.
• Grafos e algoritmos de busca.
• Noções de complexidade: as classes P, NP e coNP.

A disciplina tem carga de 4 horas de aulas teóricas por semana durante cerca de 12 semanas e dá direito a 8 créditos.

Pré-requisitos

Os pré-requisitos de MAC5711 são noções básicas de estruturas de dados e teoria dos grafos. Esses pré-requisitos correspondem às disciplinas  MAC5710 (Estruturas de Dados e sua Manipulação)  e  MAC5770 (Introdução à Teoria dos Grafos).  A edição mais recente de MAC5710 esteve a cargo de Cristina Gomes Fernandes, e a edição mais recente de MAC5770 esteve a cargo de Paulo Feofiloff.

Também são desejáveis noções básicas de teoria das probabilidades (correspondentes a uma disciplina de graduação sobre o assunto) e uma certa experiência de programação,  particularmente em linguagem C.

Aulas

• Introdução à AA [CLR 1.1-1.2, CLRS 2.1-2.2]
• Notação O [CLR 2.1, CLRS 3.1]
• AA com notação O
• Recursão
• Recorrências [CLR 4.1-4.2, CLRS 4.1-4.2]
• Análise de algoritmos recursivos [CLR 1.3, CLRS 2.3]
• Heapsort [CLR 7, CLRS 6]
• Filas com prioridades [CLR 7.5, CLRS 6.5]
• Quicksort [CLR 8, CLRS 7]
• Tempo médio do Quicksort
• Análise probabilística [CLR 6, CLRS 5]
• Ordenação em tempo linear [CLR 9, CLRS 8]
• Mediana e i-ésimo menor [CLR 10, CLRS 9]
• Programação dinâmica [CLR 16, CLRS 15]
• Subseqüências máximas [CLR 16, CLRS 15]
• Algoritmos gulosos [CLR 17, CLRS 16]
• Análise amortizada [CLR 18, CLRS 17]
• Conjuntos disjuntos [CLR 22, CLRS 21]
• Busca em grafos [CLR 23, CLRS 22]
• Componentes fortes [CLR 23, CLRS 22]
• Árvores geradores de peso mínimo [CLR 24, CLRS 23]
• Algoritmo de Dijkstra [CLR 25, CLRS 24]   
• Problemas completos em NP [CLR 36, CLRS 34]