Mathematical Analysis of Algorithms

Data is displayed for the academic year: 2024./2025.

Lecturers

Prof.
Andrea Aglić Aljinović
PhD

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).

Prerequisites

Mathematical Analysis 1, Discrete Mathematics 1

Study Programmes

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

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

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,

General

ID 222645
  Winter semester
5 ECTS
L1 English Level
L1 e-Learning
45 Lectures
0 Seminar
0 Exercises
0 Laboratory exercises
0 Project laboratory
0 Physical education excercises

Grading System

85 Excellent
70 Very Good
55 Good
45 Sufficient

Similar Courses