CSCI 5980/8990 Functional Algorithm Design and Calculation

Course Description

This course covers topics in algorithm design using functional programming. We study different design strategies including divide and conquer, greedy algorithms, dynamic programming, and search. The approach we take to algorithm design has two steps. We will first endeavor to write a precise but perhaps inefficient specification of the algorithm in the form of a functional expression using higher-order functions including maps, filters, and folds over the relevant datatypes. Second, we 'calculate' a more efficient program using equational reasoning to, in essence, fuse the component functions to, for example, replace multiple passes over the data with just one. This work will be done in the Haskell programming language.

Textbook

We will be using the book "Algorithm Design in Haskell" by Richard Bird and Jeremy Gibbons.

Jeremy Gibbons has recently written a SIGPLAN blogpost about this book and the approach it takes to algorithm design. This is the first in a series of three of them and you can find it here.

Prerequisites

Students are expected to have had some non-trivial experience in functional programming. This experience can come from completing CSCI 2041 or CSCI 5106. It can also come from self-study. This course is not appropriate for those without functional programming experience. Feel free to email me at evw@umn.edu if you have questions about your preparedness for this course.

Students that have completed CSCI 2041 should have an appreciation for the material in that course on reasoning / proving properties about functions. Some similar techniques will be used in this course.

Logistics

Class time: Monday and Wednesday, 9:45am - 11:00am.

The course will be available online in a synchronized manner. We will use class time to discuss material and problems from the textbook. For these reasons, the course is not offered in an asynchronous form. The class may also be offered in an optional in-person manner if that is feasible. If this does work, we will meet in Keller Hall in room 3-230. This will give us ample room to spread out. Student wishing to participate remotely are encouraged to do so - there is no requirement that one attend in person.

Registering for 5980 or 8980

This course is offered at both the 5000-level and the 8000-level. If you are an undergraduate student then you should take the 5980 version of the course.

The 8980 version of the course is for graduate students. This version will have additional requirements. One of these will be the completion of an independent project with a presentation of it to the rest of the class.

Getting a permission number to register

If you are interested in registering for this course, please email me at evw@umn.edu to request a permission number. Please indicate how you fulfill the prerequisites and if you are anticipating registering for 5980 or 8980.

Please also note that there a limited number of seats in the course.

My perspective on data structures and algorithms

This is meant to be taken with a grain of salt, but only with a small grain...