Changes between Version 10 and Version 11 of SoC2010

Timestamp:

Mar 8, 2010, 8:17:17 PM (13 years ago)

Author:

Andrew Sutton

Comment:

--

SoC2010

@@ -60 +60 @@
  * Topology Generators - One useful set of algorithms not included in the BGL is the ability to easily generate graphs of specific topologies (e.g., [http://mathworld.wolfram.com/PathGraph.html path], [http://mathworld.wolfram.com/CycleGraph.html cycle], [http://mathworld.wolfram.com/StarGraph.html star], etc.). In addition to creating graphs of these topologies, it would be useful to induce these topologies on an existing set of vertices, and query a set of vertices to determine if the topology is admitted by a set of vertices.
  
- * Graph Connectives - The Boost.Graph library is missing [http://mathworld.wolfram.com/Connective.html connectives].  Develop a set of generic algorithms for computing the [http://mathworld.wolfram.com/GraphUnion.html union], [http://mathworld.wolfram.com/GraphJoin.html join], [http://mathworld.wolfram.com/GraphIntersection.html intersection], and [http://mathworld.wolfram.com/GraphDifference.html difference] of graphs. Additional algorithms might be constructed for unary operations (e.g., line graph).
+ * Graph Connectives - The Boost.Graph library is missing [http://mathworld.wolfram.com/Connective.html connectives].  Develop a set of generic algorithms for computing the [http://mathworld.wolfram.com/GraphUnion.html union], [http://mathworld.wolfram.com/GraphJoin.html join], [http://mathworld.wolfram.com/GraphIntersection.html intersection], and [http://mathworld.wolfram.com/GraphDifference.html difference] of graphs. Additional algorithms might be constructed for unary operations (e.g., line graph). Other operations may include a family of [http://mathworld.wolfram.com/GraphProduct.html graph products].
 
-== Heaps and Queues ==
+== Heaps & Queues ==
 There are a number of data structures in `boost/pending` that implement different kinds of heaps and queues that are used in a number of different Boost.Graph (BGL) algorithms. These can be cleaned up, decoupled from the BGL and redeveloped into a useful library for advanced data structures. 
 
@@ -72 +72 @@
 This project requires a working knowledge of C++, templates and data structures.
 
+== Bits & Ints ==
+Boost could use a utility library that brings together and extends a number of existing data structrues and utilities for working with binary data. Specifically, this library might include:
+
+ * Static and dynamic bitfields (i.e., in std, boost or the sandbox).
+ * Compressed value array and vector (like `vector<bool>` but also for multi-bit values)
+ * Programming utilities for bit and bitmask manipulation
+ 
+This may also cover a number of integral special functions, including:
+
+ * Functions for getting carry bits from addition and the high-half of an integer multiply
+ * Sign extension from a length of m bits to a length of n
+ * Rounding right-shifts (correctly rounded integer divide by powers of 2)
+ * Saturating arithmetic operations
+ * Multi-word shifts (used for things like inserting in the middle of a vector<bool>)
+ * Bit reversal
+ * Two-word divide by one-word value (there is often a special instruction for that)
+ * Bit-interleaved arithmetic operations (used for Morton order/cache-oblivious traversals of matrices and similar things) 
+ * Everything from chapter 5 of [https://www-01.ibm.com/chips/techlib/techlib.nsf/techdocs/
+852569B20050FF7785256996007558C6]
+
+Students should be familiar with C++ templates, STL-style data structrues, and logic.
+
+
 = Summer of Code Policies =
 Forthcoming...