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

Criteria for passing the "Introduction to Programming".

Passing the course consists of two stages:

1. Passing the laboratories and exercises

2. Exam

Ad 1:

In the laboratories you will have 4 tasks. The results of the best 3 count. Each task is rated on a scale of 0-20 and we assess both the correctness of the code, its complexity, as well as the style of solutions and the timeliness of task delivery. Therefore, a maximum of 60 points can be obtained from laboratory tasks. In order to pass the course, you must receive at least 50% of the maximum number of points, i.e. 30 points, and additionally pass the exercises.

There will be 8 quizzes and 3 colloquia during the exercises. The quizzes will be 10 points each, but the final result will be taken into account by the best 6 of these 8. The colloquia will be worth 40 points each and all grades count. A maximum of 60 and 120 points can be obtained from quizzes and colloquias, respectively.

In total, a maximum of 240 points can be obtained from laboratory tasks, quizzes and colloquias.

The standard pass threshold is 60%, so 144 points pass.

Those who obtain 90%, i.e. 216 points, are entitled to take the zero exam and we offer them a very good grade (5) from this term (i.e. de facto exemption).

Those who pass the laboratories and exercises have the right to take the exam on the first term.

Ad 2:

The exam consists of written tasks. The final score depends on the percentage score, which is the maximum of the two numbers

- pure percentage result of the exam

- 50% weighted result from the percentage result from exercises and laboratories and 50% from the exam.

A score of at least 60% guarantees passing the exam. A score below 50% guarantees a failure.

Example:

Someone got 40 points from quizzes, 40 points from laboratory tasks and 100 points from colloquia. In total, she or he scored 180 points and passes exercises and laboratories at the level of 75%.

He or she is allowed to take the exam and writes it at 45%. The average of these two results is 60%, so it is enough to pass the exam.

Students who do not pass the exam on the first term can take the exam a second time.

The second term of the exam is governed by the same rules, except that we also conditionally admit people who have passed the laboratories themselves. Passing this exam on the above terms results in passing the exercises and the subject at the same time. Failing means failing the exercises and the subject.