Obligatory Assignment

Please note that an obligatory assignment is an exam, so all rules which apply in an exam situation also apply here.

The deadline is Wednesday, May 16, 2007, 12:00.

This is supposed to be fun! You get to choose your favorite problem to implement. Do not get discouraged by the many rules and regulations below. We know that the great majority of you will automatically comply to these, which mostly describe reasonable conduct. However, ever so often there are a few students who seem to need them.

My favorite problem in computational geometry

The intention is that you should be allowed to choose your own problem. This could be an implementation of one of the algorithms in the textbook or one of the algorithms we have considered in the exercises. The project must be at a reasonable level and have a certain minimum size, so before you start you must consult the lecturer to have your project idea approved.

In your implementation, you are supposed to use the techniques which have been introduced during the course, and your implementation must be of the same asymptotic complexity as the corresponding algorithm in the book, or for algorithms not explicitly analyzed in the textbook must be implemented according to the criteria given by the lecturer when the project idea was approved.

You may also suggest which programming language you want to use. The choice of language must also be approved in advance.

It must be possible to evaluate you project from your report alone. Thus, in addition to the print of the program, you must include a sufficiently detailed description of the problem you solve, an account the asymptotic complexity, and some examples demonstrating that your program works. If you use a programming language where you can use packages, classes, libraries or other code which 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.

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 as well as electronically. Your program must also be capable of outputting the result in text form, e.g., in the form of coordinates for points and lines. Again, you must specify the format and include examples. Finally, your program must also be capable of showing the result graphically. You can choose the method yourself, but it must be printable such that you can include examples in the report. One of the simplest satisfactory ways of doing this is to use LaTeX. There is an example of how this can be done below.

This project is solved in groups. The group size is two, unless another agreement is obtained with the lecturer.

The entire group must see the lecturer at the same time for approval of the project idea, programming language, etc. There is no deadline for doing this, but since you cannot start your project before this time, you ought to get this done several weeks prior to the deadline for handing in the project.

You must document that you have done all that is required, as outlined in the description above, in the form of a report which is handed in at the secretaries' office at IMADA. In addition, your program must be handed in electronically as described below. For programs, the maximum number of characters per line, including spaces, is 79. The report must contain a complete print of your program, and it must be identical to the program which is handed in eletronically.

You are not allowed to receive help from anybody not in your group, and you must ensure that other users cannot read your files. A good method is to create a new directory, DM45project, for your project files. After having issued the command makedir DM45project, issue the command chmod 700 DM45project.

Report and code must be handed in before the deadline. Reports or code handed in after the deadline will generally not be accepted. System and printer failures, illness, etc. will not automatically give you extra time.

The front page of your report must contain the date when you hand it in, and also full name, first 6 digits of your CPR number, IMADA e-mail address, student e-mail address (nn@student.sdu.dk) and signature for each group member.

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. 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.

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 in class or via your IMADA e-mail address. It is your responsibility to check your e-mail regularly. If you do not come in for a necessary meeting before the exam office needs the results, you will not pass.

Handing in Electronically

All the files you want to hand in and nothing other than those files must be in a directory. We assume you have named this directory DM45project. Change to this directory using cd DM45project, and then issue the command aflever DM45. If, in your set-up, this command is not recognized, try the full path by writing /usr/local/bin/aflever DM45. You can hand in as many times as you wish. Each subsequent hand-in overwrites the previous. Thus, only the last counts.

Pictures in LaTeX

See the example LaTeX file, Example.tex, to see how simple geometric figures can be produced. To process such a file, you write latex Example.tex on the command line. This produces a dvi-file, Example.dvi, which can be viewed using xdvi Example.dvi or printed using dvips -Pd3 Example.dvi. The format can be changed to postscript using dvips Example.dvi. This creates a file Example.ps, which can be viewed using gv Example.ps. The format can be changed to pdf using dvipdf Example.dvi. This creates a file Example.pdf, which can be viewed using acroread Example.pdf.

Last modified: Mon Oct 5 18:43:41 CEST 2009
Kim Skak Larsen (kslarsen@imada.sdu.dk)