Algorithmic Problem Solving
News
Watch this space for announcements.
- 30/11/11Skeletons for lecture on 30th November added.
- 29/11/11Deadline for 2nd coursework revised.
- 05/10/11Coursework 1 is now available. See below.
- 03/10/11Tutorials are shared with G51MCS. You should attend one tutorial per week. See the section on Coursework and Tutorials at http://www.cs.nott.ac.uk/~vxc/g51mcs/g51mcs.html for the division of students into groups. The course tutors are Neil Sculthorpe (email: nas at cs.nott.ac.uk) and Laurence Day (psxld at nottingham.ac.uk). They will explain how the division between aps and mcs will work out.
- 01/10/10: Coursework 1 available. See below.
Course Information
This module is about how to solve problems that involve the construction of an algorithm. Many problems are of this nature, so the scope is very broad. The module is structured around the basic principles of algorithm design (invariants, problem decomposition, etc.) with each principle being introduced via well-chosen problems. Appropriate mathematical skills are introduced in the same problem-driven way.
- Convenor: Roland Backhouse
- Module Code: G51APS
- Duration: Autumn 2011, Semester 1
- Method and frequency of class: Two lectures per week:
- Monday, 11:00-12:00 in JC-EXCHGE-C.C33+
- Wednesday, 09:00-10:00 in JC-EXCHGE-C.LT2+
- Method of assessment: Unseen 120-minute examination (100%)
Forum
The CS School provides a forum where you can ask questions. If you want to access it, please follow the following link:Literature
|
|
|
The book Algorithmic Problem Solving is available from the publisher John Wiley and amazon. |
The following texts provide supplementary reading.
- How to Solve It, George Polya. 2nd ed., Princeton University Press, 1957, ISBN 0-691-08097-6.
- Puzzle-Based Learning. An Introduction to Critical Thinking, Mathematics, and Problem Solving, Zbigniew Michalewicz and Matthew Michalewicz, Hybrid Publishers, 2008
- The Art and Craft of Problem Solving, Paul Zeitz, John Wiley and Sons, Inc. , 1999.
Lectures
The lecture overview below is tentative. On some topics we may progress slower or faster than scheduled. If so, any references to lecture numbers will always refer to the content listed below, regardless of the date the lecture took place. Also, some topics may change slightly, especially towards the end.
The dynamic nature of problem solving cannot be properly conveyed in a static text. The lectures are an important, integral part of this module. Come to them prepared to take notes and to participate actively. Skeletons of the lectures are available in the table below.Remember to bring printed copies of these to every lecture.
| Lecture | Date | Content | Skeleton | ||
| 1 | 3rd October | Administrative Details and Introduction | Introduction | ||
| 2 | 5th October | Invariants | Invariants | ||
| 3 | 10th October | Invariants (cont.) | Summary | ||
| 4 | 12th October | Logic Puzzles | LogicPuzzles | ||
| 5 | 17th October | Logic Puzzles (cont.) | |||
| 6 | 19th October | A chessboard problem. | |||
| 7 | 24th October | Crossing a River. Coin Problem | Nervous Presidents | Coin Problem | |
| 8 | 26th October | Help with coursework | |||
| 9 | 31st October | Brute Force Search | Problem Decomposition | Brute-force Search | |
| 10 | 2nd November | Games | Games | ||
| 11 | 7th November | Games | Game Sum | Mex Numbers Summary | |
| 12 | 9th November | Feedback on Coursework 1 | |||
| 13 | 14th November | Feedback on Coursework 1 | |||
| 14 | 16th November | No lecture | |||
| 15 | 21st November | Games (cont.) | Games: Summary | ||
| 16 | 23rd November | Tower of Hanoi | Tower of Hanoi | ||
| 17 | 28th November | Induction | Induction | ||
| 18 | 30th November | Bridge Problem | Tower of Hanoi and Bridge Problem | ||
| 18 | 5th December | Revision | |||
| 18 | 7th December | Revision | Revision | ||
| 19 | 12th December | Coursework feedback. | Model Solutions | Supplement | |
| 19 | 14th December | Revision | |||
Lecture Notes
The primary source of additional reading is the book Algorithmic Problem Solving. It is possible that additional material may be placed here.
Coursework
Coursework is non-assessed but will be marked for feedback purposes. Examination questions will be substantially, but not exclusively, based on the coursework. On account of the tight feedback-deadlines, coursework handed in late will not be marked.- Coursework 1 Model Solutions , Qu. 3. RCB's Solution, Mingyan Yang's Solution (Ningbo, China), Radu Tuica's Solution (Nottingham, UK)
- Coursework 2 Deadline: 2nd December, 3pm (Questions 1 and 2), 9th December (Question 3).
Tutorials
Tutorials for this module are being coordinated by Dr Neil Sculthorpe. They are shared with tutorials for G51MCS. See the section on Coursework and Tutorials at http://www.cs.nott.ac.uk/~vxc/g51mcs/g51mcs.html for the division of students into groups. (The division is by student ID so still applies even if you are not doing G51MCS.) The course tutors are Neil Sculthorpe (email: nas at cs.nott.ac.uk) and Laurence Day (led at cs.nott.ac.uk). They will explain how the division between aps and mcs will work out.
Model Solutions to Past Examination Papers
Past examination papers can be found here (access restricted to Nottingham University students).
Local copies and model solutions to these papers can be found below.
Getting Help
If you have any questions on the course, please arrange to see one of the tutorial assistants or see the module convenor immediately after the lecture or in his office (room B30).
If you do have difficulty getting hold of someone, send an email to rcb at cs.nott.ac.uk suggesting a time and day that you would like to come. Make sure your email includes your name and states that it is about G51APS and is sent from a University email account. (Emails from non-university accounts may be spammed.) Please keep email traffic to a minimum.