Program Complexity of Rectangles within the Abstract Tile Assembly Model
· Install LaTeX, a text editor for using LaTex (WinEdt for example), and a vector graphics drawing program (Inkscape for example).
· Write a theorem and proof (using LaTeX) of a non-trivial upper bound on the tile complexity for self-assemblying a 3 x 100 rectangle within the abstract tile assembly model.
· Bonus: Write an additional theorem stating a non-trivial lower bound for a 3 x 100 rectangle
· Bonus: In both cases, try to write an additional theorem generalizing your claim to the case of a 3 x n rectangle.
· Bonus: In both cases, try to write an additional theorem generalizing your claim to the case of a k x n rectangle.
· Bonus: Apply your rectangle upper bound construction to prove a non-trivial upper bound for n x n squares.