Data structures and algorithms 2

2022/2023
Programme:
Financial mathematics, First Cycle
Year:
3 year
Semester:
second
Kind:
optional
Group:
B2
ECTS:
5
Language:
slovenian
Hours per week – 2. semester:
Lectures
2
Seminar
0
Tutorial
1
Lab
1
Prerequisites

Completed course Data structures and algorithms 1.

Content (Syllabus outline)

• Greedy algorithms: Huffman codes, set cover, and others.
• Amortized time complexity. Disjoint sets.
• Minimum spanning tree. Boruvka’s, Prim’s and Kruskal’s algorithm.
• Balanced search trees.
• Randomized search trees. Skip lists.
• Hashing.
• Fast Fourier transform.
• Examples of NP-hard problems. Generic methods for hard problems.
• Other selected algorithms.

Readings

T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms, 2. izdaja, MIT Press, Cambridge, 2001.
S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani: Algorithms, McGraw-Hill, 2008.
J. Erickson: Zapiski za Undergraduate Algorithms, 2012.
J. Kleinberg, E. Tardos: Algorithm design, Pearson/Addison-Wesley, 2005.
J. Kozak: Podatkovne strukture in algoritmi, DMFA-založništvo, Ljubljana, 1997.

Objectives and competences

The student upgrades the knowledge about basic data structures and related algorithms that are used at programming. It gets familiar with mathematical analysis of correctness, time and space complexity of algorithms.

Intended learning outcomes

Knowledge and understanding: Knowledge about basic data structures and algorithms, as well as practical problems with relevant applications. Knowledge about basics of theory of computational complexity and understanding its meaning in practice.
Application: Designing efficient computer programs and predicting their behavior by using mathematical methods.
Reflection: Connection between theoretical predictions about behavior of computer programs an actual behavior.
Transferable skills: Meaning of mathematical analysis of computational procedures and its practical applicability. Distinction between manageable and unmanageable problems.

Learning and teaching methods

Lectures, exercises, homework, consultations

Assessment

Type (examination, oral, coursework, project):

Homeworks with defense;
2 midterm exams instead of written exam, written exam

grading: 5 (fail), 6-10 (pass) (according to the Statute of UL)

Lecturer's references

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, KNAUER, Christian. Algorithms for graphs of bounded treewidth via orthogonal range searching. Computational geometry, ISSN 0925-7721. [Print ed.], 2009, vol. 42, iss. 9, str. 815-824. [COBISS-SI-ID 15160409]
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]
PERME, Tomaž, NOVAK, Matjaž, STRAŠEK, Rok, KAVKLER, Iztok, ORBANIĆ, Alen. A model for technical optimisation of the distribution centre, 2011, Acta technica corviniensis, tome 4, fasc. 2, str. 39-43. [COBISS-SI-ID 4154583]
ORBANIĆ, Alen. F -actions and parallel-product decomposition of reflexible maps. Journal of algebraic combinatorics, ISSN 0925-9899, 2007, issue 4, vol. 26, str. 507-527. [COBISS-SI-ID 14429529]
ORBANIĆ, Alen, BOBEN, Marko, JAKLIČ, Gašper, PISANSKI, Tomaž. Algorithms for drawing polyhedra from 3-connected planar graphs. Informatica, ISSN 0350-5596, 2004, vol. 28, no. 3, str. 239-243. [COBISS-SI-ID 13285977]