Introduction to programming (functional approach) 1000-211bWPF

It is a basic introductory course to computer science. The focus is on programming and elements of algorithms construction.
Sylabus:
1) Introduction:
- the history and the notion of algorithm,
- examples of algorithms and programming languages in the real life,
- the notion of the algorithmic domain.
2) Elements of the programming language:
- BNF -- meta-notation for the definition of the programming
language syntax,
- syntax and evaluation of expressions,
- logical values and conditional expressions if-then-else,
- procedure definitions, lambda-abstraction, recursive procedures,
tail recursion,
- local definitions.
3) Problem decomposition and program verification:
- problem specification, initial and terminal conditions,
- partial correctness and the stop property,
- program verification,
- examples.
4) Data structures:
- built-in types,
- constructors and patterns,
- Cartesian products,
- lists,
- type declarations,
- records,
- algebraic data-types (trees),
- exceptions.
5) Building abstractions using data structures:
- constructors, selectors and modifiers,
- abstraction levels and barriers,
- examples.
6) Higher-level procedures:
- procedural types and polymorphisms,
- examples,
- higher-level procedures and lists,
- applications of higher-level procedures.
7) Operational semantics of functional programs (simplified):
- frames and environments,
- semantics of global definitions,
- representation of data-structures and procedures,
- procedure application,
- tail-recursion,
- semantics of local definitions,
- garbage collection.
8) Complexity analysis:
- calculus of orders of magnitude,
- memory and running time costs,
- amortized cost.
- examples.
9) The "divide and conquer" method:
- the "divide and conquer" method,
- examples,
10) Quick-sort -- example of the expected running-time analysis.
11) Examples of amortized cost analysis.
12) Modules:
- structures,
- signatures,
- merging structures and signatures,
- how to divide a program into modules.
13) Functors,
- simple functors,
- higher-order functors,
- examples.
14) Imperative programming:
- references,
- sequential composition of instructions,
- loops,
- arrays,
- examples
- functional programming vs. imperative.
15) Imperative pointer data-structures
- examples.
16) Imperative programs verification -- Hoare's logic.
- while-programs,
- Hoare's logic,
- loop invariants,
- measures and the stop property,
- examples.
17) Back-tracking:
- back-tracking,
- pruning and other improvements,
- examples.
18) Memorization:
- memorization technique,
- general memorizer,
- examples.
19) Dynamic programming:
- examples.
20) Greedy programming:
- Huffman's codes,
- other examples.

Some more advanced topics (to be chosen):

21) Pattern matching and the KMP algorithm,
- naive algorithm,
- Rabin-Karp's algorithm,
- the KMP algorithm.
22) Suffix array:
- algorithm computing the suffix array,
- the LCP array,
- examples.
23) Much higher-order procedures:
- definition of data types using procedures,
- Church's natural numbers,
- fix-point operator and recursive definitions.
24) Streams.