Data Structures and Algorithm Analysis

Course title: Data Structures and Algorithm Analysis

Code: 3ФЕИТ07Л024

Number of credits (ECTS): 6

Weekly number of classes: 2+2+1+0

Prerequisite for enrollment of the subject: Passed:Programming and algorithms, Taken course: Data structures and programming.

Course Goals (acquired competencies): Working with complex data structures in Java programming language. Algorithms for working with data structures. After finishing this course the student will be able to solve problems using complex data structures and algorithms in Java.

Total available number of classes: 180

Course Syllabus: Introduction to algorithm theory and basic concepts of data structures. Logical and physical structures. Implementation of Java ADT. Analysis and algorithm complexity. Linear data structures - arrays and lists. Statical and dynamical arrays and lists in Java. Application of arrays and lists for logical data structures: stack, queue, priority queue (in Java). Algorithmic strategies. Algorithm design. Algorithms classification. Brute force strategy. Greedy algorithms. Strategy divide and conquer. Non-linear structures. Trees. Binary trees. Binary search trees. Balanced binary search trees. AVL trees. Red Black trees. Hash structures. Hashing functions and their properties. Collisions and dismissal. Graphs. Directed and nondirected graphs. Application of graphs. Weighted graphs. Representation of graphs through data structures. Graph traversal algorithms: depth-first and breadth-first. Shortest path algorithms in weighted graphs. Bellman-Ford algorithm. Djikstra`s algorithm. Kruskal`s algorithm. Prim`s algorithm.

Literature: