Assignment 3
COMP6741: Algorithms for Intractable Problems
Students: insert your names and zIDs here
1 Instructions
Assignment 3 is a group assignment. Each group consists of 3-4 members. Each group selects one alternative among
the three alternatives described in section 2–4. By mutual agreement, students may form their own groupings. After
the census date, the lecturer-in-charge partitions the remaining students into groups (see forum).
Due date. All deadlines are 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. It is
crucial to attempt to submit your report before the day of the group presentation.
How to submit. Before starting your work, create one GIT repository per group (i.e., Github, Bitbucket). The
repository may be private or public. Invite the lecturer-in-charge to this repository. The Readme.md file in this
repository contains your zIDs and names, followed by a description of the repository contents, instructions how to
run the code, and all required software and packages clearly stated. The repository should contain a report which
forms the basis for marking the assignment and answers the questions in section 5.
Grade. 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 (LiC) 40%
Presentation (LiC) 20%
Presentation (peers from different groups) 20%
Peer evaluation (peers from same group) 20%
Your group has complete freedom in how to divide the work, but each student should be involved in the final
presentation (pre-recorded video presentations are allowed).
Programming environment. All implementations will be done in SageMath (an extension of Python focused
on graphs and other mathematical objects). Implementations for Alternative 1 may be written in C/C++ instead.
In your group, decide which programming language and version you use and how you plan to collaborate. For
example, in Ubuntu 22.04, sudo apt install sagemath installs SageMath 9.5 by default.
Make sure to write good quality code, following general conventions, with appropriate naming, spacing, testing
procedures, comments and documentation.
Existing implementations and libraries may be reused, as long as their licenses allow unrestricted (academic)
use.
1
2 Alternative 1 - PACE challenge
The PACE challenge is an annual challenge that brings theoretical ideas from parameterized complexity into practice.
In this alternative of Assignment 3, your task revolves around writing a solver for one of the tracks of this year’s
PACE, submit a report discussing your findings, and giving a presentation about your work.
2.1 Expectations
It is expected that you consult the literature and use sound theoretical underpinnings of your work. Design and
discuss various algorithms and aim for several implementations or features that can be switched on and off, so that
you can compare several solutions. Think about preprocessing (simplification rules) and postprocessing (once we
have found a solution, can we make local modifications to try to get an improved solution), 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 a built-in pseudo-random number gen-
erator 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.
2
3 Alternative 2 - educational
Select one concept taught in the course and develop relevant visual learning material.
The implementation of this alternative needs to be in SageMath and develop an interact widget.
Submit both a report and a video demo of your widget to demonstrate how it can be used in teaching.
Examples includes a step-by-step visual execution of an algorithm or a visualization of the effect of graph
modifications to the treewidth of the graph.
3
4 Alternative 3 - open source
Make a contribution to the open-source SageMath project.
Select a topic that is relevant to both the course (i.e., an algorithm solving an NP-complete graph problem) and
the SageMath community (i.e., by checking open issues on Github).
Your implementation should be short, easy to understand and well-documented, so as to minimize any issues
with code submission and publishing.
Past UNSW students have implemented nice tree decompositions and algorithms for maximum leaf spanning
tree and connected dominating set.
4
5 Questions for all alternatives
Exercise 0. Describe how you collaborated, how you split up the work, and the contributions of each team
member. [10 points]
Exercise 1. Describe the design of your project. Describe benchmark instances if relevant. Describe the design of
your tests and testing environment. If relevant, how would your benchmarks scale to larger instances. [50 points]
Exercise 2. Describe your implementation. Include screenshots, code, and testing examples. Describe challenges
you faced, and how you overcame them. [20 points]
Exercise 3. Describe the outcomes of your project and draw conclusions about its merits. What future work is
needed? [20 points]