G51APS - Algorithmic Problem Solving – University of Nottingham

Algorithmic Problem Solving

News

11/01/10: local copies of past exams are now available
14/12/09: the lecture notes of lecture 17 are now available
07/12/09: the lecture notes of lecture 18 are now available
27/11/09: the appendix that will be distributed with the exam is now available
27/11/09: the lecture notes of lecture 16 are now available
25/11/09: the skeleton of lecture 16 is now available
21/11/09: the skeleton of lecture 15 is now available

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: Joao Ferreira
Module Code: G51APS
Duration: Autumn 2009, Semester 1
Method and frequency of class: Two lectures per week:
- Monday, 14:00-15:00 in JC-EXCHGE-C.LT2+
- Friday, 14:00-15:00 in JC-EXCHGE-C.LT2+
Method of assessment: Coursework (25%) and an unseen 90-minute examination (75%)

Forum

The CS School provides a forum where you can ask questions. If you want to access it, please follow the following link:

APS Forum

Literature

The Art and Craft of Problem Solving, Paul Zeitz, John Wiley and Sons, Inc. , 1999.
Program Construction. Calculating Implementations from Specifications, Roland Backhouse, John Wiley and Sons, Inc., 2003.
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

Exercises

The problems we will be discussing are divided into groups. You will be asked to first tackle the problems on your own. Later the solution technique will be discussed in the lectures. In this way, you will have some familiarity with the problems before they are discussed in lectures, and will be in a better position to understand their solutions.

Invariants (pdf)
River Crossing Problems (pdf)
Matchstick Games (pdf)
Logic Puzzles (pdf)
Induction (pdf)

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	25th September	Administrative Details and Introduction	01-Introduction
2	28th September	Invariants	02-Invariants
3	2nd October	Invariants (cont.)	03-Invariants
4	5th October	Crossing a River	04-CrossingRiver
5	9th October	Crossing a River (cont.)	05-CrossingRiver
6	12th October	Crossing a River / Games	06-CrossingGames
7	16th October	Games (cont.)	07-Games
8	23rd October	Games (cont.)	08-Games
9	26th October	Logic Puzzles	09-LogicPuzzles
10	2nd November	Logic Puzzles (cont.)	10-LogicPuzzles
11	9th November	Coursework Discussion	Solutions are not available.
12	13th November	Logic Puzzles (cont.)	12-LogicPuzzles
13	16th November	Logic Puzzles (cont.)	13-LogicPuzzles
14	20th November	Induction	14-Induction
15	23rd November	Induction (cont.)	15-Induction
16	27th November	Fake-coin detection	16-17-FakeCoin
17	30th November	Fake-coin detection (cont.)	16-17-FakeCoin
18	7th December	Revision	18-Revisions
19	11th December	Coursework Discussion	Solutions are not available.

There will be no lecture on the following dates: 19th October, 30th October, 6th November, and 4th December.

Lecture Notes

2009/2010: (ps) (pdf). A printed copy can be purchased from the School Office.

Restricted Material: There is some content that is password protected, due to copyright reasons. You can access it if you are trying to access it from machines on campus.

Appendix with laws discussed in the lectures: ExamAppendix.pdf
This appendix will be distributed with the exam and it contains a summary of the mathematical laws discussed in the APS lectures and tutorials. Please note that this summary is for your convenience only and it does NOT necessarily cover all the laws you have to know.

Coursework

Coursework 1 (10%). Deadline: 30th October, 3pm
Coursework 2 (15%). Deadline: 7th December, 12pm

Tutorials

Tutorials for this module will take place in the week starting on the 23rd October. At other times, you can get help by contacting the module convenor. Please send an email before approaching him.

Each student is assigned to a tutorial group. See the tutorial groups to determine to which group you have to attend to. If you cannot attend the tutorial group you are assigned to, then you'll have to send me an email before the 23rd of October with the reason why you can't attend.

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 come to see me immediately after the lecture or in my office (room B39).

If you do have difficulty getting hold of me, send an email suggesting a time and day that you would like to come and see me. (But please keep email traffic to a minimum.)