Print

Data Structures

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.