COMP6741: Algorithms for Intractable Problems Assignment 3
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Assignment 3
COMP6741: Algorithms for Intractable Problems
Students: insert your names and zIDs here
1 Instructions
Assignment 3 is a group assignment. Groups are determined by the lecturer-in-charge and each group consists of at least 3 members.
For the solutions to this assignment, you may rely on all theorems, lemmas, and results from the lecture notes. If any other works (articles, Wikipedia entries, lecture notes from other courses, etc.) inspired your solutions, please cite them and give a list of references at the end. You may use any result you find in the literature, without re-proving it. Existing implementations and libraries may also be used, as long as their licenses allow unrestricted academic use.
If you have questions about this assignment, please post them to the Forum.
Due date. This assignment is due on Friday, 14 April 2023, at 5pm Sydney time. Submitting x hours after the deadline, with x > 0, reduces the obtained mark by 5 · ⌈x/24⌉ marks. No submissions will be accepted 5 days (120 hours) or more after the deadline.
How to submit. There is one Bitbucket GIT repository per group. The Readme.md file in this repository describes where to put various files, including the report answering the questions below, by the submission deadline.
2 Background
The PACE challengeis an annual challenge that brings theoretical ideas from parameterized complexity into practice. This year’s challenge is to compute the twinwidth parameter of graphs, or compute an upper bound via heuristics.
2.1 Outline
In this assignment, your task revolves around writing a solver for the Heuristic Track of PACE 2023, submit a report discussing your findings, and giving a presentation about your work.
A part of the Assignment 3 mark is determined by peer grading where students are asked to grade the work of other students based on the collaboration within their own team and the presentation of other teams.
Report + code Presentation Peer evaluation |
80% 10% 10% |
Each team is responsible for dividing the work among the team members.
2.2 Programming environment
All implementations will be done in SageMath 9.5 (or later, up to the most recent stable version, which is 9.8). It extends Python3 by adding mathematical capability from either external Python packages or inbuilt methods. It has an extensive implementation of graphs and some graph algorithms.
In your group, decide which version of SageMath you use and how you plan to collaborate. For example, in Ubuntu 22.04, sudo apt install sagemath installs SageMath 9.5 by default.
Figure 1: This graph and its tikz representation were generated in SageMath.
Make sure to write good quality code, following general conventions, with appropriate naming, spacing, testing procedures, comments and documentation.
2.3 Expectations
It is expected that you consult the literature and use sound theoretical underpinnings of your work. Design and discuss various heuristics for computing contraction sequences with small width. Aim for at least 3 implementations / variants. Think about preprocessing (simplification rules) and postprocessing (once we have found a contraction sequence, can we make local modifications to try to get another one with smaller width?), and randomization where we get a variety of solutions by running the algorithm multiple times.
Random numbers If you use randomization, it is recommended to use the built-in pseudo-random number generator of Python as a proxy for random number generators. For your work to be reproducible (and to more easily debug and update results of a battery of tests), it is recommended to work with fixed seeds.
import random
random .seed(int(5787549218)) # using a seed helps with reproducibility
print(random .randint(1 ,100)) # prints the same integer each time we run this code
Experimental evaluation To test your implementations, use a small-scale test set of up to 100 instances (these should not all be random instances), describe the origin of these instances, and how you would scale up the testing for a more rigorous experimental analysis.
3 Exercises
Exercise 0. Describe how you collaborated, how you split up the work, and the contributions of each team member. [10 points]
Exercise 1. Design heuristics for Twinwidth. What is the reasoning why these heuristics should perform well? [20 points]
Exercise 2. Implement these heuristics, describe challenges you faced, and how you overcame them. [20 points]
Exercise 3. Describe your benchmark instances, the setup of your experimental analysis, and your testing environment. How would you scale up this experimental analysis? [20 points]
Exercise 4. Describe your experimental results and draw conclusions about the effectiveness of the heuristics. [20 points]
Exercise 5. Give an honest assessment how competitive your team would be at PACE 2023. What additional steps are needed to increase your competitiveness? [10 points]
2023-04-15