LABORATORY FOR ALGORITHMS AND DATA STRUCTURES
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.
Students will be expected to design and debug programming projects.
Each student is expected to have experience in C++ programming, and 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.
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.
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;
R. Sedgwick, Algorithms, Princeton University.