Introductory programming

* 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

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.