Projects for CS605 practical work

The practical work for CS605 will comprise a significant amount of theorem proving described in a self-contained report.

Topic

The topic is analysis of the computational power and/or analysis of the computational complexity of a number of Bebras or Bebras-style tasks. Computationally different variants of the tasks should be explored. One task should be chosen, with proofs using between two and four different variants of the task. If you cannot generate enough interesting variants of your task for all the proofs you need (for example if the task is a very easy task) you can choose a second task. You can invent your own Bebras-style computational thinking task(s) for extra credit. The international Bebras website is here, with links to Bebras websites from individual countries, and links to publications, so that you can gain an understanding of the Bebras initiative.

Students must submit a report appropriately through Moodle (use appropriate link on CS605 Moodle page, not a Moodle forum message) that includes all proofs completed as part of the project as a single PDF file (see below for detailed requirements).

No two students will be allowed to choose the same task (or computationally-equivalent task) -- please also check the tasks chosen by students in previous years. Tasks will be allocated on a first-come-first-served basis. The tasks chosen to date are as follows.

Tasks chosen in previous years (Bebras year: task name):

original:	Ball Sport, Beaver Jump Challenge 2, Calories Intake, City Traffic, Cricket, Rainbow
2011:	Fast Laundry, Hierarchical Structure
2012:	Beaver Navigation, Bebrocarina, Beaver Pyramid, Falling Ball, Glasses, Programmed Robot, Rotating Puzzle
2013 (AU 2014):	Watering a tree, Mirrored or not?, Zebra Tunnel
2014 (AU 2015):	Funny Windows, Ice Cream, Loading Lisas, Log-Art, Mobile Phones, Only Nine Keys, Select a Picture, Tic Tac Toe, Village Network
2015 (AU 2016):	Beaver the Alchemist (Crock of Gold 2021), Birthday Balloons, Bowl Factory, Bracelet, Collecting Pollen, Crane Operating, Cross Country, Dream Dress, Fair Share, Kangaroo, Stack Computer, Word Chains
2016 (AU 2017):	Beach Flags, Beaver Code, Bebras Painting, Broken Window, Candy Jar, Exciting Soccer, Magic Potions (Magic Potions 2021), Paint It Black, Shelf Sort, Spherical Robot, Sudoku
2017 (AU 2018):	Bird House, Bracket Bracelet, Brackets, Chameleon, Dancing Man, Levenshtein Distance, Message Service, Parking Lot, Robot, Skaters, Sticks and Shields, Small program, Swapping Dogs, The Way Home, Toothbrushes and Lollipops
2018 (AU 2019):	Balloons, Beaver Graffiti, Beaver Jump Challenge, Bird Colours, Elevator, Flipping Cards, Flowerbed, Flowers, Getting Dressed, Gifts, Honey Pot, Infinite Ice-cream, Lemonade Party, One Hour One Task, Passcode, Pizza, Robots, Rotation Game, Rubbish Robots, Shoe Prints, Signup Debugging, Simon Says (Spinning Squares), Three Friends, Treasure Maps, Trees in a Circle, Visiting Friends, What to Wear
2019 (AU 2020):	Ancient Message, Box of Balls, Box of Marbles, Crossroads, Double Parked, Escape Room, Filling Boxes, Friendship Bracelets, Greener Flight Routes, Language Detection, Let's Decorate, Light Buttons, Making Stitches, Many Beavers, Mystery Beaver, Plates, Recover My Robot, Recycling, Seating Plan, Swapping Cats, Water Pouring
2020 (AU 2021):	A Tree Structure, Bear Selection, Bowls, Connect the Dots, Crypto Keys, Drawing a Robot, Flying Bees, House Numbers, Library Books, Lisa's Lovely Lyrics, Puzzle Pieces, Processing Objects, Rare Mushrooms, Scarf Making, Sock Selection, Train Ticket Reservation, Train Tracks
2021 (AU 2022):	Arranging Objects, Coin Bag, Colourful Tubes, Forest Towers/Forest Watch, Genetic Data, Object Swap Arranging, Overlapping Coins, Picking up Carrots
2022 (AU 2023):

How do I choose a topic?

• On CS605 Teams go to the channel "Choosing Bebras tasks for project work". Open the three links listing choices for tasks. Choose a task that is not already taken by one of your classmates (see previous messages on this Teams channel). Send a "New conversation" message on the channel with the name of the task. Double check you were the first to select that task -- if you were not, delete your message and repeat until you successfully select a task.
• It is possible to change your mind at any time by deleting your message and sending a new message with your new choice, as long as your new choice is not already taken.

How will the report be marked?

• Only reports uploaded appropriately through Moodle (use appropriate link on CS605 Moodle page, not a Moodle forum message) on or before the date and time specified on the CS605 homepage will be marked, unless alternative arrangements have been agreed with me in advance. The report should be in the form of a single PDF document.
• The projects will be marked by giving equal weighting to each of the following four criteria:
  • Structure and explanation (e.g. does your report have a beginning middle and end, do you explain the background or context of the work, do you have a conclusion, does each part of the report follow logically from what came before, do your explanations convince the reader of your understanding of the material),
  • Technical accuracy (e.g. are there few flaws, contradictions, and omissions causing ambiguity in the proofs or explanations),
  • Demonstration of understanding by incorporating novel information (e.g. your own unique examples, or unique explanations of concepts in your own words), and
  • Difficulty of the topic (e.g. did you tackle a problem that would be regarded as challenging at masters level, did you choose variants of tasks that went beyond standard textbook examples such as aⁿbⁿ, ww^R, and ww).
• A submission link will be active on CS605 Moodle. This Moodle link automatically uses Turnitin technology that compares the text of student submissions with a range of internet sources, including other CS605 project reports. It is expected that the text of your reports will closely match many sentences in the CS605 project examples handout, and the Sipser book, and may match other sources, and this is not a problem so long as you properly reference this material and only claim, as your own work, your own original text and inventions.

What should be in my report?

• Your report should be a single PDF file.
• Your report should contain a title page with the project title, your student number (but not your name), the date you finished writing the report, the institution name "Maynooth University", and the module name "CS605".
• Your report should have a section "Introduction" that (i) briefly explains what your project was about, (ii) states your assumptions about what computer theory the reader knows before reading your report.
• The body of your report should be divided into sections. The particular section names in the body of one's report will vary from project to project, in particular depending on whether one or several games are analysed, whether programming was part of the project, whether the multiple proofs are related or independent, and so on. One section will be "Conclusion" that briefly summarises what was in your report and can suggest future directions for the work. An "Appendix" should contain screenshots of the tasks chosen. One section will be "References" (see the next bullet point).
• There should be a section called "References", with each numbered entry in the list of references containing an author, publication title, source (book, journal, webpage), and publication date. All material in the body of your report that was taken from other sources (e.g. books, journals, websites, lecture notes) must be clearly identified with a reference number. For any fact, code, equation, proof, example and picture/figure in your report that is not followed by a reference number (e.g. "[5]"), it will be assumed you are claiming this as your own invention.
• There should be an appendix showing screenshots of the original version of the Bebras task(s) that you analysed in your report.
  • Marks will be deducted for failures to properly reference such material in your report. This way I can clearly identify what programs, examples, proofs, and proof ideas are the novel information that you are offering as your project. For multiple sentences, you can reference using a sentence similar to "The sentences in this paragraph were taken from/paraphrased from [4]." or "The following proof is paraphrased from [7]."
• Regarding the expected length of the report, there is no expected length as some complicated proofs can be short.
  • The effort put into the project will be expected to be equivalent to four full days of work, not including the self-study time required to understand and practice the module material delivered in lectures, and the projects will be marked assuming each student did invest that amount of effort.
  • There should be four proofs in your report:
    1. proving a language is regular,
    2. proving a language is context-free,
    3. proving a language is not regular, and
    4. proving a language is not context-free.
  • Note, proofs that a language is decidable or Turing-recognisable would be considered too basic for this report.
  • As a substitute for (or in addition to) these proofs, students can include more sophisticated proofs such as using a Turing machine to prove the computational complexity of deciding a language, or proving a language is NP-complete, NP-hard, or outside NP -- discuss with the lecturer if you wish to take this option.
• Good luck!