Algorithms and Data Structures
- 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
Forms of Teaching
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
- 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.
- Advanced data structures: multi-way trees and graphs; Representations of graphs (e.g., adjacency list, adjacency matrix) and Depth- and breadth-first traversals.
- 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.
- Strings and string processing; Pattern matching and string/text algorithms (e.g., substring matching, regular expression matching, longest common subsequence algorithms).
- Final exam.