 Study

# Computing

## Algorithms and Data Structures

• Class 60
• Practice 6
• Independent work 114
Total 180

### Course title

Algorithms and Data Structures

Obligatory

183381

3

6

### Course objectives

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.
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.
Recurrence relations; Analysis of iterative and recursive algorithms; Reduction: transform-and-conquer.
Divide-and-conquer; Recursive backtracking; Dynamic programming.
Worst case quadratic sorting algorithms (selection, insertion); Worst or average case O(N log N) sorting algorithms (quicksort, heapsort, mergesort).
Linear data structures: arrays and lists; Linked lists.
Abstract data types and their implementation (stacks, queues, priority queues, sets, maps).
Midterm exam.
Hash tables, including strategies for avoiding and resolving collisions.
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).
Binary search trees and common operations on binary search trees such as select min, max, insert, delete, iterate over tree.
Heaps.
Strings and string processing; Pattern matching and string/text algorithms (e.g., substring matching, regular expression matching, longest common subsequence algorithms).
Final exam.

### Prerequisites for:

1. Artificial Intelligence
2. Interactive Computer Graphics
3. Software Design Project
4. Multimedia Technologies
5. Scripting Languages
6. Object-oriented programming

(.), 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).,

#### Minimal learning outcomes

• Describe the use of various data structures
• Describe a number of standard algoritms
• Apply appropriate data structures and algorithms to solve specific problems
• Develop programs using appropriate data structures and algorithms
• Evaluate the complexity of algorithms and programs
• Identify appropriate data structures and algorithms to solve specific problems