Topics in mathematical foundations of computer science

2022/2023
Programme:
Mathematics, Second Cycle
Year:
1 ali 2 year
Semester:
first or second
Kind:
optional
Group:
R1
ECTS:
6
Language:
slovenian, english
Hours per week – 1. or 2. semester:
Lectures
2
Seminar
1
Tutorial
2
Lab
0
Content (Syllabus outline)

The lecturer selects some important topics in computational mathematics, such as:
Computational geometry and geometric optimization.
Computational topology.
Graph algorithms.
Graph and data visualization.
Computer graphics.
Computer vision.
Matroids.
Algorithmic game theory.
Approximation algorithms.
Parallel algorithms.
Algorithms for data streams.
Symbolic computation.
Bioinformatics.

Readings

M. de Berg, O. Cheong, M. van Kreveld, M. Overmars: Computational Geometry: Algorithms and Applications, 3. izdaja, Springer-Verlag, 2008.
S. Har-Peled: Geometric approximation algorithms, AMS, 2011.
H. Edelsbrunner, J.L. Harer: Computational Topology. An Introduction, AMS, 2010.
G. Di Battista, P. Eades, R. Tamassia, I.G. Tollis: Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, 1998.
C. H. Lampert: Kernel Methods in Computer Vision, Foundations and Trends in Computer Graphics and Vision 4 (2009) 193-285.
B. Mohar: Teorija matroidov, DMFAS, Ljubljana, 1996.
N. Nisan, T. Roughgarden, E. Tardos (ur.): Algorithmic Game Theory, Cambridge University Press, 2007.
D.P. Williamson, D.B. Shmoys: The Design of Approximation Algorithms, Cambridge University Press, 2011.
J. JaJa. Introduction to parallel algorithms. Addison-Wesley, 1992.
S. Muthukrishnan: Data Streams: Algorithms and Applications, Foundations & Trends in Theoretical Computer Science, 2005.
J. von zur Gathen, J. Gerhard: Modern Computer Algebra, 3rd ed., Cambridge University Press, 2013.
M. Kauers, P. Paule: The concrete tetrahedron. Symbolic sums, recurrence equations, generating functions, asymptotic estimates, Springer, 2011.
N. C. Jones, P. A. Pevzner: An Introduction to Bioinformatics Algorithms, MIT Press, Cambridge MA, 2004.
Znanstveni članki.

Objectives and competences

The students get acquainted with some important and actual areas of computational mathematics.

Intended learning outcomes

Knowledge and understanding: Students gain deeper knowledge of selected areas in computational mathematics. They become familiar with both the theoretical foundations and the techniques for solving problems in these areas.Application: Solving computational problems from different areas.Reflection: The students see computational problems and modelling. Connection between theory and praxis.Transferable skills: Use of algorithmic thinking for solving imperfectly defined problems.

Learning and teaching methods

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

Assessment

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]