Entrega: 13/03/2009

• Implementar um heap binário
• Implementar o algoritmo de Prim usando esse heap
• Verificar as complexidades experimentalmente

• Os casos de teste são parte do Steinlib.
• Todos possuem somente uma componente conectada.

• 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 Boost.

#include <iostream>
#include <cassert>
using namespace std;
 
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/connected_components.hpp>
#include <boost/graph/kruskal_min_spanning_tree.hpp>
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<vecS, vecS, undirectedS,VertexInformation,EdgeInformation> Graph;
typedef graph_traits<Graph>::vertex_descriptor Node;
typedef graph_traits <Graph>::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; i<n; i++)
    add_vertex(g);
 
  for(unsigned i=0; i<n; i++)
    for(unsigned j=i+1; j<n; j++)
      if (drand48() < p) {
        Edge e = add_edge(i,j,g).first;
	g[e].weight = lrand48()%maxweight;
      }
 
  // (2) verify number of connected components
  unsigned cc = connected_components(g, get(&VertexInformation::component,g));
  cout << cc << " connected components." << endl;
  if (cc>1)
    return 1;
 
  // (2.1) MST
  vector <Edge> mst;
  kruskal_minimum_spanning_tree(g, back_inserter(mst), weight_map(get(&EdgeInformation::weight,g)));
  unsigned cost = 0;
  for(vector<Edge>::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<Graph>::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;
}

Entrega: 23/03/2009

• 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.

• Podem ser usados os mesmo casos de teste do primeiro trabalho.

• 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)¹⁾.

Entrega: 06/04/2009

• Implementar o algoritmo de Ford-Fulkerson usando busca por largura para achar um caminho s-t²⁾.
• Verificar a complexidade do algoritmo experimentalmente.

• Um gerador de casos de teste em formato DIMACS em C é disponível 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)

• As implementações do algoritmo devem aceitar uam instância no formato DIMACS na entrada padrão (stdin) e imprimir o valor do fluxo máximo na saída padrão (stdout).

• O seguinte código determina o fluxo máximo. Para compilar: Usar C++ e Boost.

/**
 * \file maxflow.cpp
 *   \author Marcus Ritt <mrpritt@inf.ufrgs.br>
 *   \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 <iostream>
#include <cstring>
using namespace std;
 
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/read_dimacs.hpp>
#include <boost/graph/edmunds_karp_max_flow.hpp>
 
using namespace boost;
 
// a directed graph with reverse edges
struct VertexInformation {};
struct EdgeInformation;
 
typedef adjacency_list<vecS,vecS,directedS,VertexInformation,EdgeInformation> DiGraph;
typedef graph_traits<DiGraph>::edge_descriptor Edge;
typedef graph_traits<DiGraph>::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;
}

Entrega: 13/04/2009

• 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.

• O caso de teste é uma imagem de si mesmo.

• 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).

• Ler uma imagem PPM plain

// image data structure
enum { R = 0, G, B };
typedef unsigned short Color;
typedef multi_array<Color,3> 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<h; i++)
    for(unsigned j=0; j<w; j++)
      in >> 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<h; i++) {
    for(unsigned j=0; j<w; j++)
      cout << im[i][j][R] << " " << im[i][j][G] << " " << im[i][j][B] << " ";
      cout << endl;
  }

• Converter qualquer imagem para PPM plain (usando 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<nG; i++) {
    double t;
    t = pow(double(R)-skin[i][0],2)/skin[i][3] + pow(double(G)-skin[i][1],2)/skin[i][4] + pow(double(B)-skin[i][2],2)/skin[i][5];
    t = skin[i][6]*exp(-t/2) / (pow(2*M_PI,1.5) * sqrt(skin[i][3]*skin[i][4]*skin[i][5]));
    r += t;
  }
  return r;
}
 
double noskin_value(Color R, Color G, Color B) {
  double r = 0;
  for(unsigned i=0; i<nG; i++) {
    double t;
    t = pow(double(R)-noskin[i][0],2)/noskin[i][3] + pow(double(G)-noskin[i][1],2)/noskin[i][4] + pow(double(B)-noskin[i][2],2)/noskin[i][5];
    t = noskin[i][6]*exp(-t/2) / (pow(2*M_PI,1.5) * sqrt(noskin[i][3]*noskin[i][4]*noskin[i][5]));
    r += t;
  }
  return r;
}

Entrega: 04/05/2009

• 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).

• Gerar grafos bi-partidos randômicas com probabilidade de uma aresta 0 ⇐ p ⇐ 1.

• As implementações do algoritmo devem aceitar um grafo bi-partido não-direcionado no formato DIMACS na entrada padrão (stdin) e imprimir a cardinalidade de um emparelhamento máximo na saída padrão (stdout).

• Gerador de casos de teste no formato DIMACS + verificação.
• Para compilar: Usar C++ e Boost.

#include <iostream>                                                                                                  
#include <cassert>                                                                                                   
using namespace std;                                                                                                 
 
#include <boost/graph/adjacency_list.hpp>                                                                            
#include <boost/graph/max_cardinality_matching.hpp>                                                                  
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<vecS, vecS, undirectedS,VertexInformation,EdgeInformation> Graph;                             
typedef graph_traits<Graph>::vertex_descriptor Node;                                                                 
typedef graph_traits <Graph>::edge_descriptor Edge;                                                                  
 
struct VertexInformation {
  Node mate; // partner or graph_traits<Graph>::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<n; i++)
    for(unsigned j=n; j<2*n; j++)
      if (drand48() < p) {
        Edge e = add_edge(i,j,g).first;
      }
 
  // (2) get maximum matching
  edmonds_maximum_cardinality_matching(g, get(&VertexInformation::mate,g));
  unsigned card = 0;
  graph_traits<Graph>::vertex_iterator vb, ve;
  for ( tie(vb, ve)=vertices(g); vb != ve; vb++)
    if (g[*vb].mate != graph_traits<Graph>::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<Graph>::edge_iterator eb, ee;
  for ( tie(eb, ee)=edges(g); eb != ee; eb++)
    cout << "e " << source(*eb,g)+1 << " " << target(*eb, g)+1 << endl;
}

Entrega: 18/05/2009

• 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.

• Conjuntos de chaves aleatórias.

• 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.

Entrega: 15/06/2009

• 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.

• Podem ser usados os mesmos casos de teste do trabalho 3 (ignorar os vértices s e t).

• Os códigos devem respeitar a mesmas convenções do trabalho 3 (imprimindo o valor do corte mínimo na saida padrão).