University of L'Aquila
(Click here) to get News|
Department of Information Engineering Computer Science and Mathematics
Academic Year 2021/2022
Web Algorithms (6 CREDITS).
Link to the Computer Science Degree official website (click here).
The course Distributed Systems and Web Algorithms (12 CFU) is divided into: Distributed Systems (6 CFU. By Prof. Proietti) and Web Algorithms (6 CFU).
The goal of this course is to provide students knowledge of advanced algorithmic techniques; ability to identify, formalize and solve optimization problems; concept of approximation;
knowledge of the web search and sponsored web search strategies in search engines.
- Review of computational complexity and intractability. Optimization problems. Approximation algorithms.
- Algorithmic techniques: greedy. local search, dynamic programming and linear programming.
- Polynomial Time Approximation Schemes (PTAS).
- Prestige and centrality indices in social networks.
- Web search: Pagerank, Topical Pagerank, TrustRank, Hubs and Authorities.
- Sponsored web search: matching markets and market clearing prices, auctions, mechanisms.
First semester (September 27, 2021 - January 14, 2022), Wednesday: 11.30 - 13.30 (room Digital class), and Friday: 11.30 - 13.30 (room Digital class).
Name of the Team: Web Algorithms - A.A. 2021/2022.
Team code: 0aq67u5
Online by appointment on the Team called: Gianpiero Monaco - Ricevimento Studenti (Students' Reception).
Students are invited to arrange the day and time of the meeting by e-mail and therefore to send an e-mail preventively.
Lecture notes (slides) provided by the lecturer.
Additional didactic material:
- Vijay V. Vazirani, Approximation Algorithms , Springer. 2001. ISBN: 3-540-65367-8.
- G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi, Complexity and Approximation , Springer. 1999. ISBN: 3-54065431-3.
- Jure Leskovec, Anand Rajaraman and Jeff Ullman, Mining of Massive Datasets, Stanford University. 2011. ISBN: 9781107015357 http://infolab.stanford.edu/~ullman/mmds/book.pdf.
- Soumen Chakrabarti, Mining the Web – Discovering Knowledge from Hypertext Data , Morgan Kaufmann. 2003. ISBN: 9781558607545.
- David Easley and Jon Kleinberg, Networks, Crowds, and Markets, Cambridge University Press. 2010. ISBN: 9780521195331 www.cs.cornell.edu/home/kleinber/networks-book/
September 29, 2021: Presentation of the course.
Slides (Click here).
Computational Complexity: Problems in Computer Science, Problem Types (Decision, Search, Optimization), Complexity of Algorithms and Problems, Decision Problems and Complexity Classes, Clique problem, Vertex Cover problem, decision problems, non-deterministic algorithms for decision problems, non-deterministic algorithm for clique, efficiency and tractability, growth of polynomial functions with respect to exponential ones, robustness of the concept of polynomial time solvability, polynomially related codes, example, example on non-natural encoding, polynomially simulable computational models, classes P and NP, NP-Complete problems. Optimization problems: definition, definition of the Clique optimization problem, definition of the Min Vertex Cover optimization problem, definition of the Min Traveling Salesman Problem (TSP), underlying decision problem, underlying decision problem of Max Clique, Complexity Classes of Optimization Problems: PO, NPO, NP-HARD problems. Slides (Click here).
October 1, 2021: Computational Complexity: NP-HARD problems. Approximation Algorithms: coping strategies for solving an NP-HARD problem, r-approximation algorithms for minimization and maximization problems, determination of the approximation factor, approximation algorithm for Min Vertex Cover, example of execution of the Approx-Cover algorithm, optimal solution of the Approx-Cover algorithm, proof that the Approx-Cover algorithm is 2-approximating. Algorithmic techniques, Greedy: characteristics, Max 0-1 Knapsack, Greedy choice, Algorithm Greedy-Knapsack, proof that it is not r-approximating for any given r<1. Modified Greedy-Knapsack algorithm, proof that Modified-Greedy-Knapsack algorithm is ½-approximating. Min Multiprocessor Scheduling, Greedy Algorithm of Graham, proof that the Greedy Algorithm of Graham is (2-1/h)-approximating. Slides (Click here).
October 6, 2021: Proof that the Greedy Algorithm of Graham is not r-approximating for r < 2-1/h, improving the approximation ratio, algorithm Ordered-Greedy, proof that Ordered-Greedy is (3/2 – 1/(2h))-approximating, Max Cut, Algorithm Greedy for Max Cut, Example Greedy Choice, Proof that the Greedy Max Cut algorithm is ½-approximating, Min Weighted Set Cover. Slides (Click here).
October 8, 2021: Greedy algorithm for Min Weighted Set Cover, Greedy Choice, Algorithm Greedy-Min-Weighted-Set-Cover, proof that the greedy algorithm for Min Weighted Set Cover is Hn-approximating, example showing that the approximation ratio of the greedy algorithm is at least Hn, conclusions on the greedy technique. Slides (Click here).
Example of execution of the greedy algorithm for Min Weighted Set Cover. Slides (Click here).
October 13, 2021: Algorithmic techniques: local search; characteristics, scheme of a local search algorithm, complexity, approximation, neighborhood definition, extremal cases. Max Matching, Algorithm of Edmonds, Complexity, Max Cut, Local-Search Algorithm for Max Cut, Complexity, proof that the Local-Search Algorithm for Max Cut is ½-approximation, Example of execution of the Local-Search Algorithm for Max Cut, conclusions on local search. Slides (Click here).
October 15, 2021: Algorithmic techniques: linear programming; characteristics, rounding, characteristics of rounding. Min Weighted Vertex Cover: ILP, LP, Algorithm Round-Vertex-Cover, Proof that the Round-Vertex-Cover Algorithm is a 2-approximation algorithm. Min Weighted Set Cover: ILP, LP, Algorithm Round-Set Cover, proof that Round-Set-Cover is f-approximating (f>=1). Slides (Click here).
October 20, 2021: Algorithmic techniques: linear programming; characteristics, primal-dual, General Primal-Dual, LP-duality Theorem, Weak duality theorem, Structure of optimal solutions, Complementary slackness conditions theorem, Observations, Relaxing the dual complementary conditions, Relaxed complementary conditions theorem, Primal-dual method goal, Primal and relaxed dual complementary conditions, Steps of an algorithm that follows the primal-dual method, Primal and dual formulation of Min Weighted Vertex Cover, Example. Slides (Click here).
October 22, 2021: Algorithmic techniques: linear programming; Algorithm Primal-Dual Vertex-Cover. Proof that Primal-Dual-Vertex-Cover is 2-approximating, Examples of executions of the Primal-Dual Vertex-Cover algorithm Slides (Click here).