Objectives and competences
The objectives of this course is to acquaint the students with the most important computer data structures and algorithms, strategies for algorithm design, and methods for evaluating the algorithm efficiency.
Content (Syllabus outline)
• Introduction: problem and algorithm, time and space complexity. Elementary data structures: array, stack, queue, linked lists. Tree: elementary items, binary tree, binary search tree, querying a binary search tree, insertion and deletion. Heap: heap viewed as an array, maintaining the heap property, building a heap, heapsort algorithm, priority queues. Hash table: hash functions, collision resolution by chaining, open addressing. Divide-and-conquer: general strategy, quicksort, mergesort, matrix multiplication, Strassen’s algorithm for matrix multiplication. Graph: representations of graphs. Decrease-and-conquer: insertion sort, breadth-first search, depth-first search. Greedy technique: general method, simple knapsack problem, Kruskal's algorithm, Prim's algorithm, Dijkstra's algorithm, Bellman-Ford algorithm. Dynamic programming: Floyd-Warshall algorithm, traveling salesman problem. Backtracking: general method, N-queens problem, graph colouring. Branch-and-bound: 0/1-knapsack problem.
Learning and teaching methods
• lectures,
• tutorials,
• lab work.
Intended learning outcomes - knowledge and understanding
• describe basic data structures, sorting algorithms, tree and graph algorithms,
• select the appropriate algorithm among multiple alternatives for solving the problem with respect to its properties,
• evaluate an algorithm by determining the best, the mean and the worst time and space complexity,
• apply a suitable data structure and algorithm to a given problem,
• recognize algorithms with various strategies, such as divide and conquer, greedy method, dynamic programming
Intended learning outcomes - transferable/key skills and other attributes
Communication skills: oral lab work defense, manner of expression at written examination.
Use of information technology: writing computer programs.
Calculation skills: solving calculation problems in homework assignments.
Problem solving: estimating time and space complexity of algorithms.
Readings
• T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms, 4. izdaja, MIT Press, Cambridge, Massachusetts, 2022.
Additional information on implementation and assessment The exam may be replaced by written midterm examinations in the weight of 50 %.
