*Conducted in terms:*2020Z, 2021Z

*Erasmus code:*11.3

*ISCED code:*0612

*ECTS credits:*13

*Language:*Polish

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

*Related to study programmes:*

# Introductory programming (imperative approach) 1000-211bWPI

* Notion of an algorithm:

o History of computation

o Basic school algorithms: Euclid, Horner, solving linear and quadratic equations

* Formal languages

o Alphabet, syntax and semantics

o context-free grammars as a tool for defining syntax

o context-free grammars as a tool for defining semantics

* Representation of numbers:

o constants: Reals and Integers

o fixpoint binary representations of positive numbers

o complement-1 and complement-2 representation of negative numbers

o floating-point representation of Real numbers. The notion of a range and the rounding error.

* Constants and epressions:

o type and value of a variable

o arithmetic and logical expressions: syntax and semantics

* Statements of while-programs:

o empty, assignment, conditional, iteration, selection, read, write, procedure call - syntax and formal semantics

o finite and infinite computations

o algorithmic errors

o basic algorithms examples

* Assertions and invariants

o Hoare's logic

o Proving program correctness

o Proving halting of a loop

* Data types:

o arrays

o records

o sets

o files

o enumerate types

o pointer types

* Files:

o random access files

o text files

* Functions and procedures:

o syntax and semantics

o parameters passed by constant, value and variable

o visibility in nested procedures

* Algorithm complexity:

o algorithm costs: time, space, pessimistic, average

o data size

o examples of determining cost of an algorithm

o amortized cost

* Recursion:

o recursive definitions

o application and implementation

o proving corretness of recursive procedures

* Backtracking:

o exhaustive search

o recursion cuts

* Divide and conquer methodc

o incrementational approach to the design of algorithms

o binary splits

* Dynamic data structures

o pointer types

o pointer type representation of linked lists

o basic list operations

o one-directional, bi-directional, cyclic lists

o dummy elements and guardians

* Linear data structures: stacks and queues

o array and list implementation of stacks and queues

o linked list implementation of a graph

o DFS and BFS

* Trees:

o implementation of trees od any of order

o binary trees

o tree traversals: prefix, infix, postfix

o expression conversions; Polish reverse notation

* Greedy algorithms:

o Huffman coding

* Memoization method:

o dynamic programming

o knapsack problems

o multiple matrix multiplication

## Type of course

## Course coordinators

## Learning outcomes

Introduction to Programming is the primary subject of the computer for the first year. We assume that secondary school graduates can not program yet, so we teach programming from scratch.

During the course students learn one language (C) - syntax and semantics.

The syntax of the programming is not the main concern. The primary objective of the course is to develop algorithmic thinking - the ability to recognize the algorithmich problem, analyse it, design an algorithm, and code it, as well as to show the correctness of the solution.

The students will learn how do design well-structured programs, which have low time and memory requirements. Students will learn basic data structures and algorithmic techniques to enable effective programming.

A lot of attention is put to the quality of the code. We would therefore account for its correctness, but also on the proper naming of variables, the aesthetics of text, comments, the use of constants. During the related laboratory workshops students learn programming environment and the basic techniques to run programs. They also are expected to understand and analyse algorithms.

Due to the specific organization of the laboratory tasks we teach students promptness and observing deadlines.

## Bibliography

1. Alagić S., M.Arbib M.A.,The Design of Well Structured and Correct Programs, Springer Verlag (1991)

2. Banachowski L., Kreczmar A., Rytter W., Analysis of Algorithms and Data Structures; Addison-Wesley (1991)

3. Cormen T.H.,Leiserson Ch.E., Rivest R.L., Introduction to algorithms, MIT Press, (2009).

4. Knuth D.E., The Art of Computer Programming vol.3 Addison-Wesley (1973)

5. Wirth N, Systematic Programming: An Introduction; Prentice-Hall series in Automatic Computation (1973)

6. Wirth N., Algorithms + Data Structures = Programs; Prentice-Hall Series in Automatic Computation (1976)

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