Mathematical Analysis of Algorithms

Course Description

Discrete mathematical methods for analysis of algorithms: recurrence relations, generating functions, asymptotic approximations and analytic combinatorics. Applications for fundamental algorithms and combinatorial structures (trees, permutations, strings, words).

Learning Outcomes

  1. Analyze classic computer algorithms
  2. Apply recurrence relations for analysis of algorithms
  3. Apply generating functions for analysis of algorithms
  4. Apply asymptotic approximations for analysis of algorithms
  5. Apply analytic combinatorics for analysis of algorithms

Forms of Teaching

Lectures

Lectures are held in two cycles, 3 hours per week.

Independent assignments

Each student will have to solve independent assignments.

Grading Method

Continuous Assessment Exam
Type Threshold Percent of Grade Threshold Percent of Grade
Homeworks 0 % 10 % 0 % 0 %
Mid Term Exam: Written 0 % 45 % 0 %
Final Exam: Written 0 % 45 %
Exam: Written 0 % 100 %

Week by Week Schedule

  1. Nonlinear first-order recurrences
  2. Solving methods: change of variables, repertoire, bootstrapping, perturbation
  3. Binary and general divide-and-conquer recurrences
  4. Ordinary and exponential generating functions
  5. Generating function solution of recurrences
  6. Expanding generating functions
  7. Functional equations on generating functions
  8. Midterm exam
  9. Notation, definition, basic properties of O-notation
  10. Asymptotic approximations of finite sums; Approximating sums with integrals
  11. Examples for Ramanujan and binomial distributions
  12. Symbolic method for unlabelled combinatorial classes
  13. Symbolic method for labelled combinatorial classes
  14. Applications for essential combinatorial structures
  15. Final exam

Study Programmes

University graduate
Audio Technologies and Electroacoustics (profile)
Free Elective Courses (1. semester) (3. semester)
Communication and Space Technologies (profile)
Free Elective Courses (1. semester) (3. semester)
Computational Modelling in Engineering (profile)
Free Elective Courses (1. semester) (3. semester)
Computer Engineering (profile)
Free Elective Courses (1. semester) (3. semester)
Computer Science (profile)
Free Elective Courses (1. semester) (3. semester)
Control Systems and Robotics (profile)
Free Elective Courses (1. semester) (3. semester)
Data Science (profile)
Free Elective Courses (1. semester) (3. semester)
Electrical Power Engineering (profile)
Free Elective Courses (1. semester) (3. semester)
Electric Machines, Drives and Automation (profile)
Free Elective Courses (1. semester) (3. semester)
Electronic and Computer Engineering (profile)
Free Elective Courses (1. semester) (3. semester)
Electronics (profile)
Free Elective Courses (1. semester) (3. semester)
Information and Communication Engineering (profile)
Free Elective Courses (1. semester) (3. semester)
Network Science (profile)
Free Elective Courses (1. semester) (3. semester)
Software Engineering and Information Systems (profile)
Elective Course of the Profile (1. semester)

Literature

(.), R. Sedgewick, P. Flajolet: An Introduction to the Analysis of Algorithms,
(.), R. Sedgewick, K. Wayne: Algorithms,
(.), T. Cormen, C. Leiserson, R. Rivest, C. Stein: Introduction to Algorithms,
(.), R. Sedgewick, P. Flajolet: Analytic Combinatorics,
(.), D. Knuth: The Art of Computer Programming,

For students

General

ID 222645
  Winter semester
5 ECTS
L1 English Level
L1 e-Learning
45 Lectures

Grading System

85 Excellent
70 Very Good
55 Good
45 Acceptable