ALGORITHMSAcademic Year 2015/2016 - 2° Year - Curriculum A and Curriculum B
Credit Value: 9
Scientific field: INF/01 - Informatics
Taught classes: 72 hours
Term / Semester: 1°
Detailed Course Content
The course presents the main design methodoligies (incremental, recursion, dynamic programming, greedy algorithms) and the techniques for their complexity analysis, both in the worst and average cases.
Knowledge and understanding: students will acquire knowldege relative to the main methodologies for the design of efficient algorithms (incremental, recursion, dynamic programming, greedy algorithms), as well as the techniques for their computational analysis, both in the worst and in the average cases.
Applying knowledge and understanding: students will acquire the ability to solve problems of low difficulty, requiring the design and analysis of elementary algorithmic solutions.
Making judgements: students will be able to evaluate the quality of an algorithmic solution in terms of efficiency and reuse.
Communication skills: students will acquire the necessary communication skills and expressive ability in communicate problems regarding the algorithmic studies, also to non-expert interlocutors.
Learning skills: students will have the ability to adapt the knowledge acquired also in new contexts and to advance his/her knowledge through the consultation of specialist sources in the algorithmic field.
Computational problems and algorithms: the sorting problem
Algorithms as technology
Incremental methodology: Insertion-Sort (correctness and complexity)
Divide-and-Conquer methodology: Merge-Sort (complexity)
Asymptotic notations and relationships among them
Standard notations and common functions.
The substitution method
The iterative method and the recursion tree
The master theorem
Sorting and order statistics
Heaps and their construction
Quicksort and its randomized version
Analysis of Quicksort in the worst- and average case
Lower bounds for sorting
Sorting in linear time: Counting-Sort, Radix-Sort, Bucket-Sort
Medians and order statistics
Hash functions (division method, multiplication method, universal hashing)
Rotations, insertions, deletions
Elements of dynamic programming
Optimal substructure, overlapping subproblems, reconstructing an optimal solution
Some case studies: assembly line scheduling, matrix-chain multiplication, longest common subsequence, editing distance
Elements of the greedy strategy
Greedy-choice property, optimal substructure
Some case studies: the activity-selection problem, Huffman codes
Elementary graph algorithms
Depth-first search (edges classification)
Strongly connected components
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to algorithms (Third Edition), The MIT Press, Cambridge - Massachusetts, 2009.