Introduction
The closing date for this coursework is Thursday 4th December 2003 at 15:00.
However, the secretaries will accept the coursework up until Thursday 11th December 2003 at 15:00. This extra week is to allow for anybody who has problems with their printer, their disc crashing, job interviews, colds, flus, other minor illnesses etc. etc. That is, I am granting an automatic extension for anybody who has problems.
Anybody handing in their work after the 11th December will suffer a 5% reduction of their mark for each day (or part) that their work is late.
Please note, that late work still has to be handed into the secretaries as it has to be logged as being received. I cannot accept work from you.
Any work handed in after 18th December will receive zero marks.
In summary, you should finish the coursework by 4th December. If you can't do that, because of some catastrophe, then I am granting an automatic weeks extension. There will be no further extensions.
DO NOT TREAT THE 11TH DECEMBER AS THE DEADLINE IN CASE YOU HAVE PROBLEMS
This coursework accounts for 25% of the marks for this course.
What you need to submit
- You need to submit your report to the secretaries in B33.
- You need to submit your source code. This will be used to check for plagiarism and may be run to check that it gives the results you claim. The source code will be automatically collected. All you need to do is place the source files in a directory called G5AIAI (in your home user – make sure it is not readable by others) before the 12th December 2002 (it will be collected sometime between then and the 19th December).
Failure to submit either of these will result in zero marks.
Administration
On the course web site is a word document that you should use for your report. This includes a title page and the report structure that you should adhere to.
- Every page should, at least, have your name, your username (for those of you outside of computer science, use the University of Nottingham username that you most often use) and a page number on it. The word file I have supplied on the course web site allows you to put this information into the header of the report.
- When you hand in your assignment, do NOT put it inside a plastic wallet/folder. Stapled, top left, is probably the best idea (rather than a paper clip).
- Do not include any appendices, extra pages, source code listings etc.
- Your assignment must be typed and should be no longer than five A4 sides. The font size used must be 10 or greater. This limit does not include the title page.
Some of the above may sound a bit pedantic but when I have 100 pieces of coursework to mark, small things such as those listed above really do help
Assignment
During the course you will look at various search techniques. This assignment asks you to implement, and comment on, those techniques.
Consider the following (10x10) maze. You need to make your way through it from S (the initial state) to E (the goal state).
- Briefly justify your choice of programming language and discuss your program design and implementation. (3 marks)
Your program design/implementation should follow the structure shown in AIMA (Russell/Norvig) (and in the course notes).
- Using a programming language of your choice, implement a breadth first search algorithm to reach the goal state (E) from the given initial state (S).
- How many nodes were expanded in finding the goal state? (0.5 mark)
- At what level did you find the goal state? (0.5 mark)
- Show the route that was found. (0.5 mark)
- Comment on your results. (3 marks)
- Repeat the search, but this time using Depth First Search and comment on the results (4 marks)
- Repeat the search but use Iterative Deepening (3 marks)
- Repeat the search, using the A* algorithm
- What heuristic(s) did you use? (1 mark)
- Is your heuristic(s) admissible? Justify your answer (0.5 mark)
- Comment on the results (3 marks)