Algorithms and Programming in Python

The subject is an introduction to the field of algorithmics and programming. In addition, it develops algorithmic thinking and improves logical reasoning. The main goal is to prepare students to solve problems in various fields of science with the use of basic algorithms, data structures, and implement algorithms in Python.

The lecture covers the basic concepts of algorithm theory, classical algorithms, data structures and the rules of programming in Python. During the laboratory, students acquire the skills of algorithm design by solving typical tasks, such as searching, sorting, implementation of algorithms in Python using standard libraries and complex data structures.

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.

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

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