Introductory programming
General data
Course ID:  1000211bWPI 
Erasmus code / ISCED: 
11.301

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

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 mediumscale 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., contextfree grammars, or BNF),  The concepts of syntax and semantics,  Algorithmic domain: * arithmetic expressions (integer and floatingpoint numbers), * logical expressions, * characters and strings,  Variables and their types, assignment statements.  Defining (nonrecursive) 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,  Floatingpoint 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 preprocessing,  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, worstcase and expected,  Data size,  Analysis of recursive programs,  Amortised cost,  Complexity analysis examples. Divideandconquer method:  Incremental method,  Bisection, and binary search,  Examples  sorting algorithms. Dynamic data structures:  Pointer types,  Pointerbased 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,  Breadthfirst search,  Depthfirst search,  FloydWarshall 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; AddisonWesley (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 AddisonWesley (1973) 5. Wirth N, Systematic Programming: An Introduction; PrenticeHall series in Automatic Computation (1973) 6. Wirth N., Algorithms + Data Structures = Programs; PrenticeHall 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 computerrelated 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:  20231001  20240128 
Navigate to timetable
MO WYK
WYK
CW
CW
CW
CW
CW
CW
CW
CW
CW
CW
LAB
CW
CW
CW
TU LAB
CW
W CW
WYK
WYK
LAB
LAB
CW
CW
CW
CW
LAB
CW
LAB
LAB
CW
CW
CW
LAB
LAB
LAB
LAB
LAB
CW
LAB
TH CW
FR CW

Type of class: 
Classes, 60 hours
Lab, 30 hours
Lecture, 60 hours


Coordinators:  Piotr ChrząstowskiWachtel, Marcin Kubica  
Group instructors:  Łukasz Bożyk, Paweł Brach, Piotr ChrząstowskiWachtel, 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 WalukiewiczChrząszcz, Marcin Waniek, Artur Zaroda  
Students list:  (inaccessible to you)  
Examination:  Examination 
Classes in period "Winter semester 2024/25" (future)
Time span:  20241001  20250126 
Navigate to timetable
MO WYK
WYK
CW
CW
CW
CW
CW
CW
CW
CW
CW
CW
CW
CW
CW
CW
TU CW
LAB
W WYK
WYK
LAB
LAB
CW
CW
LAB
CW
CW
CW
LAB
CW
LAB
CW
LAB
CW
CW
LAB
LAB
CW
LAB
LAB
LAB
LAB
CW
LAB
CW
TH CW
FR 
Type of class: 
Classes, 60 hours
Lab, 30 hours
Lecture, 60 hours


Coordinators:  Piotr ChrząstowskiWachtel, Marcin Kubica  
Group instructors:  Łukasz Bożyk, Piotr ChrząstowskiWachtel, Jacek Chrząszcz, Marcin Dziubiński, Krzysztof Fleszar, Agata Janowska, Eryk Kopczyński, Marcin Kubica, Wojciech Nadara, Paweł Parys, Jakub Pawlewicz, Marcin Peczarski, Grzegorz Pierczyński, Jakub Radoszewski, Przemysław Rutka, Michał Startek, Tomasz Waleń, Daria WalukiewiczChrząszcz, Marcin Waniek, Artur Zaroda  
Students list:  (inaccessible to you)  
Examination:  Examination 
Copyright by University of Warsaw.