### Algorithms and Data Structures

#### Course Description

Building on the knowledge obtained in Introduction to Programming, basic data structures and algorithms are presented. Computational complexity of algorithms is introduced. Search methods are presented, followed by recursion. Algorithms for sorting are explained and illustrated. Dynamic data structures are introduced: singly and multiply linked lists. Basic data structures, stack and queue, are presented followed by hashing, binary trees, and heap. Heap sort illustrates priority queue application. Graph structure and the basic algorithms on graphs are introduced. The elementary string/text search algorithms are presented.

#### Learning Outcomes

1. Describe the use of various data structures
2. Describe a number of standard algoritms
3. Apply appropriate data structures and algorithms to solve specific problems
4. Develop programs using appropriate data structures and algorithms
5. Evaluate the complexity of algorithms and programs
6. Identify appropriate data structures and algorithms to solve specific problems

#### Forms of Teaching

Lectures

Semester is organized in two cycles in totally 15 weeks, which accounts for two weeks for intermediate exams. There are four hours of lectures per week, divided in two terms of two hours (2+2).

Independent assignments

Lecturers assign tasks to students for individual study.

Laboratory

Two to three cycles of laboratory exercises.

#### Week by Week Schedule

1. The concept and properties of algorithms, Differences among best, expected, and worst case behaviors of an algorithm, Big O notation: formal definition and use, Simple numerical algorithms, such as computing the average of a list of numbers, finding the min, max, and mode in a list, approximating the square root of a number, or finding the greatest common divisor, Records/structs (heterogeneous aggregates), References and aliasing
2. Asymptotic analysis of upper and expected complexity bounds, Constant, logarithmic, linear, quadratic, and exponential complexity classes, Empirical measurements of performance, Time and space trade-offs in algorithms, Little o, big omega and big theta notation, Sequential and binary search algorithms, Strategies for choosing the appropriate data structure
3. Recurrence relations, Analysis of iterative and recursive algorithms, Reduction: transform-and-conquer
4. Divide-and-conquer, Recursive backtracking, Dynamic programming
5. Worst case quadratic sorting algorithms (selection, insertion), Worst or average case O(N log N) sorting algorithms (quicksort, heapsort, mergesort)
6. Linear data structures: arrays and lists, Linked lists
7. Abstract data types and their implementation (stacks, queues, priority queues, sets, maps)
8. Midterm exam
9. Hash tables, including strategies for avoiding and resolving collisions
11. Brute-force algorithms, Greedy algorithms, Branch-and-bound, Shortest-path algorithms (Dijkstra's and Floyd's algorithms); Minimum spanning tree (Prim's and Kruskal's algorithms)
12. Binary search trees and common operations on binary search trees such as select min, max, insert, delete, iterate over tree
13. Heaps
14. Strings and string processing, Pattern matching and string/text algorithms (e.g., substring matching, regular expression matching, longest common subsequence algorithms)
15. Final exam

#### Study Programmes

[FER3-EN] Computing - study
(3. semester)

#### Literature

(.), Predavanja iz predmeta,
(.), Cormen, Thomas, Charles Leiserson, Ronald Rivest, and Clifford Stein. Introduction to Algorithms. 3rd ed. MIT Press, 2009.,
(.), Sedgewick and Wayne. Algorithms (4th Edition). Addison-Wesley Professional; 4th edition (2011).,

#### General

ID 209645
Winter semester
6 ECTS
L2 English Level
L1 e-Learning
60 Lectures
0 Seminar
0 Exercises
6 Laboratory exercises
0 Project laboratory