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 are not allowed to receive help from anybody not in your group,
and you must ensure that other people cannot read your files.
If you are working on your own laptop, you are probably used to handling this.
If you do the work on the IMADA computers,
a good method is to create a new directory, DM819project, for your project
files. After having issued the command makedir DM819project
,
issue the command chmod 700 DM819project
.
There are no retries! You have reached a level where you know what it takes to answer an assignment satisfactorily and on time. Blackboard will not accept assignments turned in late.
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; in particular because your initial project idea might not be approved.
You may work in different groups than you did during part 1 and your overall result will be the combination of the two results you obtained. Thus, even though you and your new partner get the same result on part 2, you and your new partner may get different overall results due to possibly different results in part 1. In conclusion, you will not be punished for working with somebody who got a worse result than you in part 1 (provided of course that the new partner's contribution to part 2 is uncorrelated with the part 1 result).
Here are possible examples of tasks from what we have covered in the first quarter of the course (but talk to the lecturer before you start):
Deadline: Thursday, December 8, 2011, at 23:59.
Input to the program is a list of line segments, S, and a query point, p. The output is a list (without duplicates) of all the line segments from S that are visible from p, as defined in the exercise.
You must use the half-line sweep technique suggested in the exercise and obtain the O(n log n) running time. You must use the design philosophy introduced in Chapter 1 of the textbook. So, for the sweep, you should use an event queue and a status. Furthermore, after the design based on input in so-called "general position", you must consider and handle special cases. Your description of your implementation in your report must include a section on how the geometric tests you use are computed. See the rules below for further requirements.
Deadline: Monday, October 3, 2011, at 23:59.
All parts of the obligatory assignment 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 in class or via one of your e-mail addresses. 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.
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. Again, you must specify the format and include examples. Additionally, your program must be capable of showing the result graphically. You can choose the method yourself, but it must work on IMADA's computers and be printable. One of the simplest satisfactory ways of doing this is to use LaTeX. There is an example of how this can be done below. It is strongly recommended that you implement graphical 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.
Your report must be in the form of a pdf-file named "report.pdf" which includes all the material (report, program listing, tests, etc.) in one pdf-file (talk to the lecturer if this is a problem), and in addition make programs and test data available in text format as well (thus, you turn in program listing and test data both as part of "report.pdf" and in the original text format). The programs etc. in the original text format must of course be identical to the listing in the report (formatting and adding line numbers and headlines is of course fine).
For may zip all of this together in one file that you can upload via Blackboard. You can use zip, bzip2 or tar (with or without gzip).
All file names should be logical and descriptive. Your report should list all file names and explain what they contain.
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 -o
.
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
.