Diferenças

Esta página mostra as diferenças entre as duas revisões da página.

--- inf05504:2012-2-trabalhos [2012/10/24 14:58]
marcus [Trabalho 2 (Árvores van Emde Boas)]
+++ inf05504:2012-2-trabalhos [2013/01/13 09:01] (Actual)
marcus [Entregas]
@@ Linha 1: / Linha 1: @@
 ==== Entregas ====
-Atualizado: 02/10/2012
+Atualizado: 13/01/2012
 ^ No. ^ T1 ^ T2 ^ T3 ^ T4 ^ T5 ^
 | 118489 | - | - | - | - | - |
-| 136830 | - | - | - | - | - |
+| 136830 | P | - | - | - | - |
-| 150821 | - | - | - | - | - |
+| 150821 | P | - | P | - | P |
-| 152985 | - | - | - | - | - |
+| 152985 | P | P | P | P | P |
-| 159847 | P | - | - | - | - |
+| 159847 | P | P | P | R | P |
-| 160636 | P | - | - | - | - |
+| 160636 | P | P | P | - | P |
-| 173362 | P | - | - | - | - |
+| 173362 | P | R | - | - | P |
 | 180190 | - | - | - | - | - |
 | 181026 | - | - | - | - | - |
@@ Linha 200: / Linha 200: @@
 /**
  * \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>
+ *   \date Time-stamp: <2012-12-06 17:10:05 ritt>
  *
  * Read a maximum flow problem in DIMACS format and output the maximum flow.
@@ Linha 213: / Linha 213: @@
 #include <boost/graph/adjacency_list.hpp>
 #include <boost/graph/read_dimacs.hpp>
-#include <boost/graph/edmunds_karp_max_flow.hpp>
+#include <boost/graph/edmonds_karp_max_flow.hpp>
+#include <boost/graph/push_relabel_max_flow.hpp>
 using namespace boost;
+// graph element descriptors
+typedef adjacency_list_traits<vecS,vecS,directedS>::vertex_descriptor DiNode;
+typedef adjacency_list_traits<vecS,vecS,directedS>::edge_descriptor Edge;
 // 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 {
@@ Linha 231: / Linha 229: @@
   Edge reverse_edge;
 };
+typedef adjacency_list<vecS,vecS,directedS,VertexInformation,EdgeInformation> DiGraph;
 int main(int argc, char *argv[]) {
@@ Linha 237: / Linha 237: @@
   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 << edmonds_karp_max_flow(g, s, t,
+  cout << push_relabel_max_flow(g, s, t,
                                 capacity_map(get(&EdgeInformation::edge_capacity,g)).
                                 residual_capacity_map(get(&EdgeInformation::edge_residual_capacity,g)).
@@ Linha 273: / Linha 273: @@
   * Para compilar: Usar C++ e Boost.
 <code c++>
 #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;
+// graph element descriptors
+typedef adjacency_list_traits<vecS,vecS,undirectedS>::vertex_descriptor Node;
+typedef adjacency_list_traits<vecS,vecS,undirectedS>::edge_descriptor Edge;
+// information stored in vertices
 struct VertexInformation {
   Node mate; // partner or graph_traits<Graph>::null_vertex()
 };
+// information stored in edges
-int main(int argc, char *argv[]) {
+struct EdgeInformation {};
+// graph is an adjacency list represented by vectors
+typedef adjacency_list<vecS,vecS,undirectedS,VertexInformation,EdgeInformation> Graph;
+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++)
@@ Linha 314: / Linha 313: @@
         Edge e = add_edge(i,j,g).first;
       }
   // (2) get maximum matching
   edmonds_maximum_cardinality_matching(g, get(&VertexInformation::mate,g));
@@ Linha 322: / Linha 321: @@
     if (g[*vb].mate != graph_traits<Graph>::null_vertex())
       card++;
-  cout << "The cardinality of a maximum matching is " << card/2 << "." << endl;
+  //cout << "The cardinality of a maximum matching is " << card/2 << "." << endl;
   // (3) print out in DIMACS format
-  cout << "c Bi-partite graph" << endl;
+  cout << "c Bi-partite graph" << endl << endl;
   cout << "p edge " << num_vertices(g) << " " << num_edges(g) << endl;
   graph_traits<Graph>::edge_iterator eb, ee;
@@ Linha 332: / Linha 331: @@
 }
 </code>
+==== Trabalho 5 (Hashing) ====
+Entrega: 12/12/2012
+=== 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
+<code>
+n m
+</code>
+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.

Marcus Ritt

Ferramentas de Utilizador

Ferramentas de Site

Diferenças

Ferramentas de Página