The lecturer chooses topics from the following list:
Balanced search trees.
Hash tables.
Binomial and Fibonacci heaps.
Union-find for disjoint sets.
Algorithms for strings (Rabin and Karp, Knuth, Morris and Pratt, Boyer and Moore).
Computation of convex hulls.
Voronoi diagram and Delaunay triangulation.
Finding maximum flows with preflows.
Finding largest (weighted) matchings in general graphs.
Alpha-beta algorithm.
Algorithms for planar graphs.
Algorithms for external memory.
Persistent data structures.
Data structures for integers.
Simple parallel algorithms.
Dynamic trees.
Data structures and algorithms 3
2022/2023
Programme:
Financial Mathematics, Second cycle
Year:
1 ali 2 year
Semester:
first or second
Kind:
optional
Group:
R1
ECTS:
6
Language:
slovenian, english
Lecturers:
Hours per week – 1. or 2. semester:
Lectures
2
Seminar
1
Tutorial
2
Lab
0
Content (Syllabus outline)
Readings
T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms, 2. izdaja, MIT Press, 2001.
D. C. Kozen: The Design and Analysis of Algorithms, Springer, 1991.
D. E. Knuth: Selected Papers on Analysis of Algorithms, Cambridge University Press, 2000.
S. Even, G. Even: Graph Algorithms, 2. izdaja, Cambridge University Press, 2011.
Znanstveni članki.
Objectives and competences
The students improve their knowledge of data structures and related algorithmic techniques used in the design of efficient algorithms. They also develop the knowledge of mathematical analysis for the correctness and the time/space complexity of algorithms.
Intended learning outcomes
Knowledge and understanding: Learning more about complex data structures and algorithms, practical and theoretical problems where this knowledge can be applied, and the basics of computational complexity.Application: The design of efficient computer programs and prediction of their behavior in practice by using mathematical methods.Reflection: The correlation between theoretical predictions about the behavior of computer programs and their actual behavior.
Transferable skills: The importance of mathematical analysis of computational processes and its practical application. Classification into difficult and less complex problems.
Learning and teaching methods
Lectures, seminar, exercises, homework, consultations and independent work by the students
Assessment
Type:
exam of exercises (2 midterm exams or written exam) or homework
oral exam.
Grading: 1-5 (fail), 6-10 (pass) (according to the Statute of UL)
Lecturer's references
Sergio Cabello:
CABELLO, Sergio, COLIN DE VERDIÈRE, Éric, LAZARUS, Francis. Algorithms for the edge-width of an embedded graph. V: 26th Annual Symposium on Computational Geometry, June 13th-16th, 2010, Snowbird, Utah. 26th Annual Symposium on Computation Geometry at Snowbird, Utah, USA : Special issue, (Computational geometry, ISSN 0925-7721, Vol. 45, iss. 5-6, 2012). Amsterdam: Elsevier, 2012, str. 215-224. [COBISS-SI-ID 16093017]
CABELLO, Sergio. Finding shortest contractible and shortest separating cycles in embedded graphs. V: 20th Annual ACM-SIAM Symposium on Discrete Algorithms, January 4-6, New York. SODA 2009 : special issue, (ACM transactions on algorithms, ISSN 1549-6325, Vol. 6, iss. 2). New York: Association for Computing Machinery, 2010, article No.: 24 (18 str.). [COBISS-SI-ID 15572057]
CABELLO, Sergio. Many distances in planar graphs. Algorithmica, ISSN 0178-4617, 2012, vol. 62, no. 1-2, str. 361-381. [COBISS-SI-ID 15702873]
