Exam Project Format

The exam project will be given in parts. The first will cover important techniques that all students should gain experience implementing. A later part will be more individual.

You may do the work yourself or work in pairs, i.e., work is done in groups of 1-2 students. If you would like to work with another student, you just arrange it yourself. There is no official recommendation as to whether or not you choose to work with another student. The implementation work should not be overwhelming for students at your level, so it mostly boils down to whether you find it helpful to discuss issues with a fellow student or if you just find it time-consuming to have to coordinate and meet at specific times that may not fit well into your schedule. You can work in different groups for the different parts if you want.

You are not allowed to receive help from anybody not in your group, and you must ensure that other people cannot read your files.

All parts of the exam project deal with implementing algorithms from the area of computational geometry. For each part, you must turn in a report and an implementation before the deadline for the given part.

After you have handed in your project, you may with no or very short notice be called in for a brief examination or be asked to demonstrate your program. If this becomes necessary, you will be notified. It is your responsibility to check your e-mail regularly.

Implementation Requirements

In your implementations, you are supposed to use the techniques that have been introduced during the course. When implementing algorithms analyzed in the textbook, your implementation must be of the same asymptotic complexity as the corresponding algorithm in the book. There may be additional requirements stated under the specific parts of the exam project or individual requirements (typically for later project parts).

There is one exception to the requirement that all algorithms must be implemented as efficiently as stated in the textbook. If you implement your own search tree as part of your solution, it is not a requirement that you implement a balancing scheme (such as red-black trees, for instance), i.e., it is sufficient to implement only a basic search tree.^[1]

Your program must be capable of reading all its input from a text file, and you must specify the format and include examples in the report and in test files. Your program must also be capable of outputting the result in text form, e.g., in the form of coordinates for points and lines. The purpose of this is to be able to read exactly what the output is, which will often not be possible from a graphical illustration. Again, you must specify the format and include examples. Note, however, that the lecturer has made some format decisions for you for the purpose of testing.

Additionally, your program must be capable of showing results graphically. You can choose the method yourself, but it must work on IMADA's computers and be printable and readable; screenshots is of course a possibility. One of the simplest satisfactory ways of producing the graphical part is to use LaTeX. There is an example of how this can be done below. This is not very impressive graphically, but it is simple and allows you to spend your time on the algorithmic issues instead of on GUIs, packages, etc. You may use color to distinguish different elements in your graphical output, but check that it works. You can also use different types of lines (solid, fat, dashed, etc.) or markings to indicate your results. It is strongly recommended that you implement graphical viewing/printing early in the process, since it makes debugging so much faster. Clearly, you should also describe how your program should be run.

Solutions in the form of programs, data for viewers, etc. must work on IMADA's computers with the compilers and other applications present on IMADA's computers, so that we can test your solution. You are free to develop your solution at home, but it is your own responsibility to transfer your solution to IMADA's system and make the necessary adjustments such that it works at IMADA. You can indicate in your report which IMADA machine you have run your code on to remove any doubt at a later point in time. If you would like to use facilities not available on the IMADA computers, talk to your lecturer as early as possible, and we will see if a solution can be found.

Corona complication: Since you cannot go to IMADA to check, use ssh into an IMADA computer in the computer lab. What you can do and how you do it depends on your set-up and OS, of course, but you need something like

ssh -Y logon.sdu.dk

to get into SDU, followed by

ssh -Y imada-106319.imada.sdu.dk

to get onto a computer with a reasonable selection of software. The last two digits can be changed to get onto another computer, in case one is down. Transfering graphics like this is really slow, so you only want to do this to test your concept and for verifying at the end.

Data Formats and Execution Requirements

For input data, represent a line going from (x1,y1) to (x2,y2) by

x1 y1 x2 y2

terminated by one newline. Positive and negative integer coordinates should be allowed with no unusual restriction on size; you decide if floats are also allowed. Before x1, in between two coordinates, and after y2 (but before the newline), any number of spaces or tabs are allowed.

If (in Part 2) you need to represent other entities, define similar formats.

There should not be any special markers to denote the end of input other than the end-of-file, and no unnecessary separators between input lines.

A point is represented similarly using two numbers instead of four.

For output, there is exactly one space between coordinates and no starting og ending whitespace other than the newline.

For graphical output, you mostly decide. However, the dimensions should be decided by the input. Thus, the coordinates you can visualize graphically should not be restricted to a pre-defined domain, but rather be adjusted to what is needed to show the result. This is because using a pre-defined domain would mean that there are things that do not show up, when we are testing, because it is outside the domain, or, alternatively, that everything is drawn more or less in one little point, because the domain is much larger than the values used in a given test.

Programming Language

The preapproved programming languages you can choose from are the following:

• C
• Java
• Python

If you have other preferences, you could likely obtain permission to use an alternative. Contact the lecturer. You should do this early; in particular if your preferred language is not available, since IT-service does not necessarily install from day to day.

Libraries

Many programming languages come with libraries. If you use a programming language where you can use packages, classes, libraries or other code that has been supplied by the programming language developers, you have to know how the facilities included in these modules are implemented such that you can account for the asymptotic complexity.

Furthermore, you should of course not use libraries that solve or partially solve the problem, you're supposed to implement, should you find such libraries.

Advice on Graphics

LaTeX is an easy option, since you are likely writing your report that way already. See the example LaTeX file, tikzExample.tex, to see how simple geometric figures can be produced. To process such a file, you write pdflatex tikzExample.tex on the command line. This produces a file tikzExample.pdf, which can be viewed using evince Example.pdf or acroread Example.pdf, or using some other pdf viewer.

There are of course lots of other options, including PyX, which could be a good choice if you code your solution in Python. If it is not installed, you can do it yourself with pip3 install pyx (for python3). The package matplotlib is also a possibility.

Overall Report Content

You must document that you have done all that is required, as outlined in the exam project description and the rules, in the form of a report. It must be possible to evaluate your project from your report alone. You must include a sufficiently detailed description of the problem you solve, an account for the geometric special cases, an account for the geometric calculations used in the implementation, an account for the asymptotic complexity, a convincing test suite demonstrating that your program works (also in special cases), and any additional requirements from the part description must be handled.

Manual

Your report must have a section called "Manual". Here you must describe the exact textual input and output format. You must also explain how to compile and run your code on IMADA's computers. Be careful not to hardwire references to you home directory etc. into the code such that it will not be possible for us to compile or run your program directly. You must also explain how to view and print your graphical output. Your goal should be to make it as easy as possible for the lecturer to run your program on additional tests to the ones you have provided. You have to make everything really clear, e.g., which directory one should be in, the order in which commands should be carried out, etc. You are adviced to make things as simple as possible. The safest is usually to have all source files and executables in one directory. Of course, your report and test files can be in other directories.

Turning In

You turn in using "itslearning". Organize a directory containing the report (as a pdf file) and all source files and test files. All file names should be logical and descriptive. Your report should list all file names and explain (briefly) what they contain. You may zip all of this together in one file that you can upload. You can use zip, bzip2 or tar (with or without gzip). Do not turn in files that are not used in your final solution. Also, please remove hidden directories (filenames starting with a period) created by git or various mac software before you zip.

---

1. ^ See, for instance, Chapter 12 of Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms (third ed.). MIT Press, 2009. ISBN 978-0-262-03384-8.

 

---