Algorithms and data structures WM-I-ASD
Lectures (WYK) Summer semester 2023/24

Basic literature (one of the books)

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

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

Suplementary material

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.

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. Hash tables.