Algorithms and Programming in Python 1000-OG-EN-APP

https://moodle.umk.pl/course/view.php?id=7170
https://moodle.umk.pl/course/view.php?id=3910 (term 2022/23Z)
https://moodle.umk.pl/course/view.php?id=3910 (term 2023/24Z)

The topics of the following lectures and laboratories are strictly correlated. For each two-hour lecture, there are four hours of exercises in a computer laboratory when the algorithms discussed in the lecture are effectively implemented in Python. Moreover, students discover and develop algorithms for solving related problems.
Lecture and laboratory topics:
1) Introduction to algorithmics and programming - definition and properties of an algorithm, ways of representing algorithms, examples of algorithmic problems, representation of characters and numbers in a computer.
2) Introduction to Python programming language, programming environment, syntax and semantics, program structure, variables, instructions, comments, using additional programming libraries - algorithms for examining various properties of numbers and texts: divisibility, Euclid's algorithm, palindromes.
3) Functions, passing parameters, random data, basic information retrieval algorithms, number systems, generating data with specific properties, a list as a data structure.
4) Basic algorithms that organize information, use of prefix sums, reading data from files, saving information in files.
5) Iteration and recursion - recursive and iterative calculations; applications of recursion, examples of recursive and iterative. algorithms: Euclid's algorithm, Horner's scheme, fast exponentiation
6) Recursive sorts; stack, queue; Reverse Polish Notation (RPN); tuples as immutable structures.
7) Sets, dictionaries and their application, graphs and their basic representations; topological sort; numerical algorithms, copying references in Python.
8) Supercomputers. Turing machine. Computational complexity, asymptotic notation, optimal algorithms.
9) Algorithmic methods and techniques; greedy approach, dynamic programming, Bellman’s optimality principle, backtracking.
10) Basic geometric algorithms - the position of a point in relation to the straight line, line intersection, polar sort, convex hull.
11) Basic graphic modules in Python, algorithm visualizations, graphical data representation, fractals, Monte Carlo method visualization.
12) Algorithms on texts: pattern searching, information compression.
13) Pseudo-code of algorithms
14) Programming paradigms, basics of object-oriented programming: classes, objects, methods.
15) Object-oriented programming - polymorphism, inheritance, operator overloading, example of object-oriented implementations.

Term 2022/23Z:

None

Term 2023/24Z:

None

Term 2024/25Z:

As in part A

Term 2025/26Z:

As in part A

Total student workload

Contact hours with teacher: - participation in virtual lectures - 30 hrs - participation in laboratory - 30 hrs Self-study hours: - preparation for lectures - 30 hrs - preparation for laboratory - 30 hrs - preparation for test - 20 hrs - preparation for examination - 20 hrs Altogether: 160 hrs (6 ECTS)

Learning outcomes - knowledge

Student: W1: has a basic knowledge of the concepts of algorithm theory: input and output data, algorithm definition, representations of algorithms, instruction, iteration, conditionals, recursion, computational complexity, etc. W2: knows general properties of algorithms useful in various fields of science, their complexity and applications; W3: is familiar with the basic methods of designing algorithms and examples of their use, knows the basic data structures (lists, tuples, dictionaries, sets, files) and operations performed on them (adding and removing elements, changing values, etc.); W4: is acquainted with the Python programming language, knows the rules of structured and procedural programming; knows the rules of object-oriented programming, the concept of class and object, the rules of inheritance, W5: knows at least two tools for working with the source code, knows how to use the installer of packages;

Learning outcomes - skills

Student: U1: is able to design algorithms for typical tasks, such as searching and sorting; can formulate a specification of an algorithm and save it in the form of a pseudocode; implements algorithms and selects appropriate data structures; analyzes the influence of data structures on the computational complexity of algorithms; U2: is able to write, run, test and debug a program in a selected development environment; can work with objects and design object-oriented programs; is able to use a standard library and install additional libraries; is able to work with complex data structures; is able to build a hierarchical structure of the program, creates code resistant to user errors; U3: has basic skills in designing algorithms that solve specific problems in various fields of science, can use ready-made functions and methods for processing data sets and creating their visualization; U4: is capable to analyze and understand programs written in the selected programming language, to explain their operation, to test the solution correctness; U5: can individyually search for information in various sources, also in foreign languages.

Learning outcomes - social competencies

Student: K1: understands the importance of a thorough analysis of problems from various areas of life in the context of the possibility of using algorithms to solve encountered problems; K2: understands the necessity of designing properly functioning computer applications and is aware of their impact on the quality of devices and applications functioning in the society; K3: is well prepared to predict possible difficulties while programming algorithms, is targeted to perform the task in the best possible way; takes care of the detail; is systematic and persistent; K4: can work in teams while creating and solving various problem situations.

Teaching methods

Expository teaching methods: - informative (conventional) lecture, - problem-based lecture, - description. Observation/demonstration teaching methods: - drama, - display, - simulation (simulation games). Exploratory teaching methods: - experimental, - brainstorming, - classic problem-solving, - project work.

Observation/demonstration teaching methods

- simulation (simulation games)
- display
- drama

Expository teaching methods

- informative (conventional) lecture
- description
- problem-based lecture

Exploratory teaching methods

- classic problem-solving
- presentation of a paper
- seminar
- brainstorming
- practical
- experimental
- laboratory

Online teaching methods

- methods developing reflexive thinking
- content-presentation-oriented methods
- exchange and discussion methods
- cooperation-based methods
- games and simulations

Prerequisites

As a prerequisite for the course it is recommended that a student has a basic digital competences, such as using a text editor, running applications, using websites. Basic knowledge of school mathematics will also be useful.

Course coordinators

Anna Kwiatkowska

Assessment criteria

Assessment methods:

Written examination composed of two parts:
– theoretical (knowledge), 50 pts, – W1, W2, W3, W4, U1, U4, K1
– practical (skills), 50 pts – W2, W3, W5, U2, U3, U5, K2, K3, K4
In order to pass an exam, a student has to receive at least 50% in every part.
Laboratories:
The final grade is composed of activities:
– two tests, 2*30 pts – W2, W3, W4,U1, U4, K1
– six homeworks, 6*5 pts – W2, W3, W5; U3, U5, K3, K4
– lecture knowledge, 10 pts, – W1, W2, W3, W4, U5
In order to pass, a student has to receive at least 50% of every
component grade. During the semester, only two unjustified absences
are permitted.

Assessment criteria:
fail (2), 0-49 pts
satisfactory (3), 50-59 pts
satisfactory plus (3+), 60-69 pts
good (4), 70-79 pts
good plus (4+), 80-89 pts
very good (5), 90-100 pts

Bibliography

Basic literature – books:
[1] R. Sedgewick, K. Wayne, Algorithms, Addison-Wesley Longman, Amsterdam 2020
[2] D. Harel, Algorithmics: The Spirit of Computing, Addison Wesley Publishing Company, 2004
[3] E. Matthes, Python Crash Course, No Starch Press, US, 2019
Basic literature – e-materials:
[4] An overview of algorithms, https://www.khanacademy.org/computing/computer-science/algorithms
[5] Descriptions of many algorithms and data structure, https://cp-algorithms.com/
[6] The documentation of Python, http://docs.python.org
[7] Lecturer’s electronic materials on the Moodle platform, http://moodle.umk.pl
Supplementary literature:
[8] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, MIT Press Ltd, 2009.
[9] W. McKinney, Python for Data Analysis, O'Reilly Media, Inc., 2017

Term 2022/23Z:

None

Term 2023/24Z:

None

Term 2024/25Z:

As in part A

Term 2025/26Z:

As in part A

Additional information

Additional information (registration calendar, class conductors, localization and schedules of classes), might be available in the USOSweb system:

Description of 1000-OG-EN-APP in USOSweb