COMPUTER SCIENCE 2Academic Year 2017/2018 - 3° Year
Credit Value: 6
Taught classes: 48 hours
Term / Semester: 1°
Knowledge and understanding: students will acquire knowledge concerning the principal methods for the design of efficient algorithms (incremental, recursion, dynamic programming, greedy algorithms), the techniques for their computational analysis, both in the worst and in the average cases and for their implementation.
Applying knowledge and understanding: students will be able to solve problems of low difficulty, requiring the design and analysis of elementary algorithmic solutions and to implement such algorithmic solutions.
Making judgements: students will acquire the ability of judging the quality of an algorithmic solution in terms of efficiency and reuse and the effectiveness of its implementation.
Communication skills: students will acquire the necessary communication ability and expressive skill in communicating problems concerning the algorithmic studies, also to non-expert interlocutors.
Learning skills: students will have the ability to use the knowledge acquired also in new ambits and to improve his/her knowledge through the consultation of specialist sources in the algorithmic field.
Detailed Course Content
The course introduces the principal design methodologies (incremental, recursion, dynamic programming, greedy algorithms), the techniques for their complexity analysis, both in the worst and average cases and the tools for their implementation. The Python programming language will be used as the main tool to present the implementations of data structures and algorithms.
Algorithms as technology to solve computational problems. Incremental methodology. Divide-and-Conquer methodology.
Asymptotic notations and relationships among them. Standard notations and common functions.
The substitution method. The iterative method and the recursion tree. The master theorem
Elements of dynamic programming
Optimal substructure, overlapping subproblems, reconstructing an optimal solution. Some case studies: matrix-chain multiplication, longest common subsequence, editing distance.
Elementary graph algorithms
Breadth-first search. Depth-first search (edges classification). Topological sorting. Strongly connected components
Elements of the greedy strategy
Greedy-choice property, optimal substructure. Some case studies: the activity-selection problem, Huffman codes.
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to algorithms (Third Edition), The MIT Press, Cambridge - Massachusetts, 2009