Course Details for A.Y. 2018/2019

The information on this page refer to the academic year 2018/2019. Therefore, several links are not available and data may be incomplete. To read the current information on the course, if it is still available, go to the university course catalogue . To read information relating other academic years, use the list at the bottom of this page.

A. Year:

2018/2019

Name:

Web Algorithms / Web Algorithms

Type:

Module

Main course:

Distributed Systems and Web Algorithms / Distributed Systems and Web Algorithms

Basic information

Code:

DT0167

Sector:

INF/01

Credits:

: Master Degree in Computer Science 6 CFU (b)

Term:

1^st semester

Degree(s):

Master Degree in Computer Science 1^st anno curriculum NEDAS Compulsory
Master Degree in Computer Science 1^st anno curriculum SEAS Elective
Master Degree in Computer Science 1^st anno curriculum UBIDIS Compulsory

Language:

English

Teacher(s):

Cosimo Vinci

Same as:

Algorithms and Data Structures II

Course Objectives

Knowledge of advanced algorithmic techniques; ability to individuate, formalize and solve optimization problems; concept of approximation; knowledge of the web search and sponsored web search strategies in search engines; ability to collaborate for the realization of applicative projects in group.

Course Content

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) and Fully Polynomial Time Approximation Schemes (FPTAS).
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, VCG and GSP mechanisms.

Learning Outcomes (Dublin Descriptors)

On successful completion of this course, the student should

Acquire knowledge of advanced algorithmic techniques for NP-Hard optimization problems. In particular, the student will have mastery command of main algorithmic (approximation) techniques like greedy, local search, dynamic programming, linear programming: Polynomial Time Approximation Schemes (PTAS) and Fully Polynomial Time Approximation Schemes (FPTAS). Moreover the student will acquire knowledge on the basic centrality and prestige indices in social networks, on the main popularity indices for ranking pages in web search and finally of matching markets, auctions and the most important mechanisms adopted for the ranking and payment of sponsored search links.
Acquire the ability of abstracting models and formal algorithmic problems from real computational problems, understanding the degree of approximability and designing efficient algorithmic solutions.
Acquire autonomy in individuating, formalizing and understanding the degree of approximability of real computational problems and identify independently their most efficient solutions.
Being able to understand complex algorithmic solutions and to formal proving performances of their algorithmic solutions for complex computational problems.
Acquire the ability of understanding the ranking strategies adopted by search engines in web search and sponsored web search.
The course aims to develop in graduate students competencies and abilities necessary in their future studies and/or works, especially with respect to doctoral studies and in general to any research activity on algorithmic and web search topics.

Prerequisites and Learning Activities

KNOWLEDGE: fundamentals of programming, discrete mathematics, algorithms and data structures, computer architectures, reading and understanding of the English language SKILLS: ability to integrate classroom and homework study, ability to interact with the teacher during the class for originating discussion.

Assessment Methods and Criteria

Written test followed by an oral exam. The written exam consists into two different parts (one part is related to approximation algorithm, the other one is related to web-search and sponsored web-search), and each part should be completed in 1:45 minutes. A student can decide to do the two parts in different exam dates. The minimum score to pass each part is 18/30, and the final score is the average of the two scores. An eventual oral exam consists into a detailed oral discussion of the written exam, and, eventually some further questions about the theoretical part of the course.

Textbooks

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-540-65431-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 https:
www.cs.cornell.edu/home/kleinber/networks-book/

Internet Resources

Homepage:

https://moodle.univaq.it/

Course page updates

This course page is available (with possible updates) also for the following academic years:

To read the current information on this course, if it is still available, go to the university course catalogue .

Course information last updated on: 16 ottobre 2018, 16:01