Time complexity, space complexity – informal definition. Asymptotic notation – what is it, why it is defined. Definition of the symbols O, Ω, o. Example of a simple algorithm and identifiction of its time and space complexity.
Array. Definition, basic parameters and properties. Operations on the array and their complexities. List (doubly and singly linked). Definition, basic parameters and properties. Operations on the list and their complexities.
Stack. Definition, basic parameters, properties and operations. Implemetation via array and singly linked list and the complexities of the basic operations. Queue. Definition, basic parameters, properties and operations. Implemetation via array and singly linked list and the complexities of the basic operations.
Bubble sort and Insertion sort. Properties and a description of the algorithms, time complexity.
Heapsort. Heap as a data structure and its properties. Representation of the heap via array. Properties and description of the algorithm, time complexity.
Merge sort. Properties and description of the algorithm, time complexity.
Quicksort. Properties and description of the algorithm, time complexity.
Searching. Data structure for searching and its operations. Finding an element in an array, linked list and a sorted array. Complexities of the find() operations on these structures.
Binary search tree. Definition, basic operations and its complexities. Height of a binary search tree.
Balanced binary search trees. The purpouse of balancing. AVL tree – definition, height, operations insert and delete and their complexities.
B-tree. Definition, height, operations insert and delete and their complexities.