Algorithms and Complexity

Welcome to the "Algorithms and Complexity" course. Within the framework of the course a variety of concepts will be presented: Introductory Concepts, asymptotic notation, Data structures. Priority Queues: Heap, classification algorithms, Union - Find, Divide-and-Conquer Algorithms: numbers and tables multiplication, exponentiation, Quicksort, probabilistic Quicksort. The problem of choice, binary search, interpolation search, greedy algorithms, dynamic programming.

Objectives

Familiarization with the basic concepts of the course.

Prerequisites

This information is not available.

Syllabus

Techniques for asymptotic program analysis and algorithm selection criteria. Algorithm design techniques: divide and conquer, dynamic programming, greedy algorithms. Applications to graph theory (depth-first search, breadth-first search, minimum spanning tree, shortest path). Sorting and searching. Algebraic problems (evaluation of polynomials, matrix multiplication). Computability and complexity. Computational complexity classes. Polynomial-time algorithms and NP-complete problems. Spatial complexity classes. Lab: A set of algorithmic problems to be solved in C / C + +.