Project

The course will culminate with a final project in which students explore a topic related to tilings and computation, from either a theoretical or a practical perspective. The project can be completed alone, or in groups of two; marking will be the same either way.

Proposal

Due date: Monday, 30 June, 11:59pm (by email)
Weight: 5%

Prepare a short document describing your plans for the final project. The proposal creates a reason for you to start thinking in advance about what you might want to do, and to look around for existing resources (papers, websites, software) that might help you achieve your goals. Of course, it's also an opportunity to receive feedback about aspects of the work that are easier or more difficult than they might appear, pointers to additional resources, and so on.

The proposal doesn't have to be long: a single page is probably sufficient, maybe two pages if you have a lot to say or want to include some images. You'll want to demonstrate that you have some idea of what the topic is and what sort of work will be involved. There's no fixed format, but think about responding to the following questions:

What's the general topic? How does the project fall into the intersection of tiling theory and computation?
What sort of work will be involved? What kind of artifact(s) will you produce? It's safe to assume that most projects will take one of two forms: "write a piece of software" or "write a research paper". Other formats are certainly possible (e.g., "write a survey paper"; "create an artwork"; "prepare a lecture or video that explains a difficult concept"), as long as there's sufficient depth related to the topic of the course. Check with the instructor before proposing anything too exotic.
What resources have you found so far? Cite any relevant papers. What tools will you use? How will you build upon software that's already out there, if applicable? If you're re-implementing an algorithm that already exists, how will you demonstrate that the new work is your own?
What are your stretch goals? That is, if the stars align and everything you do works perfectly on the first try, what else would you like to accomplish with the project?

The proposal isn't a contract: it's only natural in a research context that you might drift away from the precise topics of the proposal during your work. Of course, finding a more focused, more concrete topic at this stage permits better feedback, and may help you stay more on track.

Submit your proposal by emailing it to the instructor as a PDF attachment before the deadline. Make sure to include your name in the PDF. If you're working in a group of two, you can submit a single PDF containing both of your names.

Work-in-Progress Presentation

Dates: July 22, 24, and 29 (see class schedule)
Weight: 10%

Prepare a 10–15 minute presentation that describes your project, highlights the work you've done already and any results you've obtained, and identifies challenges yet to be overcome. There is no fixed format for the presentation. The main goals are to introduce your topic to the other students in the class, and to provide a work-in-progress report. Here are some suggestions of possible (but not required) points to cover:

What's the project about? This can essentially be a live version of your proposal. Remember that while I know what's in the proposal, the other students in the class probably don't.
Do you have any prototypes / wireframes / mock-ups that illustrate what you're hoping to achieve? Any inspirational images or examples? Show them.
What's the structure of your project? What languages or libraries are you using?
What's working so far? If you have a prototype implementation and/or any interim results, please show them off. Live demos are not required, but would be welcome if you're brave.
What's not working? What are you stuck on, or worried about getting to, now that you've dug a little deeper? This may be a good opportunity to get some brainstorming help from a captive audience: they have ideas for techniques to try, libraries to look at, papers to read, and so on.
What are your next steps?

Obviously, part of the reason to give a work-in-progress report is to generate the motivation for you to have some progress to report on! The presentations come relatively early in the overall lifecycle of the project, but I hope you'll have at least a couple of small results to demonstrate. If not, you may have to show some mock-ups of what you hope to accomplish. In any case, your mark for the presentation will be based on the quality of the presentation itself, and not how far along you are in your work.

For students working in teams, you can decide how to divide up the presentation time, as long as each student delivers a non-zero amount of the presentation. You will receive the same grade.

Final Submission

Due date: Friday, August 15th
Weight: 10% (report), 15% (content)

You must submit a final report and a source code repository (if your project has a software component). The report can be sent to me via email, in the form of either a PDF or a URL that points to a live web page. The report can optionally include a demo video (more details below); ideally, put the video online somewhere and send me a link, or embed it in your report if submitting it as a web page. The source code can come as a standard archive (.zip or .tar.gz), or as a link to an online repository to which I have access. Include a README that helps a reasonably competent programmer build and run your software.

There is no fixed format for the report. You might consider aiming for the format of a Bridges paper, against the possibility that strong projects could become submissions to next year's conference. There's no required length, but I suggest aiming for 5–8 pages, maybe more if you include lots of images (please don't go overboard with writing: the turnaround time for me to submit final grades is quite short).

If you're comfortable preparing your report in the style of a technical paper, then feel free to do so. If you prefer "project report for a grad course" format, that OK. Here are some suggested points to cover.

As always, summarize the topic: what's the high-level goal of the project?
At a high level, how did things work out? Rather than leaving it to the reader's imagination, you can come out and say how much you accomplished, what you had to leave on the table, and so on.
What work did you end up doing? Describe the system you built, in terms of what it does, any interesting algorithms or data structures you brought to bear, the programming language and support libraries you used, and any unusual aspects of the architecture that you want to highlight. If you made heavy use of support libraries or pre-existing code written by others, be sure to clarify the work that you did (i.e., prove that the work didn't consist solely of wiring together a bunch of already written code). If you relied on the assistance of LLMs to write code, mention that here, and indicate how much they helped.
Explain how to use your software. This is basically a short user manual.
Show off your results. Polished results are great; partial result are fine too, and you should say what worked and what didn't work about them.
Talk about what didn't work. What ideas that you had hoped to get to ended up presenting unexpected challenges? Did you encounter obstacles that made you think "Oh, so that's why nobody has done this before"? If you're stuck on some aspects of the project, but have a pretty good idea of how you'd get unstuck if only you had more time, say something about that.
What might be next? What could a future grad student in this course do to extend your project? How might you have adjusted the original topic based on what you learned?
Include any relevant references.
If you used any LLMs in preparing your report, disclose that at the end. Indicate how you used the LLM. By now, you know my feelings on this point. An LLM can be useful to polish your text, but don't use it to generate text. I'd rather read writing in your voice, warts and all, than more content-free AI slop full of pretty words.
Optionally, prepare a short video that demonstrates your software and shows a couple of results. If you want, this video can take the place of the user manual suggested above, as long as it covers all the features. Keep it short: a few minutes at the most. I will consider the writing and the video together as a whole, meaning that a good video could take the place of some of the writing. But style and polish matter in both cases, so the quality of the video will matter at a level comparable to the quality of the writing.

I'm somewhat open-minded about creative final submissions. If you have a good idea for how to submit your work that doesn't quite fit the mold above, you might be able to win me over. If you're not sure, you can always ask me first. If in doubt, it's fine to stick with "the usual".

Suggested Topics

The project is intended to be open-ended, so there's no specific list of topics to choose from. Thus everything below is just some thinking-aloud advice about possible topics, drawn in part from my personal wish list.

A natural starting point for a CS graduate interested in applied research is to implement a paper. A number of papers in the bibliography are about highly practical computer graphics algorithms (e.g., "Texture Tilings on Arbitrary Topological Surfaces") or computer searches of shapes (e.g., "Heesch numbers of edge-marked polyforms"). You're free to pick and choose: you're not required to precisely implement the entirety of any one paper, and there may be value in combining ideas from multiple sources to produce something new.

Students more interested in theoretical research might try producing some new results in complexity or undecidability. At the outset this feels somewhat higher risk, but you may be more comfortable than I am at writing theoretical papers.

Here's a list of random topics that might be interest. I'll add to the list of other ideas arise in the next few weeks.

Create an interactive tool for designing substitution tilings. Such a tool could let you author the shapes of the prototiles and each one's substitution rule, and show a preview of the resulting tiling. A good starting point would be a tool that allowed you to reproduce existing tilings (like those in the Tilings Encyclopedia). On top of that, it would be interesting to develop tools to verify automatically that a substitution system results in valid tilings. Then, think about how an interactive tool might assist a user in discovering new substitution systems. (Note that an interactive viewer for substitution tilings could form the foundation of an improved Tilings Encyclopedia—that site currently relies on static rasterized images.)
Create an Escherization tool that runs interactively in a web browser. The user can draw a shape, and the tool will find similar shapes that tile the plane (isohedrally). Use any of the existing published Escherization algorithms (i.e., a black box simulated annealing approach, or a maximum eigenvalue approach). In a first pass, it may make sense for focus on a small set of isohedral types.
Create an interactive polyform checker that runs in a web browser. The user would be able to click on cells in a grid, and as they do the software would report the tiling-theoretic behaviour of the shape (e.g., a periodic tiler with a given isohedral number, or a non-tiler with a given Heesch number). Consider starting with polyominos and expanding to other grids (most obviously, polyhexes and polyiamonds).
Create an interactive tool for authoring sets of Wang tiles and constructing patches of tiles from a given set. Such a tool would be useful for learning about the behaviour of Wang tiles, and for exploring the behaviour of existing sets.
Adapt existing algorithms to 3D. Very little is known about the tiling-theoretic behaviour of 3D shapes like polycubes. It would be interesting to adapt existing algorithms to check for, e.g., Heesch numbers and isohedral numbers in 3D.
Compute isohedral numbers in general grids. My heesch-sat software was originally designed to compute the Heesch numbers of shapes known not to tile the plane, but I'd like to borrow ideas from Joseph Myers to compute isohedral numbers of shapes that tile periodically. I've been working on this a little bit, but feel free to overtake me.
Try to obtain tight asymptotic bounds on (a) the number of neighbours that a polyform in a given grid (say, polyominos) can have, and/or (b) the computational complexity of checking whether a polyform has a Heesch number of at least one (i.e., if it can be completely surrounded by copies of itself).