Course Instructors: Alexandru Olteanu (ICA), Irina Mocanu (ICB), Serban Radu (ICC).

The course aims to specify and use abstract data types (ADT); implement Abstract Data Types using standard data structures; present fundamental Abstract Data Types (such lists, stacks, queues, trees, graphs), their implementation and associated algorithms; justify the choice of most appropriate data types for a given application; present data structures providing an efficient search, insertion and deletion in internal memory; present analysis tools of algorithms complexity: running time, asymptotic notations, etc; accustom students with recursive algorithms using recursive data structures (lists, trees); find correct, efficient and elegant solutions to solve problems; implement quick algorithms for searching and sorting using heaps, hash tables, etc. On completion of the course, the student should be able to: develop creatively applications using fundamental ADT; project and implement new data types, using existing data types; write correct, efficient, modular programs solving complex applications, using an imperative programming language; analyse adopted implementation solution.

Syllabus:

• Abstract Data Types.
• ADT specification.
• Complexity of algorithms.
• Recursivity.
• Divide and conquer.
• Recursive sorting (quicksort, mergesort).
• Recurrent equations.
• Stacks: ADT Stack, Stack applications  Stack implementations.
• Queues: ADT Queue. Queue applications. Implementations.
• Data model List: ADT List specification. Applications. Implementations.
• Data model Tree. Binary and multiway trees. ADT Binary Tree Specification. Binary tree traversal. Applications. Implementations.
• Binary Search Trees. Searching, node insertion, node deletion.
• Threaded trees.
• Heaps.
• Heapsort.
• Priority queues.
• Balanced trees.
• AVL trees, splay trees, red-black trees.
• Insertion and deletion in balanced trees.
• Hash tables.
• Open and chained addressing.
• Collision avoiding.
• ADT Graph.Specific operations. Implementations using adjacency matrices and adjacency lists.
• Graph traversals: DFS and BFS. Traversal applications: topological sort, strong connected components.
• Minimal Spanning trees in weighted graphs: Prim and Kruskal algorithm.
• The shortest path in graphs. Dijkstra and Bellman-Ford Algorithms.