• Algorithms, data structures and time complexity
• Arrays, stacks, queues and lists.
• Divide and conquer: binary search, mergesort, Strassen’s algorithm, solving recursive equations, Quicksort, median, and others.
• Backtracking.
• Dinamic programming: longest increasing subsequence, Levenshtein’s distance, product of several matrices, 0/1-knapsack, travelling salesmam problem, and others.
• Representations of graphs and networks. Basic algorithms on graphs: traversals, topological sorting, Floyd-Warshall algorithm, Dijkstra’s algorithm (heaps), Bellman-Ford algorithm, and others.
Data structures and algorithms 1
2023/2024
Programme:
Financial mathematics, First Cycle
Year:
3 year
Semester:
first
Kind:
optional
Group:
B2
ECTS:
5
Language:
slovenian
Course director:
Lecturer (contact person):
Hours per week – 1. semester:
Lectures
2
Seminar
0
Tutorial
1
Lab
1
Content (Syllabus outline)
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 gets familiar with data structures and related algorithms that are used in programming. It gets familiar with mathematical analysis of correctness, time and space complexity of algorithms.
Intended learning outcomes
Knowledge and understanding: Getting familiar with some basic data structures and algorithms, and some practical problems with relevant applications. Determining of correctness of computational procedures.
Application: Design of efficient computer programs and forecasting of their behavior by using mathematical methods.
Reflection: Connection between theoretical forecasts about behavior of computer programs and actual behavior.
Transferable skills: The importance of mathematical analysis of computational procedures and its practical applicability
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
Sergio Cabello:
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]
Sandi Klavžar:
KLAVŽAR, Sandi, MOLLARD, Michel. Cube polynomial of Fibonacci and Lucas cubes. Acta applicandae mathematicae, ISSN 0167-8019, 2012, vol. 117, no. 1, str. 93-105. [COBISS-SI-ID 16191833]
ILIĆ, Aleksandar, KLAVŽAR, Sandi, RHO, Yoomi. Generalized Lucas cubes. Applicable analysis and discrete mathematics, ISSN 1452-8630, 2012, vol. 6, no. 1, str. 82-94. [COBISS-SI-ID 16242265]
BATAGELJ, Vladimir, KORENJAK-ČERNE, Simona, KLAVŽAR, Sandi. Dynamic programming and convex clustering. Algorithmica, ISSN 0178-4617, 1994, let. 11, št. 2, str. 93-103. [COBISS-SI-ID 6799364]
KLAVŽAR, Sandi, LOKAR, Matija, PETKOVŠEK, Marko, PISANSKI, Tomaž. Izbrana poglavja iz računalništva. Del 2, Diskretna optimizacija, (Matematični rokopisi, 15). Ljubljana: Društvo matematikov, fizikov in astronomov SRS, 1986. 128 str. [COBISS-SI-ID 13496065]
Alen Orbanić:
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]
