Topics in mathematical foundations of computer science

2022/2023
Programme:
Computer Science and Mathematics, Second Cycle
Year:
1 ali 2 year
Semester:
first or second
Kind:
optional
Group:
B
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 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.

Readings

A. Jaklič, A. Leonardis, F. Solina: Segmentation and Recovery of Superquadrics, Computational imaging and vision 20, Kluwer, Dordrecht, 2000.
B. Mohar: Teorija matroidov, DMFAS, Ljubljana, 1996.
S. H. Heap, Y. Varoufakis: Game Theory: A Critical Introduction, Routledge, London, 2004.
N. C. Jones, P. A. Pevzner: An Introduction to Bioinformatics Algorithms, MIT Press, Cambridge MA, 2004.
R. Niedermeier: Invitation to Fixed-Parameter Algorithms, Oxford University Press, 2006.
V. V. Vazirani: Approximation algorithms, Springer-Verlag, Berlin, 2001.
S. M. LaValle: Planning Algorithms, Cambridge University Press, 2006.
A. O. Pittenger: An introduction to Quantum Computing Algorithms, Birkhäuser Boston, 1999.
R. Seydel: Tools for Computational Finance, Springer, 2000.
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.
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.
Znanstveni članki.

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.

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]