INF205 programming project

1. Basic functionality

Write a C++ code that solves one of the following basic problems:

  1. Queens on a chessboard: Find a number N, as large as you can, such that N queens can be placed on an m × m chessboard while at most k of the queens are threatened by another figure. It is not allowed to place multiple chess pieces on the same field. Determine at least one of the configurations (positions) with the maximum number of queens, and write it out as a file.
    Benchmark: Do this for m = 7 and k = 3; also measure the computing time. As the basic functionality, it is not required for you to prove that your value of N is the largest possible value (i.e., that it is strictly impossible to do it for N+1 queens); instead, deliver a serious attempt at finding a value of N that is as large as possible.
  2. Packing of spheres: Find a number N, as large as you can, such that N spheres can be placed in an a × a × a box, employing periodic boundary conditions, so that there are at most k overlaps between spheres. If the centres of two spheres are closer than the sum of their radii, it counts as one overlap, but if they are closer than half of that, it counts as eight. (Same as in the example from the lecture.)
    Out of the N spheres, at least 8N/251 spheres must have a sphere diameter σ = 3, at least 27N/251 must have a diameter σ = 2, and the remainder (at most 216N/251 spheres) can have σ = 1. Determine a configuration with the maximum number of spheres, and write it out as a file.
    For this problem, it is acceptable as a basic functionality if you limit yourself to configurations where all coordinates of spheres' centres are multiples of some factor g (don't make this very small; for the beginning, you can even try g = 2).
    Benchmark: Do this for a = 7 and k = 3; also measure the computing time. For g = 2, check values of N at least up to N = 48. As above, here you don't need to prove either that the value of N that you find is the largest possible value.
  3. Problem of special interest, discussed with and approved by the lecturer in advance of 23rd April 2024.

You can work on this individually or as a group of up to five people. This part of the work can be done together.

2. Functionality of special interest

Each student individually needs to take responsibility for at least one programming task that builds on the basic functionality. This applies irrespective whether you work together as a group (then, the individual students take responsibility for different additional features), or whether you do the whole work individually (you still need to implement something in addition to solving the basic problem).

You can select some of the suggestions below, or just as well come up with your own.

  1. Switch to a more interesting variant of the problem.
  2. Local minimization. Finding the global minimum will be complicated as you scale up the system. But you can always at least walk toward a local minimum easily. Beginning with some configuration that is not locally optimal, do small changes that improve your result until it is strictly locally optimal; e.g., move a chess piece to a directly adjacent field, or move single sphere slightly in space, so that your number of threats, overlaps, or energy decreases slightly. Stop when you are at a local minimum so that this is no longer possible. (Here, in case of the molecular simulation, you must drop the restriction of looking at multiples of g only.)
  3. Stochastic sampling. Try to approximate the global optimum (i.e., minimum threat/overlap/energy solution) numerically by stochastically sampling the search space; a recommended technique is the Monte Carlo method, specially the Metropolis algorithm. Look at a problem size that is much larger than the ones for which you can find exact solutions. What is the best result that your program can find within five minutes runtime? (Here, in case of the molecular simulation, you easily can and should drop the restriction of looking at multiples of g only.)
  4. Parallelize your code. Validate that the parallel version of your code is still correct, producing the same results as the original sequential version. Run strong scaling and weak scaling tests on Orion to assess the parallel performance.
  5. Visualize the computation, and show how it proceeds toward its end result. You can use a library or output an input file for another code that does the visualization, and then just run that code. For example, vmd is often used for molecular simulations; LaTeX might be suitable to visualize chessboards.

You can submit a single code base that includes all the functionalities, or multiple versions. (The first one is preferred, as it is easier to understand and evaluate only one program, even if it is more complicated, than multiple programs.)

Group members are allowed to collaborate on these tasks as well and help each other, as long as the responsible person does most of the work.

3. Documentation

In addition to your code, include a PDF file, with maximum two pages on each of the following:

  1. Basic functionality and how to validate it: What is your basic functionality? What commands should be run to check that the code does what it should do?
  2. Data structure and input/output: Brief description and E-R diagram. What objects are containers for other objects or data items? Where do you need to implement copy constructors/assignment operators, etc.? Summarize your I/O functionality briefly.
  3. Numerical results and performance of the code: What are your findings, and how does the code scale in terms of its runtime? Are memory requirements an issue?
  4. Functionality of special interest: At most two pages per task, providing a summary on what you did, what results you obtained, and how the code should be run to reproduce your results.

If you have a group, the whole group should create only one such file.

Submission and remarks

Submit the PDF documentation, your presentation slides in PDF format (if you have any slides, which is not required), and the source code without executables (and without any unnecessarily large files) as one ZIP archive on Canvas by the end of 7th May 2024. If there are any issues with the submission through Canvas, you can also hand it over at the tutorial meeting on 8th May 2024.

If you work in a group, your group can do a single submission - with the individual responsibilities clearly stated as part of the documentation. In this case, every member should still make a submission on Canvas, not necessarily with the whole content, but at least pointing to the person who has uploaded the main content.

The project work also needs to be presented (by at least one of the group members for each group, or individually). However, these presentations are not part of the graded programming work. They are instead part of the (ungraded) mandatory prerequisites for passing INF205. They will be scheduled and announced in due course.

You can use all the examples from the lecture and any other code to which you have the license, as long as you make it transparent.

Criteria for grading

The submission will be graded against the following criteria: Functionality and testability (20%); data structure and memory management (20%); input/output and data serialization (10%); resource efficiency and performance (10%); clarity and style of the code (20%); numerical results (20%).

Index