Introductory programming
General data
Course ID: | 1000-211bWPI | 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): |
13.00 ![]() ![]() |
||
Language: | Polish | ||
Type of course: | obligatory courses |
||
Short description: |
Basic lecture introducing the notions of algorithms and programs. Students are taught how to design algorithms, prove their correctness and express them in a programming language. Complexity of algorithms is an important issue. Basic data structures (arrays, llists, trees) and programming techniques are introduced. |
||
Full description: |
* 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 |
||
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: |
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. |
||
Assessment methods and assessment criteria: |
(in Polish) Zaliczenie przedmiotu składa się z trzech elementów:
Kolejne wymagania przedstawione są poniżej:
|
Classes in period "Winter semester 2021/22" (past)
Time span: | 2021-10-01 - 2022-02-20 |
![]() |
Type of class: |
Class, 60 hours ![]() Lab, 30 hours ![]() Lecture, 60 hours ![]() |
|
Coordinators: | Piotr Chrząstowski-Wachtel | |
Group instructors: | Łukasz Bożyk, Piotr Chrząstowski-Wachtel, Marcin Dziubiński, Krzysztof Fleszar, Marcin Peczarski, Grzegorz Pierczyński, Michał Startek, Tomasz Waleń, Daria Walukiewicz-Chrząszcz, Artur Zaroda | |
Students list: | (inaccessible to you) | |
Examination: | Examination |
Classes in period "Winter semester 2022/23" (future)
Time span: | 2022-10-01 - 2023-01-29 |
![]() |
Type of class: |
Class, 60 hours ![]() Lab, 30 hours ![]() Lecture, 60 hours ![]() |
|
Coordinators: | Piotr Chrząstowski-Wachtel, Marcin Kubica | |
Group instructors: | Piotr Chrząstowski-Wachtel, Jacek Chrząszcz, Marcin Dziubiński, Krzysztof Fleszar, Eryk Kopczyński, Marcin Kubica, Mirosława Miłkowska, Jakub Pawlewicz, Marcin Peczarski, Grzegorz Pierczyński, Jakub Radoszewski, Przemysław Rutka, Piotr Skowron, Michał Startek, Tomasz Waleń, Daria Walukiewicz-Chrząszcz, Artur Zaroda, Maciej Zielenkiewicz | |
Students list: | (inaccessible to you) | |
Examination: | Examination |
Copyright by University of Warsaw.