Data structures and algorithms 2

Completed course Data structures and algorithms 1.

• 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.

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.

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.

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.

Lectures, exercises, homework, consultations

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)

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]