Introduction to programming (imperative approach) 1000-211aWPI

1.The history of the notion of algorithm. Algorithms known from high school (Euklid, Horner, solving linear and quadratic equations).
2.The history of the computers.
3.Formal languages: alphabet, syntax and semantics. Context-free grammars, as the tool to define syntax. Definition of semantics as an interpretation of syntactically sound expressions.
4.Integer and real constants. Binary representations of numbers. Fixed-point and floating-point notations. Floating point arithmetic. Floating point error. Overflow and underflow.
5.Variables and expressions. Type of a variable, assignment of values. Arithmetic and Boolean expressions: syntax and semantics.
6.Instructions: empty, assignment, conditional, loop, choice, read, write, procedure call. Syntax and semantics. Finite and infinite computations. Fatal errors.
7.Data types: arrays, records, sets, files, enumerate types.
8.Random access and text files.
9.Functions and procedures. Syntax and semantics. Parameter passing methods: by constant and by variable. Visibility of variables in nested procedures.
10.Partial and total correctness. Elements of Hoare's logic. Loop invariants. Proving corectness of algorithms. Halting problem. The well-founded set method.
11.Cost of the algorithms. Time and memory. Pessimistic and average complexity. Data measuring. Examples of cost computation. Ammortized cost.