Algorithmic Problem Solving
News
Watch this space for announcements.
- 10/12/12. Coursework 5, deadline extension. I will present solutions to coursework 5 in tomorrow's lecture. Solutions that are handed in before the lecture will be marked.
- 10/12/12. Revision handout now available. See lecture schedule below for copies of revision handout (also handed out in today's lecture).
- 15/11/12. Change in schedule. Because I had to miss the lectures at the beginning of this week, I have revised the schedule. In particular, the hand-in deadline for coursework 4 has been put back. See below for details. My apologies for any inconvenience.
- 05/11/12. Tuesday lectures moved to LT3. Effective immediately. Following complaints about C33, the University's Timetabling section has agreed to move the Tuesday 9am lecture to LT3 in the Exchange Building. This change will take place immediately. The lecture on Tuesday 6th November was originally cancelled but I will now use this opportunity to repeat the Monday 5 November feedback lecture.
- 22/10/12. Catch-up Tutorials. There will be an extra catch-up tutorial for anyone who with good cause is unable to attend a particular tutorial. The catch-up tutorials will take place in alternating weeks, in the week following the regular tutorial, on Tuesday at 11am in C81a, Computer Science Building. (For example, if you are ill in the week beginning 29th October, you may book to attend the catch-up tutorial on 6th November.) This is a very small room so please contact Khin in advance before attending; otherwise you may be turned away. The first catch-up tutorial will take place tomorrow (23/10/12).
- 22/10/12 The move of Monday tutorials to Thursday is now confirmed. NB. As last week, the Monday, 9.00-10.00 tutorial will now take place on Thursdays from 09.00-10.00 in C60 (CS building); the Monday 14.00:15.00 tutorial will now take place on Thursday from 15.00:16.00 in JC-BSSOUTH-A07 (Business School South, room A07).
- 16/10/12 The tutorials WILL go ahead this week. Students allocated to the 9am, Thursday tutorial in the Dearing building should go to C60 instead. Apologies for the inconvenience.
- 16/10/12 Skeletons for lecture on 16th October added.
- 11/10/12 Monday tutorials to move to Thursday. Because those with tutorials scheduled for Monday will always be two lectures behind, I have arranged for them to move to Thursdays. The Monday, 9.00-10.00 tutorial will move to Thursday, 09.00-10.00 in C60, CS building. The Monday 14.00:15.00 tutorial will move to Thursday 15.00:16.00, C60, CS building. In case anyone does not receive this information on time, the tutorials on Monday 15th October will go ahead as scheduled but will also be repeated on Thursday 18th October. If anyone is inconvenienced by the change of time, please contact Khin Lwin to arrange a switch.
- 09/10/12 Summary of yesterday's lecture added here.
- 27/09/12 Website is being updated ready for the new academic year. Information may be out of date!
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 2012, Semester 1
- Method and frequency of class: Two lectures per week:
- Monday, 16:00-17:00 in JC-EXCHGE-C.C33+
- Tuesday, 09:00-10:00 in JC-EXCHGE-LT3+
- Method of assessment: Unseen 2 hour 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. It is also available in the University bookshop. |
The following texts provide supplementary reading.
- How to Solve It, George Polya. 2nd ed., Princeton University Press, 1957, ISBN 0-691-08097-6.
- Algorithmic Puzzles, Anany Levitin, Maria Levitin, Oxford University Press, 2012.
- 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 | 1st October | Administrative Details and Introduction | Introduction | |
| 2 | 2nd October | Invariants | Invariants | |
| 3 | 8th October | Invariants (cont.) | Boxes Problem -- Summary | |
| 4 | 9th October | Crossing a River. | Nervous Presidents | Problem Decomposition |
| 5 | 15th October | Brute Force Search | Brute-force Search | 3x2 Nervous Presidents, State Transition Diagram |
| 6 | 16th October | Sets, Permutations and Combinations | Sets, Permutations and Combinations | |
| 7 | 22nd October | Solutions Feedback on coursework 1. | ||
| 8 | 23rd October | Logic Puzzles | Logic Puzzles | |
| 9 | 29th October | Logic Puzzles (Cont.) | ||
| 10 | 30th October | Logic Puzzles (Cont.) | ||
| 11 | 5th November | Solutions Feedback on Coursework 2 | ||
| 12 | 6th November | Repeat of lecture on 5th November. New location: LT3. | ||
| 13 | 12th November | Lecture cancelled because of illness | ||
| 14 | 13th November | Lecture cancelled because of illness | ||
| 15 | 19th November | Games | Games | |
| 16 | 20th November | Games (cont.) | Game Sum | |
| 17 | 26th November | Games (Cont.) | ||
| 18 | 27th November | Induction | Induction | Tower of Hanoi |
| 19 | 3rd December | Tower of Hanoi | ||
| 20 | 4th December | Solutions Feedback on coursework 3 | Solutions Feedback on coursework 4. | |
| 21 | 10th December | Revision | Revision | |
| 22 | 11th December | Solutions Feedback on coursework 5. | Revision. State-Space Explosion. | |
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. (Non-)completion of coursework will be monitored and reported.
Coursework can be downloaded by clicking on the links below. The dates shown are the deadlines for submission. Model solutions will not be made available electronically but will be distributed in hard-copy form in lectures and tutorials.
-
12 October 2012 Coursework 1 (Invariants). -
26 October 2012 Coursework 2 (River Crossing). -
9 November 2012 Coursework 3 (Logic Puzzles). -
30 November 2012 Coursework 4 (Games). -
14 December 2012 Coursework 5 (Induction).
Tutorials
Tutorials for this module are being coordinated by Khin Lwin (psxktl at nottingham.ac.uk).
There are five tutorial groups, each at a different time in the week. Each student is assigned to one group. See the tutorial groups to determine which group you are in. If you have been allocated to a tutorial group that you cannot attend because of timetable clashes, you are welcome to change to another group.
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 recent 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.