* Ver também a página com [[dicas]] gerais.
* D. S. Johnson: {{http://www.research.att.com/~dsj/papers/experguide.pdf|A Theoretician's Guide to the Experimental Analysis of Algorithms}}
==== Trabalho 1 (Heaps binários) ====
Entrega: 13/03/2009
=== Objetivos ===
* Implementar um heap binário
* Implementar o algoritmo de Prim usando esse heap
* Verificar as complexidades experimentalmente
=== Casos de teste ===
* Os casos de teste são parte do [[http://steinlib.zib.de//steinlib.php|Steinlib]].
* Todos possuem somente uma componente conectada.
^ Nome ^ MST ^ Nome ^ MST ^ Nome ^ MST ^
| b01 | 238 | c01 | 2426 | msm0580 | 2141 |
| b02 | 238 | c02 | 2333 | msm0654 | 7333 |
| b03 | 217 | c03 | 2313 | msm0709 | 8837 |
| b04 | 196 | c04 | 2391 | msm0920 | 4195 |
| b05 | 167 | c05 | 2372 | msm1008 | 2381 |
| b06 | 168 | c06 | 1705 | msm1234 | 5252 |
| b07 | 341 | c07 | 1734 | msm1477 | 7110 |
| b08 | 343 | c08 | 1665 | msm1707 | 1713 |
| b09 | 331 | c09 | 1616 | msm1844 | 517 |
| b10 | 282 | c10 | 1669 | msm1931 | 5218 |
| b11 | 236 | c11 | 862 | msm2000 | 5333 |
| b12 | 253 | c12 | 895 | msm2152 | 12279 |
| b13 | 480 | c13 | 884 | msm2326 | 2525 |
| b14 | 463 | c14 | 855 | msm2492 | 23844 |
| b15 | 462 | c15 | 882 | msm2525 | 17518 |
| b16 | 319 | c16 | 503 | msm2601 | 17024 |
| b17 | 296 | c17 | 499 | msm2705 | 7646 |
| b18 | 337 | c18 | 503 | msm2802 | 9540 |
| | | c19 | 504 | msm2846 | 18494 |
| | | c20 | 509 | msm3277 | 9579 |
| | | | | msm3676 | 5948 |
| | | | | msm3727 | 25659 |
| | | | | msm3829 | 24972 |
| | | | | msm4038 | 1436 |
| | | | | msm4114 | 2333 |
| | | | | msm4190 | 2270 |
| | | | | msm4224 | 1094 |
| | | | | msm4312 | 30628 |
| | | | | msm4414 | 1996 |
| | | | | msm4515 | 4488 |
=== Gerador de casos de teste ===
* Gera um grafo com n vértices e probabilidade de um arco p, e imprime o peso total de uma árvore geradora mínima
* Existe uma chance que o grafo não é conexo. Nesse caso o algoritmo falha.
* Para compilar: Usar C++ e [[http://www.boost.org|Boost]].
#include
#include
using namespace std;
#include
#include
#include
using namespace boost;
// information stored in vertices
struct VertexInformation {
unsigned component;
};
// information stored in edges
struct EdgeInformation {
unsigned weight;
};
const unsigned maxweight = 1000;
// graph is an adjacency list represented by vectors
typedef adjacency_list Graph;
typedef graph_traits::vertex_descriptor Node;
typedef graph_traits ::edge_descriptor Edge;
int main(int argc, char *argv[]) {
assert(argc == 3);
unsigned n = atoi(argv[1]);
double p = atof(argv[2]);
srand48(time(0));
// (1) generate random graph
Graph g;
for(unsigned i=0; i1)
return 1;
// (2.1) MST
vector mst;
kruskal_minimum_spanning_tree(g, back_inserter(mst), weight_map(get(&EdgeInformation::weight,g)));
unsigned cost = 0;
for(vector::iterator i=mst.begin(); i!=mst.end(); i++)
cost += g[*i].weight;
cout << "The weight of a MST is " << cost << "." << endl;
// (3) print out in STP format
cout << "SECTION Graph" << endl;
cout << "Nodes " << num_vertices(g) << endl;
cout << "Edges " << num_edges(g) << endl;
graph_traits::edge_iterator eb, ee;
for ( tie(eb, ee)=edges(g); eb != ee; eb++)
cout << "E " << source(*eb,g)+1 << " " << target(*eb, g)+1 << " " << g[*eb].weight << endl;
}
==== Trabalho 2 (Heaps binomiais) ====
Entrega: 23/03/2009
=== Objetivos ===
* Implementar um heap binomial e verificar a complexidade das operações experimentalmente.
* Verificar a complexidade do algoritmo de Prim usando um heap binomial experimentalmente.
* Comparar as complexidades experimentais dos heaps binários e binomiais.
* Comparar as complexidades experimentais do algoritmo de Prim com os dois heaps.
=== Casos de teste ===
* Podem ser usados os mesmo casos de teste do primeiro trabalho.
=== Mais observações ===
* Para facilitar a avaliação, as implementações do algoritmo Prim devem aceitar uma árvore no formato Steinlib na entrada padrão (stdin) e imprimir o peso total de uma árvore geradora mínima na saída padrão (stdout)((Quem já tem implementação com outro formato, não precisa modificar o parser, so implementar de acordo com as convencões da entrada e saída)).
==== Trabalho 3 (Fluxo s-t máximo) ====
Entrega: 06/04/2009
=== Objetivos ===
* Implementar o algoritmo de Ford-Fulkerson usando busca por largura para achar um caminho s-t((Esse algoritmo é conhecido pelo nome Edmonds-Karp)).
* Verificar a complexidade do algoritmo experimentalmente.
=== Casos de teste ===
* Um gerador de casos de teste em formato DIMACS em C é disponível {{http://www.inf.ufrgs.br/~mrpritt/washington.c|aqui}}.
* Documentação:
To use: cc washington.c -o gengraph
gengraph function arg1 arg2 arg3
Command line arguments have the following meanings:
function: index of desired graph type
arg1, arg2, arg3: meanings depend on graph type
(briefly listed below: see code
comments for more info)
Mesh Graph: 1 rows cols maxcapacity
Random Level Graph: 2 rows cols maxcapacity
Random 2-Level Graph:3 rows cols maxcapacity
Matching Graph: 4 vertices degree
Square Mesh: 5 side degree maxcapacity
Basic Line: 6 rows cols degree
Exponential Line: 7 rows cols degree
Double Exponential 8 rows cols degree
DinicBadCase: 9 vertices
(causes n augmentation phases)
GoldBadCase 10 vertices
Cheryian 11 dim1 dim2 range
(last 2 are bad for goldberg's algorithm)
^ No. ^ Nome ^ Parâmetros ^ Descrição ^ n ^ m ^
| 1 | Mesh | r,c | Grade, 3 viz. 1 direita | rc+2 | 3r(c-1) |
| 2 | Random level | r,c | Grade, 3 viz. rand. 1 direita | rc+2 | 3r(c-1) |
| 3 | Random 2-level | r,c | Grade, 3 viz. rand. 2 direita | rc+2 | 3r(c-1) |
| 4 | Matching | n,d | Bipart. n-n, d viz. rand. | 2n+2 | n(d+2) |
| 5 | Square Mesh | d,D | Quadr. mesh dxd, grau D | d*d+2 | (d-1)dD+2d |
| 6 | BasicLine | n,m,D | Linha, grau D| nm+2 | nmD+2m |
| 7 | ExpLine | n,m,D | Linha, grau D | nm+2 | nmD+2m |
| 8 | DExpLine | n,m,D | Linha, grau D | nm+2 | nmD+2m |
| 9 | DinicBad | n | Linha | n | 2n-3|
| 10 | GoldBad | n | | 3n+3 | 4n+1 |
=== Convenções ===
* As implementações do algoritmo devem aceitar uam instância no formato {{http://lpsolve.sourceforge.net/5.5/DIMACS_maxf.htm|DIMACS}} na entrada padrão (stdin) e imprimir o valor do fluxo máximo na saída padrão (stdout).
=== Verificação ===
* O seguinte código determina o fluxo máximo. Para compilar: Usar C++ e {{http://www.boost.org|Boost}}.
/**
* \file maxflow.cpp
* \author Marcus Ritt
* \version $Id: emacs 2872 2009-01-31 01:46:50Z ritt $
* \date Time-stamp: <2009-03-23 17:52:25 ritt>
*
* Read a maximum flow problem in DIMACS format and output the maximum flow.
*
*/
#include
#include
using namespace std;
#include
#include
#include
using namespace boost;
// a directed graph with reverse edges
struct VertexInformation {};
struct EdgeInformation;
typedef adjacency_list DiGraph;
typedef graph_traits::edge_descriptor Edge;
typedef graph_traits::vertex_descriptor DiNode;
typedef unsigned Capacity;
struct EdgeInformation {
Capacity edge_capacity;
Capacity edge_residual_capacity;
Edge reverse_edge;
};
int main(int argc, char *argv[]) {
// (0) read graph
DiGraph g;
DiNode s,t;
read_dimacs_max_flow(g,
get(&EdgeInformation::edge_capacity,g),
get(&EdgeInformation::reverse_edge,g),
s, t);
// (1) determine maximum flow
cout << edmunds_karp_max_flow(g, s, t,
capacity_map(get(&EdgeInformation::edge_capacity,g)).
residual_capacity_map(get(&EdgeInformation::edge_residual_capacity,g)).
reverse_edge_map(get(&EdgeInformation::reverse_edge,g))) << endl;
}
==== Trabalho 4 (Segmentação de imagens) ====
Entrega: 13/04/2009
=== Objetivos ===
* Implementar um algoritmo de segmentção de imagens como vista em aula.
* Usar a própria implementação do fluxo máximo na solução.
* Segmentar uma imagem em pele/não-pele com pesos de separação diferentes.
=== Casos de teste ===
* O caso de teste é uma imagem de si mesmo.
=== Convenções ===
* As implementações do algoritmo devem aceitar uma imagem no formata PPM plain na entrada padrão (stdin) e imprimir uma imagem no mesmo formato (com todos pixels não-pelo em preto) na saída padrão (stdout).
=== Códigos disponíveis ===
* Ler uma imagem PPM plain
// image data structure
enum { R = 0, G, B };
typedef unsigned short Color;
typedef multi_array Image;
// read an image im PPM (plain) format
void read_ppm(Image& im, istream& in) {
unsigned w,h,maxcolor;
string magic;
in >> magic >> w >> h >> maxcolor;
assert(magic == "P3");
im.resize(extents[h][w][3]);
for(unsigned i=0; i> im[i][j][R] >> im[i][j][G] >> im[i][j][B];
}
* Imprimir uma imagem PPM plain
cout << "P3 " << w << " " << h << " 255 " << endl;
for(unsigned i=0; i
* Converter qualquer imagem para PPM plain (usando {{http://www.imagemagick.org|Image Magick}})
convert -compress none myimage.ext myimage.ppm
* Determinar a probabilidade de pele ou não-pele (para obter valores inteiros multiplicar com p.ex. 10.000.000.000)
// mixture of Gaussians, according to Jones, Regh
const unsigned nG = 16;
const unsigned nV = 7;
double skin[nG][nV] = {
{ 73.53, 29.94, 17.76, 765.40, 121.44, 112.80, 0.0294 },
{ 249.71, 233.94, 217.49, 39.94, 154.44, 396.05, 0.0331 },
{ 161.68, 116.25, 96.95, 291.03, 60.48, 162.85, 0.0654 },
{ 186.07, 136.62, 114.40, 274.95, 64.60, 198.27, 0.0756 },
{ 189.26, 98.37, 51.18, 633.18, 222.40, 250.69, 0.0554 },
{ 247.00, 152.20, 90.84, 65.23, 691.53, 609.92, 0.0314 },
{ 150.10, 72.66, 37.76, 408.63, 200.77, 257.57, 0.0454 },
{ 206.85, 171.09, 156.34, 530.08, 155.08, 572.79, 0.0469 },
{ 212.78, 152.82, 120.04, 160.57, 84.52, 243.90, 0.0956 },
{ 234.87, 175.43, 138.94, 163.80, 121.57, 279.22, 0.0763 },
{ 151.19, 97.74, 74.59, 425.40, 73.56, 175.11, 0.1100 },
{ 120.52, 77.55, 59.82, 330.45, 70.34, 151.82, 0.0676 },
{ 192.20, 119.62, 82.32, 152.76, 92.14, 259.15, 0.0755 },
{ 214.29, 136.08, 87.24, 204.90, 140.17, 270.19, 0.0500 },
{ 99.57, 54.33, 38.06, 448.13, 90.18, 151.29, 0.0667 },
{ 238.88, 203.08, 176.91, 178.38, 156.27, 404.99, 0.0749 }
};
double noskin[nG][nV] = {
{ 254.37, 254.41, 253.82, 2.77, 2.81, 5.46, 0.0637 },
{ 9.39, 8.09, 8.52, 46.84, 33.59, 32.48, 0.0516 },
{ 96.57, 96.95, 91.53, 280.69, 156.79, 436.58, 0.0864 },
{ 160.44, 162.49, 159.06, 355.98, 115.89, 591.24, 0.0636 },
{ 74.98, 63.23, 46.33, 414.84, 245.95, 361.27, 0.0747 },
{ 121.83, 60.88, 18.31, 2502.24, 1383.53, 237.18, 0.0365 },
{ 202.18, 154.88, 91.04, 957.42, 1766.94, 1582.52, 0.0349 },
{ 193.06, 201.93, 206.55, 562.88, 190.23, 447.28, 0.0649 },
{ 51.88, 57.14, 61.55, 344.11, 191.77, 433.40, 0.0656 },
{ 30.88, 26.84, 25.32, 222.07, 118.65, 182.41, 0.1189 },
{ 44.97, 85.96, 131.95, 651.32, 840.52, 963.67, 0.0362 },
{ 236.02, 236.27, 230.70, 225.03, 117.29, 331.95, 0.0849 },
{ 207.86, 191.20, 164.12, 494.04, 237.69, 533.52, 0.0368 },
{ 99.83, 148.11, 188.17, 955.88, 654.95, 916.70, 0.0389 },
{ 135.06, 131.92, 123.10, 350.35, 130.30, 388.43, 0.0943 },
{ 135.96, 103.89, 66.88, 806.44, 642.20, 350.36, 0.0477 }
};
double skin_value(Color R, Color G, Color B) {
double r = 0;
for(unsigned i=0; i
==== Trabalho 5 (Emparelhamentos) ====
Entrega: 04/05/2009
=== Objetivos ===
* Implementar o algoritmo de Hopcroft/Karp que resolve o problema do emparelhamento máximo em grafos bi-partidos.
* Documentar a implementação, em particular as estruturas de dados para a representação do problema.
* Conduzir testes, que demonstram que a complexidade do algoritmo é O(sqrt(n)m).
=== Casos de teste ===
* Gerar grafos bi-partidos randômicas com probabilidade de uma aresta 0 <= p <= 1.
=== Convenções ===
* As implementações do algoritmo devem aceitar um grafo bi-partido não-direcionado no formato [[http://prolland.free.fr/works/research/dsat/dimacs.html|DIMACS]] na entrada padrão (stdin) e imprimir a cardinalidade de um emparelhamento máximo na saída padrão (stdout).
=== Códigos disponíveis ===
* Gerador de casos de teste no formato DIMACS + verificação.
* Para compilar: Usar C++ e Boost.
#include
#include
using namespace std;
#include
#include
using namespace boost;
// information stored in vertices
struct VertexInformation;
// information stored in edges
struct EdgeInformation {};
// graph is an adjacency list represented by vectors
typedef adjacency_list Graph;
typedef graph_traits::vertex_descriptor Node;
typedef graph_traits ::edge_descriptor Edge;
struct VertexInformation {
Node mate; // partner or graph_traits::null_vertex()
};
int main(int argc, char *argv[]) {
assert(argc == 3);
unsigned n = atoi(argv[1]);
double p = atof(argv[2]);
srand48(time(0));
// (1) generate random bi-partite graph
Graph g;
for(unsigned i=0; i<2*n; i++)
add_vertex(g);
for(unsigned i=0; i::vertex_iterator vb, ve;
for ( tie(vb, ve)=vertices(g); vb != ve; vb++)
if (g[*vb].mate != graph_traits::null_vertex())
card++;
cout << "The cardinality of a maximum matching is " << card/2 << "." << endl;
// (3) print out in DIMACS format
cout << "c Bi-partite graph" << endl;
cout << "p edge " << num_vertices(g) << " " << num_edges(g) << endl;
graph_traits::edge_iterator eb, ee;
for ( tie(eb, ee)=edges(g); eb != ee; eb++)
cout << "e " << source(*eb,g)+1 << " " << target(*eb, g)+1 << endl;
}
==== Trabalho 6 (Hashing) ====
Entrega: 18/05/2009
=== Objetivos ===
* Implementar tabelas hash com resolução de colisões com encadeamento, com endereçamento aberto e com cuco hashing.
* Escolher funções hash adequadas.
* Conduzir testes, que determinam a complexidade média (amortizada) das operações insert e lookup para diferentes fatores de ocupação.
=== Casos de teste ===
* Conjuntos de chaves aleatórias.
=== Convenções ===
* As implementações do algoritmo devem aceitar um arquivo na entrada padrão (stdin) que informa na primeira linha
n m
o número de inserções n e o número de consultas m, seguido por n linhas que contém um número inteiro que
representa uma chave a inserir e m linhas que contém um número inteiro que representa uma consulta. O algoritmo deve imprimir na saida padrão (stdout) m linhas que contém o resultado dos m lookups: 0 para uma chave que não pertence a tabela hash, e 1 caso contrário.
==== Trabalho 7 (Minimum cut) ====
Entrega: 15/06/2009
=== Objetivos ===
* Implementar o algoritmo randomizado (simples) visto em aula para calcular um corte mínimo.
* Determinar o corte mínimo de duas formas: (i) Aplicando o algoritmo de Edmonds-Karp n-1 vezes (ii) Usando o algoritmo randomizado.
* Conduzir testes, que determinam o tempo de execução das duas abordagens e a número média de falhas do algoritmo randomizado.
=== Casos de teste ===
* Podem ser usados os mesmos casos de teste do trabalho 3 (ignorar os vértices s e t).
=== Convenções ===
* Os códigos devem respeitar a mesmas convenções do trabalho 3 (imprimindo o valor do corte mínimo na saida padrão).
