Learning objectives
The goal of the course is to familiarize students with algorithms, data structures and with the techniques needed for analyzing their efficiency. <br />Students will be expected to design and debug programming projects.<br /><br />
Prerequisites
Each student is expected to have experience in C++ programming, and to know the basic concepts of discrete mathematics, and calculus. <br /><br />
Course unit content
<br /><br /> Models of computation, analysis of algorithms.<br />Basic data structures: linked lists, stacks, queues, trees.<br />Basic sorting algorithms, lower bounds for sorting.<br />Quicksort, heapsort. Sorting in linear time.<br />Median and order statistics.<br />Divide and conquer technique.<br />Introduction to dynamic programming and greedy technique.<br />Huffman trees. Binary trees, binary search trees, B-trees, red-black trees.<br />Hash tables.<br />Graphs, BFS,DFS, directed acyclic graphs, topological sort and strong components.<br />Union-find, MST, Kruskal's algorithm, Prim's algorithm.<br />Dijkstra's algorithm, Bellman-Ford algorithm.<br /><br /><br />
Full programme
- - -
Bibliography
<br /><br />T. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction to Algorithms, McGraw-Hill;<br />C. Demetrescu, I. Finocchi, G.F. Italiano, Algoritmi e strutture dati, McGraw-Hill;<br />R. Sedgwick, Algorithms, Princeton University.<br />
Teaching methods
- - -
Assessment methods and criteria
- - -
Other information
- - -
