[DLS]Algorithm Design with Functional Programming (Delivered in English)
- LecturerProf. Jeremy Gibbons (Department of Computer Science, University of Oxford, England)
Host: Hsiang-Shang Ko - Time2023-08-17 (Thu.) 10:00 ~ 12:00
- LocationAuditorium106 at IIS new Building(actual);Live Streaming is availible
Live Stream
- Meeting Link：
- https://asmeet.webex.com/asmeet/j.php?MTID=ma3081776130851e5db39162450100f1b
- Meeting Code：
- 2514 128 7597
- Password：
- p8EMiCabz28
Abstract
Algorithm design is a core topic in computer science. It is traditionally taught using two distinct formalisms: some form of mathematics for the "algorithms", and some programming language for their "implementations". I will show that only one formalism is needed: the right choice of programming language - specifically, a functional programming language - can also serve as the mathematical notation. This simplification removes some sources of confusion and vagueness.
The talk is based on the book "Algorithm Design with Haskell" by Richard Bird and Jeremy Gibbons (CUP, 2020). The book is devoted to five main principles of algorithm design: divide and conquer, greedy algorithms, thinning, dynamic programming, and exhaustive search. These principles are presented using Haskell, leading to simpler explanations and shorter programs than would be obtained with imperative languages. Carefully selected examples, both new and standard, reveal the commonalities and highlight the differences between algorithms. The algorithm developments use equational reasoning where applicable, clarifying the applicability conditions and correctness arguments. I will describe the premise of the book, including in particular the small aspect in which Haskell is insufficient, and present an example.
The talk is based on the book "Algorithm Design with Haskell" by Richard Bird and Jeremy Gibbons (CUP, 2020). The book is devoted to five main principles of algorithm design: divide and conquer, greedy algorithms, thinning, dynamic programming, and exhaustive search. These principles are presented using Haskell, leading to simpler explanations and shorter programs than would be obtained with imperative languages. Carefully selected examples, both new and standard, reveal the commonalities and highlight the differences between algorithms. The algorithm developments use equational reasoning where applicable, clarifying the applicability conditions and correctness arguments. I will describe the premise of the book, including in particular the small aspect in which Haskell is insufficient, and present an example.
BIO
Jeremy Gibbons is Professor of Computing at the University of Oxford, where he leads the Algebra of Programming research group, and is Director of the part-time professional postgraduate master’s programme in Software Engineering. His research interests are in programming languages, especially functional programming and patterns in programming. He is Editor-in-Chief of the The Art, Science, and Engineering of Programming (and was until recently Editor-in-Chief of the Journal of Functional Programming), and a member of IFIP Working Group 2.1 on Algorithmic Languages and Calculi, and of IFIP Working Group 2.11 on Program Generation.