ALGORITHMS AND DATA STRUCTURES I
Learning outcomes of the course unit
The goal of the course is to familiarize students with algorithms, data structures and with the techniques needed for analyzing their efficiency.
Prerequisites
Each student is expected to know the basic concepts of discrete mathematics, and calculus.
Course contents summary
Models of computation, analysis of algorithms.
Basic data structures: linked lists, stacks, queues, trees.
Basic sorting algorithms, lower bounds for sorting.
Quicksort, heapsort. Sorting in linear time.
Median and order statistics.
Divide and conquer technique.
Introduction to dynamic programming and greedy technique.
Huffman trees. Binary trees, binary search trees, B-trees, red-black trees.
Hash tables.
Graphs, BFS,DFS, directed acyclic graphs, topological sort and strong components.
Union-find, MST, Kruskal's algorithm, Prim's algorithm.
Dijkstra's algorithm, Bellman-Ford algorithm.
Recommended readings
T. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction to Algorithms, McGraw-Hill;
C. Demetrescu, I. Finocchi, G.F. Italiano, Algoritmi e strutture dati, McGraw-Hill.
