Skip to main content

Topics in mathematical foundations of computer science

Computer Science and Mathematics, Second Cycle
1 ali 2 year
first or second
slovenian, english
Hours per week – 1. or 2. semester:

There are no prerequisites.

Content (Syllabus outline)

The lecturer chooses some important topics from computer mathematics, like for example:
Visualization of graphs and data. Computer Graphics. Computer vision.
Matroids. Duality and connectivity. Linear and binary matroids. Graphic matroids. Minors in matroids.
Game theory. Matrix games. Solutions and equilibria. Uncertanty and risks. Evolutional game theory. Combinatorial games.
Bioinformatics. Sequencing algorithms. Markov models. Phylogeny and classification of groups. Protein structure.
Tools for hard problems. FPT, exponential algorithms, approximation algorithms.
Alternative models of computation. Algorithms for cache models. Algorithms for data streams. Word RAM. Parallel algorithms. Quantum algorithms.
Connections between motion planning and computational geometry.
Algorithms for graphs. Planar graphs. Connectivity. Treewidth.
Computational financial mathematics.

  1. J. JáJá: Introduction to parallel algorithms, Reading : Addison-Wesley, cop. 1992.
  2. N. C. Jones, P. A. Pevzner: An Introduction to bioinformatics algorithms, Cambridge (Mass.) : MIT Press, cop. 2004.
  3. B. Mohar: Teorija matroidov, Ljubljana : Društvo matematikov, fizikov in astronomov Slovenije, 1996.
  4. R. Niedermeier: Invitation to fixed-parameter algorithms, New York : Oxford University Press, 2008.
  5. N. Nisan … [et al.], eds.: Algorithmic game theory, Cambridge : Cambridge University Press, 2008, cop. 2007.
  6. R. U. Seydel: Tools for computational finance, 4th ed., Berlin : Springer, cop. 2009.
  7. V. V. Vazirani: Approximation algorithms, Berlin : Springer, cop. 2001.
Objectives and competences

The student gets acquainted of some important subaread of computer mathematics.

Intended learning outcomes

The students learn and understand basic concepts, problems, and tools in different areas of computer mathematics.

Learning and teaching methods

Lectures, seminar, exercises, homework, consultations, and independent work by the students.


Exam of exercises (2 midterm exams or written exam) or homework
Oral exam
grading: 5 (fail), 6-10 (pass) (according to the Statute of UL)

Lecturer's references

Andrej Bauer:
BAUER, Andrej, STONE, Christopher A. RZ: a tool for bringing constructive and computable mathematics closer to programming practice. Journal of logic and computation, ISSN 0955-792X, 2009, vol. 19, no. 1, str. 17-43. [COBISS-SI-ID 15325785]
BAUER, Andrej, CLARKE, Edmund, ZHAO, Xudong. Analytica - An experiment in combining theorem proving and symbolic computation. Journal of automated reasoning, ISSN 0168-7433, 1998, vol. 21, no. 3, str. 295-325. [COBISS-SI-ID 10606425]
BAUER, Andrej, PETKOVŠEK, Marko. Multibasic and mixed hypergeometric Gosper-type algorithms. Journal of symbolic computation, ISSN 0747-7171, 1999, let. 28, št. 4-5, str. 711-736. [COBISS-SI-ID 9210969]
Sergio Cabello:
CABELLO, Sergio, KREVELD, Marc van. Approximation algorithms for aligning points. Algorithmica, ISSN 0178-4617, 2003, vol. 37, no. 3, str. 211-232. ,19,105,linkingpublicationresults,1:100117,1. [COBISS-SI-ID 13352793]
CABELLO, Sergio. Approximation algorithms for spreading points. Journal of algorithms, ISSN 0196-6774, 2007, vol. 62, no. 2, str. 49-73. [COBISS-SI-ID 14298201]
CABELLO, Sergio, HAVERKORT, Herman Johannes, KREVELD, Marc van, SPECKMANN, Bettina. Algorithmic aspects of proportional symbol maps. Algorithmica, ISSN 0178-4617, 2010, vol. 58, no. 3, str. 543-565. [COBISS-SI-ID 15151193]