Algorithms and data structures WM-I-ASD
Prerequisites: Diecrete Mathematics, Calculus and Algebra. Introduction to Programming
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
Learning outcome code/codes
Type of subject
A writing exam.
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.
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: