University of Warsaw - Central Authentication System
Strona główna

Introductory programming

General data

Course ID: 1000-211bWPI
Erasmus code / ISCED: 11.301 Kod klasyfikacyjny przedmiotu składa się z trzech do pięciu cyfr, przy czym trzy pierwsze oznaczają klasyfikację dziedziny wg. Listy kodów dziedzin obowiązującej w programie Socrates/Erasmus, czwarta (dotąd na ogół 0) – ewentualne uszczegółowienie informacji o dyscyplinie, piąta – stopień zaawansowania przedmiotu ustalony na podstawie roku studiów, dla którego przedmiot jest przeznaczony. / (0612) Database and network design and administration The ISCED (International Standard Classification of Education) code has been designed by UNESCO.
Course title: Introductory programming
Name in Polish: Wstęp do programowania
Organizational unit: Faculty of Mathematics, Informatics, and Mechanics
Course groups: Obligatory courses for 1st grade JSIM
Obligatory courses for 1st year Computer Science
ECTS credit allocation (and other scores): 12.00 Basic information on ECTS credits allocation principles:
  • the annual hourly workload of the student’s work required to achieve the expected learning outcomes for a given stage is 1500-1800h, corresponding to 60 ECTS;
  • the student’s weekly hourly workload is 45 h;
  • 1 ECTS point corresponds to 25-30 hours of student work needed to achieve the assumed learning outcomes;
  • weekly student workload necessary to achieve the assumed learning outcomes allows to obtain 1.5 ECTS;
  • work required to pass the course, which has been assigned 3 ECTS, constitutes 10% of the semester student load.

view allocation of credits
Language: Polish
Type of course:

obligatory courses

Short description:

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.

Full description:

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.

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)

Learning outcomes:

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

Classes in period "Winter semester 2023/24" (past)

Time span: 2023-10-01 - 2024-01-28
Selected timetable range:
Navigate to timetable
Type of class:
Classes, 60 hours more information
Lab, 30 hours more information
Lecture, 60 hours more information
Coordinators: Piotr Chrząstowski-Wachtel, Marcin Kubica
Group instructors: Łukasz Bożyk, Paweł Brach, Piotr Chrząstowski-Wachtel, Jacek Chrząszcz, Marcin Dziubiński, Krzysztof Fleszar, Eryk Kopczyński, Marcin Kubica, Paweł Parys, Jakub Pawlewicz, Marcin Peczarski, Jakub Radoszewski, Przemysław Rutka, Marcin Smulewicz, Michał Startek, Daria Walukiewicz-Chrząszcz, Marcin Waniek, Artur Zaroda
Students list: (inaccessible to you)
Examination: Examination

Classes in period "Winter semester 2024/25" (future)

Course descriptions are protected by copyright.
Copyright by University of Warsaw.
Krakowskie Przedmieście 26/28
00-927 Warszawa
tel: +48 22 55 20 000 https://uw.edu.pl/
contact accessibility statement mapa serwisu USOSweb 7.0.4.0-4 (2024-07-15)