Convex Optimization (NMMB409) - Winter term 2024/25

Lecture: Thursday 12:20 - 13:50, K7; Friday 12:20 - 13:50, K8
Practicals: Wednesday 12:20 - 13:50, K8; run by Alexey Barsukov.

Literature: The lecture follows mainly the book and slides on Convex Optimization by Boyd and Vandenberghe [BV], which are freely available online on Boyd's website. If alternative material is used, it will be shared here. Practicals and homework assignments will also be published here. Homeworks will include programming assignments that are based on using the Python package CVXPY (CVXPY).

Evaluation:
There will be 4 homework assignments, on each of which you need to score at least 60% to obtain the credit (zápočet) for the course. If this condition cannot be met (e.g. due to illness, or some other significant reasons), there is the possibility of solving an extra 5th homework assignment.
Exam: oral examination. It is necessary to have the credit in order to take the exam.

Consulation: If you have any questions, do not hesitate to ask! Best in my office hours, Fr: 11:00-12:20.

Overview:

Date	Topics	Reference	Homework
2.10	Pr.: Introduction to Python and the CVXPY package	Pr0, Pr1
3.10	Optimization problems Convex problems can be solved efficiently (e.g. linear programming, least-squares)	BV 1
4.10	Convex sets: Important examples (affine spaces, halfspaces, balls, cones,...) closedness under intersection and affine/perspective functions	BV 2.1-2.3
9.10	Pr.: Examples of LPs and least-squares problems	Pr2
10.10	Separating hyperplane theorem convex/concave function: important examples, first and second order criteria	BV 2.5, 3.1
11.10	the epigraph, operations that preserve convexity (weighted sums, suprema, infima, composition)	BV 3.1., 3.2
16.10	Pr.: Convex sets and functions, the perspective of a function	Pr3	[HW1] - 30.10
17.10	Quasiconvex functions; Important definition for general optimization problems Convex OPs: local optima are optima; optimality criterion in differentiable case	BV 3.4, 4.1, 4.2
18.10	LP, QP, QCQP, SOCP + Examples (Chebyshev center, distance of polyhedra, robust LP...); Transforming Optimization Problems	BV 4.3, 4.4, 4.2
23.10	Pr.:Transforming Optimization Problems, standard form of LP	Pr4
24.10	Geometric programming, linear-fractional programs bisection method for quasiconvex problems, proper cones	BV 4.5, 4.3.2 4.2,5, 2.4
25.10	Generalized inequality constraints (conic problems), SDPs the SDP-relaxation of Max-Cut, LP relaxations	BV 4.6 Notes
30.10	Pr.: Examples of SDPs, reduction of LP, QCQP, SOCP to SDPs	Pr5
31.10	Multiobjective optimization problems, finding Pareto optima via scalarization; scalarization for general K via dual cones K*	BV 4.7, 2.6
1.11	Duality: Lagrangian, dual function, dual problem, weak duality Slater's condition for strong duality	BV 5.1, 5.2
6.11	Pr.: Duality	Pr6	[HW2] - 20.11
7.11	Different interpretations of duality (geometrical, saddle point interpretation) Examples, randomized strategies for randomized matrix games	BV 5.3, 5.7 5.2.5
8.11	Farkas lemma, strong duality for LPs	BV 5.8, Notes
13.11	Pr.: Duality, Slater's condition	Pr7
14.11	KKT conditions, perturbation analysis	BV 5.5, 5.6
15.11	Duality for generalized inequalities Norm and penality function approximation	BV 5.9, 6.1
20.11	Pr.: KKT conditions, perturbation analysis; log barrier penalty function	Pr8	[HW3] - 4.12
21.11	Comparisons of different penalty functions, Huber penalty for robust approximation least-norm problems, regularization problems and applications in signal processing	BV 6
22.11	maximimum likelihood estimates and examples: linear measurement models, Poisson distributon, logistic regression, covariance matrix	BV 7.1
27.11	Pr.:Function fitting	Pr9
28.11	Function fitting (discussion practicals Pr9), MAP estimates Binary hypothesis testing	BV 7.1, 7.3
29.11	Binary hypothesis testing, Optimal experiment design	BV 7.3, 7.5
4.12	Pr.:statistical estimation	Pr10	[HW4] - 22.12
5.12	Geometric problems: distance between convex sets, outer and inner Loewner-John ellipsoids, centering	BV 8.1,8.2, 8.4,8.5
6.12	Linear discriminators, support vector machines Newton's method to approximate roots of a real-valued function	BV 8.6, [wiki]
11.12	Pr.: Geometric problems (projections onto convex sets)	Pr11
12.12	Unconstraint optimization: Strong convexity and some consequences the (gradient) descent method, backtracking line search	BV 9.1-9.3
13.12	convergence analysis for gradient descent Newton descent (motivation for Newton step; convergence analysis without proof)	BV 9.3-9.5
18.12	Pr.: Steepest descent and Newton descent	Pr12	[HW5] - 10.1
19.12	Newton descent for problems with equality constraints (feasible and infeasible initial point)	BV 10
20.12	the (log-)barrier method (for general convex problems), central path proof of convergence, discussion of examples	BV 11.1-11.6
8.1	Pr.: the barrier method	Pr13
9.1	Linear Programming revisited; the Simplex method
10.1	LP and LP-relaxations in theoretical computer science

---

Algebra 2 (NMAI076) - Spring term 2024

Lecture: Thursday 14:00 - 15:30, lecture room S6
Exercises: Thursdays 15:40 - 17:10 on odd weeks, lecture room S6

Lecture notes	Czech	English
Algebra 1	alg1_cz	alg1_en
Algebra 2	alg1_cz	alg2_en

Evaluation:
To obtain the credit (Zápočet) for the course you need to score at least 54 out of 90 points. Points can be obtained from 3 homework assigments (3*30 points). The final grade will be determined by an oral exam, admission to the exam requires getting ''Zápočet'' first.

Syllabus: This course is a continuation of Algebra 1 and aims to introduce computer science students to some topics from abstract algebra:

1. Homomorphisms (group homomorphism, quotient groups, ring homomorphisms, ideals, classification of finite fields)
2. Number fields (ring and field extensions, algebraic elements, and finite degree extensions)
3. Algorithms in polynomial arithmetic (fast polynomial multiplication and division, decomposition)
4. Other algebraic structures (lattices and Boolean algebras)

Overview:

Date	Topics	Lecture notes	Homework
22/02	Repetition groups, group homomorphisms and isomorphisms, invariants Ex: Examples	Section 1.1-1.3
29/02	Group classifications; Normal subgroups, quotient groups	Section 1.4, 2
06/03	The homomomorphism theorem and isomorphism theorems for groups; Ideals, PIDs Ex: determining quotient groups, sums and intersections of ideas in Z	Section 2, 3	HW1 due 21/03
13/03	Ring homomorphisms, quotient rings	Section 4
20/03	Isomorphism theorems for rings, prime/maximal ideals, ring and field extensions Ex:computing quotient rings, ring extensions	Section 4,5.1
28/03	Algebraic and transcendental elements, the degree of a field extension, minimal polynomials	Section 5.2,6.1,6.2
04/04	minimal polynomials, degrees of general extensions, algebraic numbers are a field Ex: computing minimal polynomials, degrees of extensions, splitting fields	Section 6.2, 6.3	HW2 due 18/04
11/04	Problems solvable by ruler and compass Uniqueness of rupture fields and splitting fields	Section 7, 8
18/04	The classification of finite fields Ex: Constructability of regular n-gons	Section 9
25/04	Modular representations, Fast Fourier Transform	Section 10
02/05	(self study) fast polynomial multiplication and division using FFT Ex: primitive roots, FFT	Section 11	HW3 due 16/05
09/05	fast polynomial multiplication and division using FFT square-free decomposition	Section 11, 12.1
16/05	Berlekamp's algorithm Ex: formal power series, discussion of 3rd homework	Section 12
23/05	Examples of other algebraic structures	Section 13

Consultation:
If you have questions, do not hesitate to ask (either in person or via e-mail)! I have no official office hours, but if required, a personal meeting can be arranged. Please make also use of the exercise classes to discuss your questions.

---

Spring term 2024
Algebra Proseminar (NMAG261)

See David Stanovský's website.

---

Winter term 2023/24
Convex Optimization (NMMB409)

The course was organized via the following Moodle course. The practicals were run by Mykyta Narusevych.

---

Winter term 2023/24
Practicals in Universal Algebra 1 (NMAG405)

See Libor Barto's website.

---

Spring term 2023
Algebra 2 (NMAI076)

Lecture: Monday 09:00 - 10:30, lecture room S6
Exercises: Monday 10:40 - 12:10 on odd weeks, lecture room S6, held by Filippo Spaggiari

Lecture notes	Czech	English
Algebra 1	alg1_cz	alg1_en
Algebra 2	alg1_cz	alg2_en

Evaluation:
To get ''Zápočet'' (i.e. to pass the exercise classes) you need to score at least 45 out of 70 points. Points can be obtained from 2 homework assigments (2*30 points), and in-class presentation (10 points). For more details see Filippo Spaggiari' website.
The final grade will be determined by an oral exam, admission to the exam requires passing the exercise class.

Syllabus: This course is a continuation of Algebra 1 and aims to introduce computer science students to some topics from abstract algebra:

1. Homomorphisms (group homomorphism, quotient groups, ring homomorphisms, ideals, classification of finite fields)
2. Number fields (ring and field extensions, algebraic elements, and finite degree extensions)
3. Algorithms in polynomial arithmetic (fast polynomial multiplication and division, decomposition)
4. Other algebraic structures (lattices and Boolean algebras)

Overview:

Date	Topics	Lecture notes	Homework
13/02	Group homomorphisms and isomorphisms, invariants, classifications Ex: Examples	Section 1
20/02	Normal subgroups, quotient groups, homomophism theorem, 1st isomorphism theorem	Section 2
27/02	Ideals and divisibility, PIDs, ideals in fields Ex: quotient groups, intersection and sum of ideals	Section 3
06/03	Quotient rings, homomorphism theorem, 1st and 2nd isomorphism theorem for rings	Section 4.1,4.2
13/03	prime and maximal ideals; Ring and field extensions, degree Ex:quotient rings, ring and field extensions	Sections 4.3, 5	1st HW due 27.3
20/03	Algebraic and transcendental numbers Minimal polynomials of algebraic numbers	Section 6
27/03	Extensions by more than one element, constructability, ruler-and-circle constructions Ex: minimal polynomials and algebraic numbers	Section 6.3, 7
03/04	Uniqueness of splitting fields (up to isomorphism), Classification of finite fields	Sections 8, 9
10/04	Easter Monday
17/04	Modular representations of rings, Fast Fourier Transformation	Section 10
24/04	Fast polynomial multiplication and division, formal power series Ex: general field extensions and their degree	Section 11
01/05	International Workers' Day
08/05	V-Day		2nd HW due 24.5
15/05	Square-free factorizations of polynomials Berlekamp's algorithm for decomposition into irreducibles	Section 12
22/05	Berlekamp's algorithm; algebraic structures, substructures, homomorphisms Ex: ordered sets, lattices and Boolean algebras	Sections 12, 13

Consultation:
If you have questions, do not hesitate to ask (either in person or via e-mail)! I have no official office hours, but if required, a personal meeting can be arranged. Please make also use of the exercise classes to discuss your questions.

---

Spring term 2023
Practicals in Universal Algebra II (NMAG450)

See Libor Barto's website.

---

Spring term 2022
Universal Algebra II (NMAG450)

Lecture: Monday 10:40 - 12:10, lecture room K7
Exercise classes: even weeks, Monday 12:20 - 13:50, lecture room K7, given by Kevin Berg

Lecture notes

Syllabus:This course discusses selected topics from Universal Algebra. This includes

1. Equational logic: the equational completeness theorem, term rewriting systems, Knuth-Bendix algorithm
2. Commutator theory: Abelianness, the term condition commutator, applications
3. Finitely based algebras: McKenzie's theorem on algebras with DPC
4. Maltsev conditions: Taylor terms, polymorphism clones and CSPs, absorption theory

Evaluation:
Exercises: there will be 3 homework assignments, on which you need to score 60% to get ''Zápočet''
Lecture: oral examination (appointment by mail: michael@logic.at).

Date	Topics	Lecture notes	Exercises	Homework
14/02	Equational theories, fully invariant congruences; completeness theorem for equational logic.	Section 1.1
21/02	term rewrite systems, convergence, Knuth-Bendix	Section 1.2, 1.3	1.2,1.3,1.4
28/02	Abelian and affine algebras Herrmann's fundamental theorem	Section 2.1, 2.2
07/03	The term conditions commutator, Examples (groups and lattices)	Section 2.3	1.2,1.3,1.4 2.12, 2.13	HW1: 1.6, 1.8 (first point) 2.10, 2.14
14/03	A characterization of CD varieties by the commutator	Section 2.4
21/03	Birkhoff's theorem on Id_n a non-finitely based algebra	Chapter 3	2.19,2.20	HW1 due
28/03	Park's conjecture McKenzie's DPC theorem	Section 3.1
04/04	Jonsson's lemma DPSC varieties	Section 3.2	3.2,3.3, 3.11	HW2: 3.4, 3.5, 3.6, and 4.1
11/04	Baker's theorem CSPs: Definition and Examples	Section 3.2, 4.1
18/04	Easter holiday
25/04	Pol-Inv revisited, clone homomorphisms	Section 4.1., 4.2.		HW2 due
02/05	Minion homomorphisms, Taylor's theorem	Section 4.2.	4.3, 4.13	HW3: 4.6,4.7,4.8 and 4.12
09/05	Loop lemma (for triangles) Siggers terms	Section 4.3
16/05	only Exercise class today!			HW3 due

Consultation:
If you have questions on the material, do not hesitate to ask (either in person or via e-mail)! I have no official office hours, but personal meetings can be arranged. Please make also use of the exercise classes to discuss your questions.

Further reading:

• Clifford Bergman: Universal Algebra: Fundamentals and Selected Topics - our library has a few copies!
• Jaroslav Ježek: Universal Algebra
• Barto, Krokhin, Willard: Polymorphisms, and how to use them.
• Barto, Kozik: Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem
• Burris, Sankappanavar: A Course in Universal Algebra

---

Winter term 2021/22
Algebra 1 (NMAI062)

Please register to the !! Moodle course !!

Lecture notes

Lecture: Wednesday 10:40 - 12:10, lecture room S4
Exercise classes: Tuesdays 15:40 - 17:10, lecture room S10, given by Kevin Berg
(current covid regulations)

Evaluation:
To get ''Zápočet'' (i.e. to pass the exercise classes) you need to score at least 60/100 points. These can be obtained from 3 homework assignments (3*30 points), or weekly quizzed (10 points), which will be posted on the Moodle course
The final grade will be determined by a written exam. Admission to the exam requires passing the exercise class.

Syllabus:This course aims to give an introduction to algebra for computer science students. It will cover the following topics:

1. Number theory: prime factorization, congruences, Euler's theorem and RSA, the Chinese remainder theorem
2. Polynomials: rings and integral domains, polynomial rings, irreducibility, GCD, the Chinese remainder theorem and interpolation, the construction of finite fields and applications (error correcting codes, secret sharing,...)
3. Group theory: permutation groups, subgroups, Langrange's theorem, group actions and Burnsides's theorem, cyclic groups, discrete logarithm and applications in cryptography

Literature:The course has its own lecture notes, which are based on David Stanovsky's material from last year, and will be constantly updated during the semester. Complementary resources are for instance

• J. Rotman, A First Course in Abstract Algebra (available in our library),
• C. Pinter A Book of Abstract Algebra (freely available online),
• or any other undergraduate level textbook on abstract algebra.

Consultation:
If you have open questions, do not hesitate to ask (either in person or via e-mail)! I have no official office hours, but if required, a personal meeting can be arranged. Please make also use of the exercise classes to discuss your questions.

---

Spring term 2020
Universal Algebra II (NMAG450)

Lecture notes

Grading:
Exercises: homeworks (you need to score 60% on the 3 best out of 4 homeworks)
Lecture: oral examination (appointment by mail: michael@logic.at).
Not available from 17.07.-27.07, 17.08-28.08

Additional literature:

• Clifford Bergman: Universal Algebra: Fundamentals and Selected Topics - our library has a few copies!
• Jaroslav Ježek: Universal Algebra
• (BKW) Barto, Krokhin, Willard: Polymorphisms, and how to use them.
• (BK) Barto, Kozik: Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem
• Burris, Sankappanavar: A Course in Universal Algebra (an alternative source of examples and exercises)

Date	Topics	Lecture notes	Exercises	Homework
24/02	Equational theories, fully invariant congruences; completeness theorem for equational logic.	Section 1.1	1.1-1.3
02/03	Convergent term rewriting systems	Section 1.2
09/03	Critical pairs, Knuth-Bendix algorithm; Affine algebras	Section 1.2, 1.3 Section 2.1	1.4, 1.8,1.9	1.5,1.6,1.7 due on 24/03
16/03	Abelian algebras Herrmann's fundamental theorem	Section 2.1, 2.2	2.1-2.9; in particular 2.2, 2.6
23/03	Centralizer relation and commutator Example: groups	Section 2.3	2.11, 2.12	2.10, 2.13, 2.14 due on 07/04
30/03	Properties of the commutator Characterization of CD varieties	Section 2.3, 2.4	2.15-2.20; in particular 2.18,2.19
06/04	Nilpotent algebras and open questions	Section 2.5	Section 2.5
20/04	Birkhoff's theorem on Id_n(A) Example of a non-finitely based algebra	Chapter 3	3.1-3.4
27/04	McKenzies DPC theorem	Section 3.1	3.5-3.8
04/05	CSPs, pp-definable relations Pol-Inv	Section 4.1	4.1-4.5	3.5,3.6,4.3 due on 19/05
11/05	Clone and minion homomorphisms	Section 4.2	4.6-4.8
18/05	Taylor operations the CSP dichotomy conjecture/theorem	Section 4.3	4.9-4.11	4.6,4.7,4.8 until your exam

---

Winter term 2019/20
Practicals in Universal Algebra I (NMAG405)

See Libor's website.

---

Spring term 2019
Universal Algebra II (NMAG450)

The course will roughly follow Libor Barto's lecture from 17/18.

Lecture: Thurday 9:00 - 10:30 Seminar room of KA
Exercises: Thurday 10:40 - 12:10 Seminar room of KA (only odd semester weeks = even calendar weeks)

Grading:
Exercises: homeworks (60% from 3 best scores out of 4 homeworks)
Lecture: oral examination (appointment by mail: michael@logic.at).
next available dates 27/05-07/06; 17/06-20/06; 04/07-

Literature:

• Clifford Bergman: Universal Algebra: Fundamentals and Selected Topics - our library has a few copies!
• Jaroslav Jezek: Universal Algebra
• (BKW) Barto, Krokhin, Willard: Polymorphisms, and how to use them.
• (BK) Barto, Kozik: Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem
• Burris, Sankappanavar: A Course in Universal Algebra (an alternative source of examples and exercises)

Date	Topics	Recommended reading	Exercises	Homework
28/02	Abelian and affine algebras, Fundamental theorem.	Bergman 7.3	Ex. 1
07/03	Checking identities, Relational description of Abelianness; Centralizer relation (in general and in groups)	Bergman 7.4
14/03	Properties of the commutator Characterization of CD varieties	Bergman 7.4	Ex. 2	HW 1 due 28/03
21/03	Equational theories, fully invariant congruences; completeness theorem for equational logic.	Bergman 4.6 Jezek 13
28/03	Reduction order, critical pairs Knuth-Bendix algorithm	Jezek 13	Ex. 3
04/04	Examples of finitely based and non finitely based algebras	Bergman 5.4		HW 2 due 25/04
11/04	McKenzie's result on definable principal congruences	Bergman 5.5	Ex. 4
18/04	Constraint satisfaction problems over finite templates Pol-Inv revisited	BKW
25/04	(h1-)clone homomorphisms Taylor terms	BKW	Ex. 5	HW 3 due 09/05
02/05	Taylor's theorem	Bergman 8.4.
09/05	Smooth digraphs, algebraic length 1,absorption	BK
16/05	Absorption, transitive terms	BK	Ex. 6	HW 4
23/05	Absorption theorem, LLL (loop lemma 'light', for linked digraphs)	BK

---

Winter term 2018/19
Practicals in Universal Algebra I (NMAG405)

see David Stanovsky's website.