The course consists of two parts: theory and laboratory. The first part is devoted to data structures and algorithms for classical problems. Our goal is to present the main methods for the design of algorithms and for their analysis, which includes an evaluation of the computation time and the memory space required by the procedures. The second part is devoted to the implementation in C of some data structures and algorithms studied in the first part.
The main goal of the course is the knowledge of basic methods for the design and the analysis of algorithms. We want to develop the ability of determining algorithmic solutions for a given problem together with the capability of implementing in C language the corresponding procedures and data structures.
Intuitive notion of problem and algorithm. Design and analysis of algorithms. Complexity of an algorithm, worst-case and average case analysis. The RAM machine model. Syntax and semantics of RAM programs. Uniform and logarithmic cost criteria. Time and space complexity of RAM programs. High level (Algol-like) language. Elementary data structures: arrays, lists, stacks, queues and corresponding implementation. Graphs, trees and their representations. Recursive procedures and corresponding iterative translation by a stack. Algorithms for visiting graphs and trees; depth-first search and breadth-first search. Sorting algorithms and minimum number of comparisons. Insertionsort, heapsort, quicksort. Abstract data structures. Binary search trees, B-trees. "Union-find" operations on partitions: algorithms based on forests with balancing and compression. Divide and Conquer algorithms. Corresponding analysis of their time complexity (Master theorem): mergesort, binary search, algorithm for product of integers. Dynamic Programming algorithms: transitive closure of graphs and (all pair) shortest paths. Greedy algorithms. Algorithms for the minimum spanning tree (Kruskal, Prim) and for the shortest paths from a source (Dijkstra).
Asymptotic properties of sequences and sums. Main recurrence equations. Elements of C language: program structure, primitive data types, expressions, control flow, lexical analysis, basic data structures (arrays, matrices, strings, records), recursive procedures and functions, pointers dynamic memory allocation. Implementation of data structures and algorithms: sorting algorithms, lists, stacks and queues, graphs and trees, procedures for visiting graphs, balanced search trees, examples of dynamic programming and greedy algorithms.