AoP /

AoP

During study period 4 (end of March to beginning of June 2008) Patrik Jansson led a 7.5hp (research level) seminar course on "Algebra of Programming" centered around the book by Bird & de Moor. (Undersidor är skyddade av lösenord (driB baklänges) för att undvika spam.)

Course outline

Topic: Algebra of Programming
Examiner: Patrik Jansson
Credits: 7.5hp
First meeting: Wed. 080319, 10.00-12.00 in room EDIT 6128
Meetings: See the Sem 1 notes.
Google group: Join http://groups.google.com/group/aop2008
Literature: The book "Algebra of Programming" and a selection of related research papers
Participants: AoP.Participants - add your name to the list if you intend to follow the course

Content

From the preface of the AoP book:

"Our purpose in this book is to show how to calculate programs. We describe an algebraic approach to programming, suitable both for the derivation of individual programs and for the study of programming principles in general. The programming principles we have in mind are those paradigms and strategies of program construction that form the core of the subject known as Algorithm Design. Examples of such principles include: dynamic programming, greedy algorithms, exhaustive search, and divide and conquer."

This is the TOC from the AoP book: 1. Programs 2. Functions and Categories 3. Applications 4. Relations and Allegories 5. Datatypes in Allegories 6. Recursive Programs 7. Optimization Problems 8. Thinning Algorithms 9. Dynamic Programming 10. Greedy Algorithms

Audience

This is copied verbatim from the preface:

"The book is addressed primarily to the mathematically inclined functional programmer, though the non-functional – but still mathematically inclined – programmer is not excluded. Although we have taken pains to make the book as self-contained as possible, and have provided lots of exercises for self-study, the reader will need some mathematical background to appreciate and master the more abstract material. A first course in functional programming will help quite a lot, since many of the ideas we describe can be found there in more concrete clothing. Prior exposure to the basic ideas of set theory would be a significant bonus, as would some familiarity with relations and equational reasoning in a logical calculus. The bibliographical remarks at the end of each chapter describe where appropriate background material can be found."

Examination

Each student should

A: (10h) do a literature search to identify ten suitable research papers connecting AoP to his or her own research interests. Deliverable: (by week 17) a BibTeX-file with the citations + a memo citing them including a one-paragraph per paper explanation of the connection.
B: (10h) identify one or two (of the above) papers as suitable reads for the whole group. Deliverable: (by week 17) A one-page summary connecting the paper to the AoP theme.
C: (80h) read the book sections and identified "suitable reads" papers. Deliverable: active participation in the seminar discussions.
D: (20h) host one or two of the weekly seminars. Deliverable: a tutorial-style .pdf-slideshow of (some of) the material in the part of the book scheduled for that seminar. Presentation time, 45 min.
E: (70h) perform a case-study or implementation project. Deliverable: (by week 22) a "workshop paper" or well documented source code.
F: (10h) review the case-study / project of one other participant. Deliverable: (by week 23) a one-page review of the strengths and weaknesses of the deliverable E from the other participant.

Schedule and assigment of seminars to participants:

See Sem 1 for details.

Ten seminars:

Week 12: Ch. 1: Programs: Intro + planning meeting
Week 14: Ch. 2: Functions and Categories
Week 15: Ch. 3: Applications
Week 16: Ch. 4: Relations and Allegories
Week 17: Ch. 5: Datatypes in Allegories, (hand in deliverable A and B before this meeting)
Week 19: Ch. 6: Recursive Programs
Week 20: Ch. 7: Optimization Problems
Week 21: Ch. 8: Thinning Algorithms
Week 22: Ch. 9: Dynamic Programming, hand in deliverable E before this meeting
Week 23: Ch. 10: Greedy Algorithms, hand in deliverable F before this meeting

Selected Papers

Selected papers and their relationship to the AoP theme will be listed here.