*This course is not currently conducted!*

*Erasmus code:*11.3

*ECTS credits:*unknown

*Language:*Polish

*Organized by:*Faculty of Mathematics, Informatics, and Mechanics

*Related to study programmes:*

# 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.

## Type of course

## Bibliography

1. H. Abelson, G. J. Sussman, Struktura i interpretacja programów komputerowych, WNT 2002.

2. L. Banachowski, A. Kreczmar, Elementy analizy algorytmów, WNT 1987.

3. A. Hunt, D. Thomas, Pragmatyczny programista, WNT 2009

4. M. Kubica, Wstęp do programowania i Metody programowania, notatki do wykładów,

5. X. Leroy, The Objective Caml system, .

6. N. Wirth, Algorytmy+Struktury danych=Programy, WNT 2001.

## Additional information

Information on *level* of this course, *year of study* and semester when the course
unit is delivered, types and amount of *class hours* - can be found in course structure
diagrams of apropriate study programmes. This course is related to
the following study programmes:

Additional information (*registration* calendar, class conductors,
*localization and schedules* of classes), might be available in the USOSweb system: