![[topimage]](IMADA_en.png)
Exam Project Format
The exam project will be given in parts. The first will cover important techniques that all students should gain experience implementing. In a later part, you will be allowed to make a more individual choice.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.
You are not allowed to use generative AI.
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 Virtual Computer Lab or only require very simple installation (more on this below). 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.
I understand that you of course want to develop on your own laptop/computer, and the requirement above is not to bother you with having to use another environment. On the other hand, I have to be able to test your programs. If you use relatively new, stable versions of a programming language, standard libraries or packages, and don't do funny stuff (such as using conda for Python) or going out of your way to use extremely new versions before everyone else, then everything is probably fine. If you would like to use features not available on our platform, or any unusual facilities, then talk to me as early as possible, and we will see if a solution can be found.
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),
you should allow any number of spaces or tabs.
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 should be exactly one space between coordinates and no starting or 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 / C++
- Java
- Python
If your program needs to be compiled, it should preferable be simple, e.g., just calling the compiler with your source code as argument. If something more complicated is necessary, you could write a script for that, but keep it simple and explain carefully why and what. The user does not feel like executing magical enchantments in his or her own file system without a careful explanation of what all programs and options do and mean.
Libraries
Many programming languages come with libraries, packages, etc. If you use a programming language where you can use packages, classes, libraries, or other code that has been supplied by the developers and not written by you, 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.
Of course, it is preferably if your program generates the pdf file, so
it is ready to be viewed, but at the very least, generate a complete
LaTeX file and not just some LaTeX code that should be inserted into
a LaTeX template to be pdflatexable.
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 Virtual Computer Lab or explain a very simple installation procedure working on all operating systems platforms if extra packages or something else is required. Be careful not to hardwire references to your 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.- ^ See, for instance, Chapter 12 of Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms (4th edition). MIT Press, 2022 [the 3rd edition from 2009 is also fine].