Basic notions concerning algorithms. Asymptotic notations and their mathematical interpretation. Model of RAM-machine and RAM commands. Use of pseudo-code. Computational complexity of programs. The notions of time and memory complexities and complexity estimation. Memory representations and basic operations on selected dynamic structures (lists, stacks, queues and graphs). Tree-like structures and their features. Binary trees. Recursion. Binary search trees (BST) and their characteristics. Operations on BST. Definition, essential qualities and basic algorithms relating to heap. Priority queues. Searching on trees (breath-first, depth-first and best-first strategies). Generating of solution paths. Sorting - definitions and problem statement. Explanation and complexity estimation of selected sorting algorithms. Mathematical proof of correctness for a selected sorting method. Advanced strategies – dynamic programming and greedy algorithms.
Classes and laboratory:
Practical use of asymptotic notations. Simple algorithms and their representation in pseudo-code. Example RAM-programs. Time and memory complexity estimation. Examples using lists, stacks and queues. Solving problems with recursion. Programming operations on BST. Solving problems by searching the trees. Construction and practical verification of selected sorting algorithms.