This course covers the basics of creating effective algorithms and analyzing them in terms of execution time and memory usage. Students will learn classic algorithms, methods for optimizing them, and mathematical tools for proving correctness and evaluating complexity.
Course program
Introduction to algorithms and their analysis
- What is an algorithm?
- Complexity estimation (asymptotics): O, Ω, Θ;
- Computation models.
Basic sorting and search algorithms
- Sorting: bubble sort, insertion sort, merge sort, quick sort;
- Binary search and its application.
Algorithm design methods
- Divide and conquer;
- Greedy algorithms;
- Dynamic programming;
- Branch and bound method.
Graph algorithms
- Depth-first and breadth-first search;
- Minimum spanning tree (Kruskal, Prim);
- Shortest paths (Dijkstra, Floyd-Warshall).
Algorithm complexity theory
- Complexity classes P, NP, NP-complete;
- Examples of NP-complete problems;
- Difficulty and solvability of problems.
Proving the correctness of algorithms
- Cycle invariants;
- Inductive proofs;
- Formal methods.
Practical assignments and projects
- Implementation of algorithms in a selected programming language;
- Optimization and performance analysis.
Course duration
12 weeks (3 classes per week, 2 hours each).