Introductory programming

obligatory courses

Basic introductory course in the field of computer science. It presents concepts of algorithms and programs, principles of writing, designing and verification of computer programs, including considerations about the algorithms complexity.

The course also covers programming techniques and data structures used in small and medium-scale programming.

The concept of algorithm:

- The history of the algorithm concept,

- Examples of algorithms (e.g. Euclid's, Archimedes', Horner's, solving linear and quadratic equations),

- The notion of the algorithmic domain

Fundamentals of programming language:

- Notation for describing the syntax of the language (e.g., context-free grammars, or BNF),

- The concepts of syntax and semantics,

- Algorithmic domain:

* arithmetic expressions (integer and floating-point numbers),

* logical expressions,

* characters and strings,

- Variables and their types, assignment statements.

- Defining (non-recursive) functions:

* parameters,

* return value and void type,

* function call,

* local variables.

- Conditional statements,

- While loop,

- For loop,

- Case statement,

- Characters and strings,

- Input and output,

- Empty statement,

- Integer numbers representation,

- Floating-point numbers representation, notions of range and precision.

Decomposition of problems and program verification:

- Problem specification, initial and final conditions,

- Partial correctness and termination property,

- Assertions,

- Hoare's formulae,

- Loop invariants,

- Termination property and how to prove it,

- Reasoning about program correctness,

- Examples of problem decomposition and program verification.

Data types:

- Arrays,

- Structures,

- Unions,

- Type declarations,

- Type compatibility rules.

Files:

- Storage memory,

- Text files,

- Buffering mechanism,

- Standard input and output as streams.

Useful tools and technics:

- Macro definitions and pre-processing,

- Constant definitions,

- Classes: object types with a limited set of methods operating on them,

- Calling object methods,

- Implicit methods: constructors, destructors, copying, type casting,

- Operator overloading,

- Enumeration types,

- Useful data types.

Pointer types:

- The concept of a pointer and its dereference,

- Passing arguments (and results) by value, pointer, and reference,

- Global and local variables,

- Dynamically allocated memory,

- Smart pointers: unique and shared pointers.

Modularisation and abstraction barriers:

- Header and implementation files.

Recursion:

- Recursion and its implementation,

- Recursive expressing of the problems,

- Verification of recursive programs,

Complexity analysis:

- Asymptotic complexity calculus,

- Algorithm costs: time and memory, worst-case and expected,

- Data size,

- Analysis of recursive programs,

- Amortised cost,

- Complexity analysis examples.

Divide-and-conquer method:

- Incremental method,

- Bisection, and binary search,

- Examples - sorting algorithms.

Dynamic data structures:

- Pointer types,

- Pointer-based implementation of lists,

- Basic list operations,

- Singly linked lists, doubly linked lists, and circular lists,

- Stacks and queues,

- Sentinels and guards.

Trees:

- Binary trees, BST,

- Implementation of trees of arbitrary order,

- Tree traversals.

Useful library data structures:

- Dictionaries (maps),

- Hash tables,

- Sets,

- Queues,

- Stacks.

Backtracking:

- Full state space search,

- Accelerating heuristics,

- Recursion pruning.

Dynamic programming:

- Memoization,

- Tabulation,

- Dynamic programming on trees.

Greedy programming:

- Huffman algorithm,

- Other examples.

Graph search:

- Matrix and list implementation of graphs,

- Breadth-first search,

- Depth-first search,

- Floyd-Warshall algorithm.

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)

Knowledge: The student knows and understands:

- Theoretical foundations of programming, algorithms, complexity, computer system architecture, operating systems, network technologies, selected programming languages and programming paradigms, databases, software engineering (K_W02).

- Basic programming constructs, in an advanced degree (assignment, control statements, function calls, parameter passing, declarations and types, abstraction mechanisms), as well as the concepts of syntax and semantics of programming languages (K_W03).

- Basic methods for algorithm design, analysis and implmentation (structural design, recursion, divide and conquer method, backtracking, correctness, invariants, computational complexity) (K_W04).

- Basic data structures and operations on them (representation of numerical data, arithmetic and rounding errors, arrays, strings, sets, structures, files, pointers and references, pointer data structures, lists, stacks, queues, trees, and graphs) (K_W05).

Skills: The student can:

- Apply mathematical knowledge to formulate, analyse, and solve computer-related tasks (K_U01).

- Read and understand programs written in programming languages based on selected paradigms (K_U06).

- Apply commonly used formats for representing various types of data appropriately to the situation (numbers, arrays, text), taking into account their limitations, such as those related to computer arithmetic (K_U08).

Social competences: The student is prepared to:

- Critically assess their knowledge and the content they encounter (K_K01).

- Work with respect for intellectual honesty in their own actions and those of others, adhere to professional ethics, demand it from others, and care for the achievements and traditions of the software engineer profession (K_K02).

- Recognise the importance of knowledge in solving cognitive and practical problems, search for information in literature, and seek expert opinions (K_K03).