Assessment 1

15. Assessment 1#

15.1. Programming for Reusability#

15.2. Background#

The backtracking algorithm is an algorithm which builds solutions to problems in an incremental manner and backtracks to previous partial solutions, when the algorithm encounters an infeasible solution. The core algorithm is described in terms of a set of abstract operations and can thus to applied to a very wide range of problems. As such, the backtracking algorithm is useful for demonstrating the importance of reusability of code.

This assessment requires that you implement a backtracking algorithm to solve two problems. In both cases, the problem has been well studied, so you should be able to assess the correctness of your algorithm. In particular, the primary objective of the assessment is to produce a reusable implementation of the backtracking algorithm in the sense that the core code of the algorithm requires no modifications when used for solving the different problem types. For each problem, one should only need to specify the abstract operations required to run the backtracking algorithm.

Note that the backtracking algorithm may require a large amount of computational resource to solve the problems even for quite small values of the input parameters.

The problems to be solved are:

15.2.1. Problem 1#

For a given number number \(n\), determine all of the integer partitions of \(n\).

15.2.2. Problem 2#

Generate a Gray code of length n.

Note - for this problem, do not consider values of n greater than 15.

15.3. Assessment#

The main assessment tasks are the following:

  1. Write a generic implementation of the backtracking algorithm

  2. Apply this implementation to solve the two problems above

  3. Provide an explanation, discussion and appraisal of your design approaches

You should provide your work as a Jupyter notebook containing both source code and explanations. The structure of this notebook should be as follows:

  1. Generic backtracking algorithm

    • Explanation of design approach

    • Source code

  2. Integer Partition Problem

    • Brief explanation of how problem can be solved with backtracking

    • Explanation of design approach to coding backtracking operations

    • Source code for backtracking operations

    • Concrete example of using code to solve the problem

  3. Gray code

    • Brief explanation of how problem can be solved with backtracking

    • Explanation of design approach to coding backtracking operations

    • Source code for backtracking operations

    • Concrete example of using code to solve the problem

  4. Conclusions

    • A brief appraisal of your implementation - in particular, a discussion of how reusable it is, and any limitations of it or improvements that could be made

You may use either Python or R for your implementations. It is expected that one should be able to run the whole Jupyter notebook without intervention. If your Jupyter notebook needs any special set-up to run (e.g. the installation of third-party packages), you should explain this at the beginning of your report.

When we ask you to explain your design approach above, we mean the explanation of what data structures and design patterns you used, and any language-specific features you might have used to achieve your aims.

15.4. Assessment Criteria#

Your submission will be assessed according to the following criteria:

  • Quality of source code: readability of your code (documentation, commenting and style conventions), appropriate use design patterns and data structures, appropriate use of language features and idioms in implementation

  • Solution: the correctness of your solutions, and the robustness of your code (e.g. the code runs for different small problem instances without crashing)

  • Understanding of design principles: your explanations and appraisals demonstrate an understanding of design principles like design patterns and appropriate data structures

  • Quality of written communication: the clarity of your explanation and discussion

15.5. Submitting your work#

You should provide your code and solutions in a Jupyter notebook. If necessary, you can provide additional files for data, results, and any additional source code required for your notebook to run.

You should send all of your files as a single file, e.g. a zip file or a compressed tar ball, by e-mail to Kim Wilson by 12pm Monday 17th February.