Flow networks: the maximum flow problem, maximum flow and minimum cut, applications. Approximation algorithms: greedy techniques, linear programming. Introduction to genetic algorithms. Local search algorithms. Randomized algorithms.
J. Kleinberg, E. Tardos "Algorithm Design", Addison-Wesley, 2006
Learning Objectives
Knowledge acquired: The course aims to illustrate the main techniques useful for the resolution of difficult computing problems, presenting both algorithm design and methods ti evaluate the quality of a solution.
Prerequisites
Courses required: Algorithm and Data Structure
Courses recommended: Algorithm Design and Computational Complexity.
Teaching Methods
Total hours of the course (including the time spent in attending lectures, seminars, private study, examinations, etc...): 150
Hours reserved to private study and other indivual formative activities: 102
Contact hours for: Lectures (hours): 48
Further information
Frequency of lectures, practice and lab: Recommended
Teaching Tools
UniFi E-Learning: http://e-l.unifi.it
Office Hours:
Wednesdays, from 10.00 to 11.00 a.m., or by appointment via e-mail.
Dipartimento di Sistemi e Informatica
Viale Morgagni, 65
50134 - Firenze (FI)
Tel: 055 4237439 Fax: 055 4796363 - 4237436
E-Mail: mariacecilia.verri@unifi.it
URL: http://www.dsi.unifi.it/~cecilia/
Type of Assessment
Oral and writing.
Course program
Network flow: maximum flow problem, maximum flow and minimum cut. Applications: bipartite matching problem: disjoint paths in directed graphs; circulation on demand; survey design; Airline Scheduling; Image Segmentation; Project Selection; Baseball Elimination. Approximation algorithms: greedy techniques: the Center Selection Problem; Set Cover: a general greedy heuristic; the Pricing Method: Vertex Cover;the Disjoint Paths Problem; Linear Programming and Rounding. Arbitrarily good approximations: the Knapsack Problem. Local search algorithms. Hopfield Neural Networks. Nash Equilibria Randomized algorithms. Pattern Matching.