SLO | EN

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.

Prerequisits

None.

Lecturer

  • izr. prof. dr. DAMJAN STRNAD, univ. dipl. inž. rač. in inf.

Assessment: Weight (%)

  • Computer skills: 50%
  • Written examination: 50%
Additional information on implementation and assessment

Course structure

  • Lectures: 30 hours
  • Tutorial: 45 hours
  • Individual work: 105 hours

Language of instruction

  • Lecture: Slovenian
  • Tutorial: Slovenian

The course is implemented at

  • COMPUTER SCIENCE AND INFORMATION TECHNOLOGIES - 1st year of study

Dostopnost

Povečaj pisavo
Spremeni kontrast
Berljiva pisava