University of Warsaw - Central Authentication SystemYou are not logged in | log in
course directory - help

Introductory programming

General data

Course ID: 1000-211bWPI Erasmus code / ISCED: 11.301 / (0612) Database and network design and administration
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
view allocation of credits
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:

  1. Zaliczenie laboratorium
  2. Zaliczenie ćwiczeń
  3. Zaliczenie egzaminu

Kolejne wymagania przedstawione są poniżej:

  1. Zaliczenie laboratorium polega na uzyskaniu co najmniej 50% punktów z 3-4 domowych zadań programistycznych. Łączna liczba punktów do zdobycia, to 60. Punkty zdobywa się za poprawnie działające kody, przy czym pewna pula punktów (1/3) przyznawana jest za styl programowania, przy czym styl uwzględniamy tylko w przypadku działających programów. Osoby, które nie zaliczą laboratorium, jednocześnie nie zaliczają ćwiczeń i nie są dopuszczane do egzaminu z żadnym terminie.
  2. Na zaliczenie ćwiczeń składa się wynik uzyskany z sumy trzech składników: punktów z laboratorium (maksymalnie 60), punktów z kartkówek (maksymalnie 60) oraz punktów z 3 kolokwiów (maksymalnie 120). Kartkówek w semestrze jest 10, ocenianych w skali 0-10 i do oceny bierze się pod uwagę 6 najlepszych wyników. Kolokwia są wyceniane po 40 punktów. łącznie jest więc do zdobycia 240 punktów, z czego 144 (60%) zalicza. Osoby, które zaliczą laboratorium, ale nie uzyskają wymaganej sumy punktów, nie zaliczają ćwiczeń i tracą prawo pisania egzaminu w sesji normalnej. Mogą przystąpić warunkowo do egzaminu w sesji poprawkowej, z tym że traktujemy takie przypadki indywidualnie i zastrzegamy prawo indywidualizacji wymagań w takiej sytuacji (np. dodatkowe zadanie na zaliczenie ćwiczeń lub inne progi). W przypadku pozytywnym uzyskuje się wtedy zarówno zaliczenie ćwiczeń, jak i zdanie egzaminu, a negatywnym zarówno niezaliczenie ćwiczeń, jak i niezdanie egzaminu.
  3. Przy samym egzaminie w pierwszym terminie osoby, które uzyskały dobre wyniki z ćwiczeń i labów, będą mogły częściowo skorzystać z sumy c=L+C+K z wagą 1/3. Zatem jeśli do zdobycia na egzaminie jest E punktów, a ktoś uzyskał z samego egzaminu e, to ostateczny wynik procentowy łączony l, to l = c/(2.4*3) + (200e/3E) i ostateczny wynik całości, to maksimum z procentowego wyniku czystego (100e/E) i łączonego l, czyli max (100e/E, l). Próg zaliczenia egzaminu na ocenę dostateczną, to 60%. Reszta skali - zależna od wyników. W drugim terminie liczy się czysty wynik egzaminu i nie są brane pod uwagę ani ćwiczenia ani laboratoria.

Classes in period "Winter semester 2021/22" (past)

Time span: 2021-10-01 - 2022-02-20
Choosen plan division:


magnify
see course schedule
Type of class: Class, 60 hours more information
Lab, 30 hours more information
Lecture, 60 hours more information
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
Choosen plan division:


magnify
see course schedule
Type of class: Class, 60 hours more information
Lab, 30 hours more information
Lecture, 60 hours more information
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
Course descriptions are protected by copyright.
Copyright by University of Warsaw.