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, breadth-first search, depth-first search.
• Decrease-and-conquer: insertion sort, binary search.
• Greedy technique: general method, simple knapsack problem, Kruskal's algorithm, Prim's algorithm, Dijkstra's algorithm.
• Dynamic programming: Floyd-Warshall algorithm, traveling salesman problem, optimal binary trees.
• Backtracking: general method, N-queens problem, graph colouring.
• Branch-and-bound: 0/1-knapsack problem, traveling salesman.
Learning and teaching methods
• lectures,
• tutorials,
• lab work.
Intended learning outcomes - knowledge and understanding
• describe basic data structures, sorting algorithms, tree and graph algorithms
• recognize algorithms with various strategies, such as divide and conquer, greedy method, dynamic programming
• apply a suitable data structure and algorithm to a given problem
• evaluate an algorithm by determining the best, the mean and the worst time and space complexity
• select the appropriate algorithm among multiple alternatives for solving the problem with respect to its properties
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
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms (3rd ed., p. XIX, 1292). The MIT Press.
Additional information on implementation and assessment The written exam may be replaced by written midterm examinations in the weight of 50 %. The written exam consists of theoretical and practical part, each of them must be passed with 50 % of points.
