~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
JAVA vs C++ -- JAVA's nice features are
a) protection from stray pointers / bad memory management; this can be essential.
b) a rich set of standard class libraries and JSP specifications / classes to help you program, 2D, 3D, images, networking, internet, math, encryption, whatever.
c) A relatively sane syntax and structure for things like overloads, containers / objects, etc. Less messy than some of the obfuscated / confusing stuff you can get into in C++ / STL / et. al. Also less prone to garbage collection / memory management / pointer nightmares.
d) Some decent IDEs / tools both commercial, freeware, etc. Netbeans, et. al.
I'd use if the standard classes implement very compactly / nicely the bulk of what you want to accomplish AND only in the cases where the "other stuff" you need is either easy to do in JAVA or via 3rd party free class libraries. Doing major / complex projects in JAVA can be a pain, especially if good class libraries / components for your middleware don't exist and you'd have to write a lot of glue code or middleware code. Also it is easy to get into cases where some low level / high performance / OS specific things just can't be done in JAVA without using JNI or interfacing to non-JAVA code / OS calls; this is usually a thing to be strenuously avoided.
C++ is nice because it is
a) even more portable in many cases since good free JVMs aren't necessarily available on all platforms yet.
b) High performance (relatively; if it isn't, it's usually your fault)
c) Nice "standard" high level libraries as well as low level libraries, math, complex, STL, et. al.
d) mature with lots of sample code and books / tips on design patterns, abstractions, et. al. (same as JAVA)
e) has a TON of compatible 3rd party libraries you can link to to accomplish things reliably / with high performance / high functionality that exceeds what's possible (easily and without using JNI / RPC / CORBA) through JAVA. e.g. LAPACK, BLAS, LINPACK, OpenCV, DealII, ODBC, FFTW, qhatever.
f) has a "cleaner" interface to call operating system platform specific level DLLs and libraries.
I'd use JAVA when you can *easily* do 95% of what you need using the commonly available class libraries, tools, IDEs, techniques, et. al. using the basic tool set. Don't get bogged down trying to do things that are "hard" or which involve lots of code / work-arounds in JAVA.
I'd use C++ otherwise, assuming that, again, you can find simple / effective libraries to do 98% of what you need, and any code you choose to write yourself is simply expressed in the language. This is usually the case. The main thing to avoid is debugging due to bad aliiasing, garbage collection, pointer misuse, memory management, et. al.
Other ideas --
Concerning GOL and mechanical structures defined on a grid / mesh, I am also reminded that FEM (Finite Element Method) is a classic CS / programming problem for introductory CS / engineering academics. You define a grid/mesh made from simplices, triangles or squares or hexagons in 2D or tetrahedra, cubes, prisms in 3D. This mesh is a "triangulation" of some larger 2D or 3D object, like drawing a big circle on a piece of graph paper; each cell in the graph paper inside your big circle is a mesh cell/element. You use simple 1st order or 2nd order typically algebraic approximations defined at each cell within the mesh to approximate the way stress/strain forces flow through that cell, or heat flows through it, or sound flows through it, or whatever. In the end you "assemble" the simple approximations over all the tiny cells to get an estimate of how the whole bigger structure responds. You can write a simple 2D FEM code in a few hundred lines of code, reading a data file in, producing a data file out. 3D isn't much more complex. There are also codes / libraries like FreeFem, Femster++, DealII, GetDP, and many more that you can call / use in your own code to create a "real" engineering scale program easily with little added code.
You could certainly model something like heat transport across a cylinder, mechanical stress on a cylinder, sphere, block, plate, whatever.
Perhaps parametrically define stacked ideal regular solid blocks (think stonehenge) and model the stress on them (also the sort of thing one might do if one were designing a bridge).
http://www.freefem.org/
http://dealii.org/
http://www.salome-platform.org/
http://geuz.org/getdp/
(FDTD)
http://www.cemtach.com/reference/software/toyFDTD/
et. al.
Speaking of meshes, grids, triangulations -- the calculation of the Delaunay triangulation of a surface and the Voronoi diagram of it are very basic algorithms in computational geometry / science. The triangulation and meshing of a surface has very real every day applications in 2D / 3D graphics, 3D models / games, FEM analysis, CAD/CAM, et. al. Implementing a triangulation algorithm is a simple exercise.
Using various meshing / triangulation libraries and tools to accomplish a given task / rendering / triangulation / model is of course also an extremely commonly useful skill.
http://www.cs.cmu.edu/~quake/triangle.html
http://en.wikipedia.org/wiki/Delaunay_triangulation
http://en.wikipedia.org/wiki/Voronoi_diagram
http://www.geuz.org/gmsh/
http://geuz.org/getdp/
http://www.hpfem.jku.at/netgen/
http://tetgen.berlios.de/
http://libmesh.sourceforge.net/
On a completely different note it'd be interesting to do something a bit interesting like
a) pick a very simple algorithm problem, say addition / multiplication / sorting, factoring, whatever
b) Define the quantum algorithm / system for solving this problem (using only very well known results / designs, nothing new)
c) Write a program to simulate a simple quantum system implementing (a,b).
d) Run the simulation and present the result.
http://en.wikipedia.org/wiki/Quantum_programming
http://en.wikipedia.org/wiki/Quantum_computer
http://en.wikipedia.org/wiki/Quantum_virtual_machine
http://en.wikipedia.org/wiki/Quantum_cryptography
http://en.wikipedia.org/wiki/Quantum_gate
http://en.wikipedia.org/wiki/Quantum_finite_automata
GOL -- sure, it's a great project even in the classic implementation.
One could even use a meshing database / library to help implement it, if desired to get familiarity with using such tools.
Of course designing your own simple data structure as a first pass is highly commended.
It occurs to me there are opportunities to do GOL-2D, 3D, and even 4D which might be interesting extension projects once you get your feet wet with 2D.
I am also reminded of some interesting cross-over with biological / mechanical / computational sciences that might turn a "cool" GOL project into a "WOW!" project if feasible / accomplished. Perhaps you've heard of Folding@Home, where computer based software for molecular modelling is used to predict the ways a strand of protein molecule can physically kink / fold / flex just like a slinky or garden hose or whatever.
Perhaps you've also heard of "DNA origami" and the very mature (yet still relatively new) techniques of using artificial short DNA sequences like LEGOs of various individually unique "shapes" effectively to link together chemically and self assemble into macroscopic (or microscopic / nano-sized if desired) MECHANICAL structures just like you'd do with LEGOs?
It occurs to me that in a simplified level you could program a GOL-2D or GOL-3D that used simulated DNA sequences from a predefined set of fixed geometries (just like a box of LEGOs or jigsaw puzzle parts of different shapes which link in different ways) to form self-assembling structures that could *physically / chemically* actually be done with REAL DNA. Sort of a DNA tetris / GOL-2d or GOL-3D. Using DNA and in 3D that'd sort of be the "ultimate" GOL in a few new twists of the sense!
I'm not suggesting (for a start) molecular modelling of the DNA and its reactions itself, but just to perhaps treat the blocks as predefined objects with fixed geometric / assembly attributes (like puzzle pieces / LEGOs) and animate an arbitrary assembly process/sequence for them (like TETRIS) and display the final result GOL style. A GOL that is really (sort of) a GOL!
http://www.npr.org/templates/s...ry.php?storyId=5281562
http://www.nature.com/nature/j.../full/nature04586.html
http://www.nature.com/nature/j...ab/nature04586_F1.html
http://www.dna.caltech.edu/DNA...arch_publications.html
Folding DNA to create nanoscale shapes and patterns
Paul W. K. Rothemund
Paul sends a swarm of staple strands to tie viral DNA in knots...thereby self-assembling 100 x 100 nm objects with roughly 6 nm resolution from the 7 kilobase single-stranded genomic DNA of M13mp18. Rectangles. Squares. Triangles. Stars. Even a smiley-face. About 50 billion copies of each, in a typical reaction, and with very high yields. It works like magic. We did some calculations... Paul's smiley faces constitute the most concentrated happiness ever experienced on earth. Each spot in such a structure contains a unique address and can be addressed as such by DNA hybridization, allowing one to "write" on the DNA origami objects. Words. Pictures. Snowflakes. A map of North and South America. We did some more calculations... Paul probably made more maps than have ever been produced in the history of mankind -- we're definitely talking quantity over quality here. The applications of this technology are likely to be less whimsical. For example, it can be used as a "nanobreadboard" for attaching almost arbitrary nanometer-scale components, and there are few other ways to obtain such precise control over the arrangement of components at this scale. You'll never look at M13 phage DNA the same way again...
[Nature 440, 297-302 (16 March 2006). article, .pdf, 575 KB. News and View, .pdf, 300 KB. Supplementary material: .pdf, part 1, 6.3 MB; .pdf, part 2, 193 KB. ]
# Design of DNA origami
Paul W. K. Rothemund
Paul talks a little about the design software and future possibilities.
[Proceedings of the International Conference on Computer-Aided Design (ICCAD) 2005: .pdf, 646 KB.]
# Scaffolded DNA Origami: from Generalized Multicrossovers to Polygonal Networks
Paul W. K. Rothemund
Paul makes a DNA origami especially for Ned Seeman, and sketches how polygonal networks and polygonal three-dimensional structures can be created.
[in Nanotechnology: Science and Computation, pages 3-21, 2006. Preprint (22 pages): .pdf, 1.4 MB.]
Toward Reliable Algorithmic Self-Assembly of DNA Tiles: A Fixed-Width Cellular Automaton Pattern.
Kenichi Fujibayashi, Rizal Hariadi, Sung Ha Park, Erik Winfree, Satoshi Murata.
In biological morphogenesis, genetic information is expressed as biochemical processes that create an organism. In algorithmic self-assembly, information in DNA is expressed as complex folding and crystallization processes that construct intricately patterned supramolecular objects. Here, we combine several techniques developed in this lab -- Erik's DNA tiles, Paul's DNA origami, Rebecca's ribbon crystals, and Rob's (as yet unpublished) origami seeds -- to self-assemble a fixed-width cellular automaton pattern related to Sierpinski triangles. (One commentator calls them "snakeskin nanobelts", an odd but evocative phrase.) Along the way, we gained some insights about assembly errors and how to prevent them -- about how algorithmic crystals aggregate and grow together and about lattice defect and computation error rates.
[Nano Letters, 8(17) 1791-1797, 2008 (5 pages): .pdf, 884 KB and supplementary information, 1.9 MB. Highlighted in Nature. Made the cover of Nano Letters!
Toward Reliable Algorithmic Self-Assembly of DNA Tiles: A Fixed-Width Cellular Automaton Pattern.
Kenichi Fujibayashi, Rizal Hariadi, Sung Ha Park, Erik Winfree, Satoshi Murata.
In biological morphogenesis, genetic information is expressed as biochemical processes that create an organism. In algorithmic self-assembly, information in DNA is expressed as complex folding and crystallization processes that construct intricately patterned supramolecular objects. Here, we combine several techniques developed in this lab -- Erik's DNA tiles, Paul's DNA origami, Rebecca's ribbon crystals, and Rob's (as yet unpublished) origami seeds -- to self-assemble a fixed-width cellular automaton pattern related to Sierpinski triangles. (One commentator calls them "snakeskin nanobelts", an odd but evocative phrase.) Along the way, we gained some insights about assembly errors and how to prevent them -- about how algorithmic crystals aggregate and grow together and about lattice defect and computation error rates.
[Nano Letters, 8(17) 1791-1797, 2008 (5 pages): .pdf, 884 KB and supplementary information, 1.9 MB. Highlighted in Nature. Made the cover of Nano Letters!
Computation with Finite Stochastic Chemical Reaction Networks.
David Soloveichik, Matt Cook, Erik Winfree, and Shuki Bruck.
Some people think of chemistry as a bag of colored marbles. Shake really hard. When the marbles hit each other, they change colors, according to rules. So there's a bit of structure, but it's a chaotic mess -- at any given moment, it's anyone's guess what will happen next. Can chemistry do computation, then? At least since Jacob & Monod, and perhaps before, it has been generally recognized that biochemical systems, such as genetic regulatory networks, can operate much like electrical circuits -- the concentration of some chemical species can carry an ON/OFF signal. Arbitrary digital circuit logic can be performed. If enough marbles turn green, we'll say the output was "1". Bennett even realized that if we string the marbles together like a necklace of beads, then Turing-universal computation can be performed. That's strictly more powerful, theoretically, than digital circuits. What we show here is that finite stochastic chemical reaction networks -- bags of marbles without strings -- can also perform Turing-universal computation. Reasonably quickly, too! This result holds if we accept some probability, no matter how small, that the chemistry will produce the wrong output... but remarkably, the result fails if we insist that the chemistry always and without exception produces the correct output. It pays to be tolerant, if even ever so slightly.
[Natural Computing, (on line Feb 2008), or Technical Report CaltechPARADISE:2007.ETR085 (19 pages): .pdf, 836 KB. ]
# The Computational Power of Benenson Automata.
David Soloveichik and Erik Winfree.
In a series of experimental papers, Benenson et al demonstrated how information encoded in DNA can be processed autonomously by a molecular automaton consisting of a type IIS restriction enzyme (FokI) and a collection of DNA "rule molecules". They constructed several two-symbol, two-state finite state machines as well as several 4-input AND/NOT gates. Ultimately, applications envisioned include diagnosis of mRNA and delivery of a theraputic molecule. Here, we formalize the class of logical computations that can be performed by such systems and show that, in our abstraction, the finite-input computations that can be performed by Benenson automata can be exactly characterized by a connection to branching programs -- which indicates that (if restriction enzymes slightly more powerful than FokI can be found) Benenson automata are considerably more powerful than we had originally imagined!
[Preprint: cs.CC/0412097 on arXiv.org (18 pages): .pdf, 223 KB.]
[Journal version: Theoretical Computer Science 244(2-3):279-297, 2005, (19 pages): .pdf, 192 KB.]
[Note: Thanks to remarkably thorough comments from the reviewers, the clarity and precision of the definitions and proofs in the journal version have been improved substantially. Read this version, not the arxiv version!]
# Algorithmic Self-Assembly of DNA Sierpinski Triangles.
Paul W.K. Rothemund, Nick Papadakis, Erik Winfree.
Our first demonstration of algorithmic crystals, wherein molecularly-encoded information directs the growth process to create a complex pattern. The DNA crystals are, at the molecular level, a two-dimensional woven fabric of short DNA strands. Both because this programmable growth could be considered a super-simplified toy model of organismal development, and because DNA is the central information molecule in biology, I like to call it "weaving the tapestry of life". This is a substantial personal victory for me: I proposed that this should be possible in 1995 as a graduate student -- nearly 10 years later, Paul's efforts made it actually happen.
[PLoS Biology 2 (12) e424, 2004, (13 pages): .pdf, 4.6 MB.] See also Supplementary Material. (PLoS Biology has a synopsis and a primer by Chengde Mao for this paper. Also it was highlighted in Nature by Philip Ball.)
Complexity of Self-Assembled Shapes.
David Soloveichik and Erik Winfree.
If you can effectively describe a shape -- e.g. write a computer program that draws it -- then can the shape be self-assembled by spontaneous local processes from just a few kinds of pieces? The answer may be "no" if you are concerned about the exact size of the shape, but if it is only the form of the shape that matters, then the answer is always "yes". In fact, the Kolmogorov complexity of a shape provides upper and lower bounds for the number of tile types necessary to self-assemble it (at some scale). Proof of this result makes use of a construction for programmable "blocks" that execute a Turing machine simulation to guide the growth process, and introduces a new proof technique for establishing when growth is independent of the order in which tiles are added. This work suggests that scale plays the same role in self-assembly as does time in computability: when you ignore it and just ask, "can it be done at all?", then the theory becomes clean and elegant.
[SIAM Journal on Computing 36 (6) 1544-1569, 2007, (26 pages) paper, 810 KB.] [preprint cs.CC/0412096 on arXiv.org (25 pages): .pdf, 488 KB.] [extended abstract in DNA Computers 10, LNCS volume 3384:344-354, 2005, (10 pages): .pdf, 272 KB, color, .pdf, 271 KB, B/W]
The Program-Size Complexity of Self-Assembled Squares.
Paul W. K. Rothemund and Erik Winfree.
Are there small self-assembly programs for building squares of a particular size? Yes! Also contains a nice presentation of our model of self-assembly.
[in STOC 2000, (10 pages): squares_STOC.ps.gz, 114 KB, squares_STOC.ps, 761 KB, or squares_STOC.pdf, 243 KB]
On Applying Molecular Computation to the Data Encryption Standard.
Leonard M. Adleman, Paul W.K. Rothemund, Sam Roweis, Erik Winfree.
An algorithm for breaking DES is designed for the Stickers model. Size, space, and error rates of the resulting machine are considered.
[in DNA Based Computers II, pgs 31-44, 1998 (21 pages): des.pdf, 185 KB, or des.ps.gz, 77 KB, or des.ps, 211 KB]
The journal version: [ Journal of Computational Biology, 6(1): 53-63, 1999 .pdf, 771 KB]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~