functional programming
This was an interesting course because almost everyone who had programmed at school had programmed imperatively, and almost no one functionally. It was therefore a good first programming course, because everyone was equally confused.
In Haskell, you write everything as functions, and nothing has state — so if two expressions are equal, you can always swap one for the other. That makes a program something you can do algebra on: rather than writing one and then checking it does the right thing, you start from a specification and derive the program that satisfies it. The course introduces type theory and structural induction, but a large chunk is dedicated to generalising recursion to something called a fold (also known as reduce or inject in other languages). While tricky, I thoroughly enjoyed this course.
syllabus
Programming by writing functions: expressions, values, types, evaluation. Function definitions in Haskell scripts, interactive sessions. Mathematical functions as programs, function application as program execution; lists for sequencing, and function composition as a program structuring tool.
Strong typing. Basic types, constructed types (sums and products); constructors, selectors, and discriminators; definitions by pattern matching. Parametric polymorphism, type classes and ad-hoc polymorphism; recursive types. Lists, finite and infinite lists; list comprehensions, standard list functions including map, filter, concat.
Evaluation as computation, evaluation order; recursive definitions, non-termination and an outline of the idea of computability. Sorting as an example; the concept of efficiency of evaluation, and the asymptotic complexity of a calculation.
Sudoku solver as an example; the idea of infeasibly inefficient algorithms.
Proofs by induction. The take lemma, induction on finite lists, induction on infinite lists. The notion of chain completeness.
Folds on data structures. Left- and right-folds on lists. Fold fusion. Standard functions as instances of folds. Scans as folds. Unfolds. Writing programs by solving equations for unknown functions.
Efficiency improvement techniques involving accumulating parameters. Associativity and the relationship between left- and right-folds. Log time exponentiation.
Countdown as an example. Abstract syntax trees. Tabulation and dynamic programming.
Parsers as an example. The idea of parser combinators, as an introduction to monads. The do notation.