*Conducted in terms:*2019/20_L, 2020/21_L, 2021/22_L, 2022/23_L

*ECTS credits:*unknown

*Language:*Polish

*Related to study programmes:*

# Algorithms and data structures WM-I-ASD

Prerequisites: Diecrete Mathematics, Calculus and Algebra. Introduction to Programming

Course program

1. Basic motivations. Classes of asymptotic growth of functions, notations big and small „o”. An introduction to analysis of complexity of algorithms, methods of invariants.

2. Basic programming techniques: recursion, divide and conquer, dynamic programming. Master theorem.

3. Basic data structures and operations on them: a list, a stack, a queue.

4. A definition of a problem of sorting. Merge sort and its complexity.

5. Quicksort. A complexity analysis. Modification of the quicksort.

6. An implementation of a queue with a heap. Heapsort.

7. A lower bound for complexity of sorting by comparisons and transpositions only. Radix sort and bucket sort.

8. Dictionaries. A definition and implementation of a tree. The searching problem. Binary search and binary search tree (BST).

9. Basic operations on BST and their complexity: insert, find, delete. Methods of a tree travelsal.

10. Self balancing binary trees (AVL).

11. 2-3 trees. Red-black trees. B-trees.

12. Graphs: a definition and methods of implementations. Methods of a graph traversal: depth first search (DFS) and breadth first search (BFS).

13. Implementations of DFS and BFS with queue and stack, respectively. Topological sorting of a directed graph.

14. Minimal spanning tree. Prim's algorithm and its complexity. A description Kruskal algorithm.

15. Basics of fast Fourier tranformation (FFT).

## (in Polish) Dyscyplina naukowa, do której odnoszą się efekty uczenia się

## (in Polish) E-Learning

## (in Polish) Grupa przedmiotów ogólnouczenianych

## Subject level

## Learning outcome code/codes

## Type of subject

## Course coordinators

## Assessment criteria

A writing exam.

## Bibliography

1. Cormen T., C. Leiserson, R. Rivest, Introduction to algorithms, MIT Press, 1990.

2. Sadgewick R., Wayne K., Algorithms, 4th edition, Addison-Wesley, 2011.

3. Dasgupta, Papadimitriou, Vazirani, Algorithms, 2006.

4. Knuth D., The art of computer programming, vol. I-IV.

5. Aho, Hopcroft, Ullman, Data structures and algorithms.

6. Harel, Feldman, Algorithmics. The spirit of Computing, Academic Press.

## Additional information

Information on *level* of this course, *year of study* and semester when the course
unit is delivered, types and amount of *class hours* - can be found in course structure
diagrams of apropriate study programmes. This course is related to
the following study programmes:

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