- 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.

**Timetable:**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

**Students' reception:**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.

**Course Material:**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/

**Course Program:**

**September 29, 2021:**Presentation of the course.

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.

**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.

**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.

**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.

Example of execution of the greedy algorithm for Min Weighted Set Cover.

**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.

**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).

**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.

**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

**October 27, 2021:**Algorithmic techniques: dynamic programming (a simplified version); Characteristics, Dynamic programming algorithm scheme, MAX 0-1 Knapsack, Subproblems, Proof that Max 0-1 Knapsack satisfies the principle of optimality, Uneeded (dominated) solutions, Algorithm Dyn-Prog Knapsack, Proof that Algorithm Dyn-Prog Knapsack computes an optimal solution in pseudo-polynomial time, example of execution of the Dyn-Prog knapsack algorithm

**October 29, 2021:**Polynomial Time Approximation Schemes (PTAS): Definition, Example, Remarks. Min Multiprocessor Scheduling: recalling Graham's greedy algorithm, idea underlying PTAS, Algorithm PTAS-Scheduling, PTAS-Scheduling always returns a (1+epsilon)-approximate solution (with proof), Complexity of Algorithm PTAS-Scheduling (with proof), Min h-Processor Scheduling problem. PTAS-Scheduling is a PTAS for Min h-Processor Scheduling (with proof), Min Partition problem.

**November 3, 2021:**Fully polynomial time approximation schemes (FPTAS): definition, remarks, examples. FPTAS-Knapsack: idea, complexity, approximation. Algorithm FPTAS-Knapsack: pseudocode, complexity, approximation or error, remarks, FPTAS-Knapsack is a FPTAS for Max 0-1 Knapsack (with proof). Algorithm FPTAS-Knapsack: is it possible to reduce the time complexity (complexity dynamic programming algorithm, approximation, remarks), how to improve the bounds for m*, complexity, approximation, new Algorithm FPTAS-Knapsack.

**November 5, 2021:**Exercise (with solution) before Mid-term examination.

**November 12, 2021:**Mid-term examination.

**November 17, 2021:**Mid-term exam solutions.

Alternative approaches: Guaranteed Performance, Restriction of the set of the instances, Average or probabilistic analysis, heuristics, randomized algorithms, r-approximating randomized algorithms. Max Weighted Cut, Algorithm Random Cut, Random-Cut is a ½-approximation algorithm (with proof).

**November 19, 2021:**Web Search: social science and bibliometry, centrality, centrality measure based on the concept of radius, degree centrality, closeness centrality, betweenness centrality, examples, co-citation index, prestige. Prestige scores, eigenvectors and eigenvalues, power iteration method, why power iteration works, how to compute the prestige vector.

**November 24, 2021:**Web Search: Web and Link Popularity, Ranking algorithms based on the link analysis, PageRank, Example of PageRank Algorithm, final calculation of PageRank, problems with PageRank: Dead Ends and Spider Traps. How to cope with dead ends and spider traps: teleporting. Damping factor and modified PageRank, topic-Specific PageRank.

**November 26, 2021:**Web Search: HITS Algorithm: root set and expanded set, authorities and hubs, counting in-links (authority), expert quality (hub), reweighting, mutually recursive definition. Authority scores and hub scores, example of HITS, power iteration method to solve the HITS algorithm, pro and cons of the HITS algorithm, problems with the HITS algorithm, SALSA algorithm (overview). What is Web Spam, First Spammers, First Techniques to make Spam. Solution to term spam, why it works.

Example about HITS: execution.

**December 1, 2021:**Web Search: Link Spamming, Link Farms. TrustRank: Combating the Web Spam, idea, Trust Propagation, Simple Model of Trust Propagation, Trust Attenuation, Trust Splitting, Picking the Seed Set, Approaches to Picking Seed Set.

Web search exercises (first part). (how to read this document: put side by side pages i and i+1, for i=1,3,5,7,9,11).

**December 3, 2021:**Web search exercises (second part). (how to read this document: put side by side pages i and i+1, for i=1,3,5,7,9,11).

**December 10, 2021:**Sponsored Search. Search and Advertising: history, combining search and advertising, query or keyword-based advertising, pay-per-click, advertising as matching market, simplifying assumptions, remarks. Matching Markets: basic principles; 1st scenario: room assigning. Bipartite graphs, perfect matching, constricted sets, the Hall's matching theorem, proof of the Hall's matching theorem. Computing a perfect matching, computing a maximum matching, remarks.

**December 13, 2021:**Sponsored Search. Back to assigning rooms: refinement with valuations, optimal assignment. Market-clearing prices. 2nd scenario: House Sales: payoffs, preferred-seller graph. Pricing examples. Theorem (with proof) of existence market-clearing prices. Optimality Market-Clearing Prices, social welfare, total revenue of sellers. Theorem (with proof) asserting that for any set of market-clearing prices any perfect matching M in the resulting preferred-seller graph G has maximum social welfare.

**December 15, 2021:**Sponsored Search. Back to sponsored search: best matching, ad quality, quality factor, how quality factor is computed. Quality factors on keyword-based search, complex queries and interaction with keywords, problems from advertiser and search engine’s perspective, deciding which ads to show, agreements between advertisers and search engines, final remarks on markets. Auctions: Introduction. Types of auctions: ascending-bid, descending-bid, first-price sealed-bid, second-price sealed-bid. Relationship between auctions and properties.

**December 17, 2021:**Sponsored Search. Proof that in second price auctions it is a dominant strategy to bid truthfully, performance of second price auctions, conclusions.

Sponsored search exercises (first part).

**December 22, 2021:**Sponsored search exercises (second part).

**News:**

**November 5, 2021:**The Mid-term written exam date is Friday November 12, time: 11.30. Students that want to take part in the Mid-term examination have to notify it by email to gianpiero.monaco@univaq.it by November 9. The exam will be in presence. However, students can attend the exam online if: i) have health problems, ii) are under lock down, iii) are international students who are still waiting for visas. If a student satisfies one of the aforementioned conditions and want to attend the exam online have to specify it in the email and have to provide a self-declaration under her/his own responsibility about her/his situation.

**November 10, 2021:**Mid-term written exam of Friday November 12, time: 11.30, Room: Digital class.

**November 15, 2021:**Available the results of the Mid-term exam of November 12, 2021.

**December 3, 2021:**On the exam there will be no question about: - Proof that power iteration converges; - Trustrank.

**December 9, 2021:**On Monday December 13, there will be an extra lecture from 16.30 to 18.30. The lecture will be in presence at room A1.5 (Alan Turing building), and online streaming on the general channel of the Web Algorithms course Team.

**December 20, 2021:**Final exams A.Y. 2021/2022: (Period January 17, 2022 - February 25, 2021)

1) Monday January 17, 2022. Time: 10.00. Room A1.1.

2) Monday February 7, 2022. Time: 10.00. Room A1.1.

3) Monday February 21, 2022. Time: 10.00. Room A1.1.

To be able to sit an exam session, students must register within the deadlines provided through the online system (segreteria virtuale). Students having the course "Distributed Systems and Web Algorithms" (12 CFU), to be able to sit an exam session have to also send an email to gianpiero.monaco@univaq.it by four days before the exam date.

**December 22, 2021:**Classes are over.

**January 15, 2022:**Reminder: to be able to sit an exam session, students must register within the deadlines provided through the online system (segreteria virtuale). Students having the course "Distributed Systems and Web Algorithms" (12 CFU), to be able to sit an exam session have to also send an email to gianpiero.monaco@univaq.it by four days before the exam date. Specifically, for the exam of Monday February 7, 2022, students have to send an email by February 3, 2022, and for the exam of Monday February 21, 2022, students have to send an email by February 17, 2022.

**January 17, 2022:**Click here to download the assignment of the written examination of January 17, 2022.

**January 17, 2022:**Available the results of the examination of January 17, 2022. Oral examination: Thursday January 20, time: 11.30 a.m., room: Digital class.

**February 8, 2022:**Click here to download the assignment of the written examination of February 7, 2022.

**February 8, 2022:**Available the results of the examination of February 7, 2022.

**February 22, 2022:**Click here to download the assignment of the written examination of February 21, 2022.

**February 22, 2022:**Available the results of the examination of February 21, 2022.

**May 13, 2022:**Final exams A.Y. 2021/2022: (Period: June 13, 2022 - July 29, 2022)

1) Monday June 13, 2022. Time: 14.30

2) Monday July 11, 2022. Time: 14.30

To be able to sit an exam session, students must register within the deadlines provided through the online system (segreteria virtuale). Students having the course "Distributed Systems and Web Algorithms" (12 CFU), to be able to sit an exam session have to also send an email to gianpiero.monaco@univaq.it by four days before the exam date.

**June 14, 2022:**Click here to download the assignment of the written examination of June 13, 2022.

**June 14, 2022:**Available the results of the examination of June 13, 2022. Oral examination: Thursday June 16, time: 15.00, room: C1.16 (Coppito 2).

**July 12, 2022:**Click here to download the assignment of the written examination of July 11, 2022.

**July 12, 2022:**Available the results of the examination of July 11, 2022. Oral examination: Thursday July 14, time: 10.30, room: Digital class.

**July 20, 2022:**Final exams A.Y. 2021/2022: (Period: September 5, 2022 - September 16, 2022)

1) Monday September 5, 2022. Time: 14.30, room: Digital class.

To be able to sit an exam session, students must register within the deadlines provided through the online system (segreteria virtuale). Students having the course "Distributed Systems and Web Algorithms" (12 CFU), to be able to sit an exam session have to also send an email to gianpiero.monaco@univaq.it by four days before the exam date.

**September 6, 2022:**Available the results of the examination of September 5, 2022. Oral examination: Thursday September 8, time: 11.00, room: Digital class.

(Click here) to get News

The course Distributed Systems and Web Algorithms (12 CFU) is divided into: Distributed Systems (6 CFU. By Prof. Proietti) and Web Algorithms (6 CFU).