This site uses only proprietary and third party technical cookies. By continuing to browse the site you are agreeing to our use of cookies. I agree I want to find out more
Browse the Department site:
Browse the Teaching site:

Programme of Course "Distributed Systems and Web Algorithms"

The course is composed by the following modules: "Distributed Systems"   "Web Algorithms"  

Code:

DT0166

Type of course unit:

Master Degree in Computer Science curriculum NEDAS: Compulsory
Master Degree in Computer Science curriculum UBIDIS: Compulsory

Level of course unit:

Postgraduate Degrees

Semester:

Module Distributed Systems: 1° semester
Module Web Algorithms: 1° semester

Number of credits:

Master Degree in Computer Science: 12 (workload 300 hours)

Teachers:

Guido Proietti (GuidodotProiettiatunivaqdotit)
Cosimo Vinci (cosimodotvinciatunivaqdotit)

1. Course Objectives

Module Distributed Systems: The course provides the foundations for designing and analyzing (distributed) algorithms for reliable, faulty, concurrent, and adversarial distributed systems.
Module Web Algorithms: 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.

2. Course Contents and learning outcomes (Dublin Descriptors)

Topics of the course include:

Module Distributed Systems

  • Algorithms for COOPERATIVE Distributed Systems (DS) 1. Leader Election 2. Minimum Spanning Tree 3. Maximal Independent Set
  • Algorithms for UNRELIABLE DS: network monitoring, consensus problem
  • Algorithms for CONCURRENT DS: Mutual exclusion

Module Web Algorithms

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

On successful completion of this course, the student should

Module Distributed Systems

  • By the end of this module students will be able to: 1) understand the difference between a centralized and a distributed algorithm; 2) analyze the resources (space and time) needed by a distributed algorithm; 3) known efficient algorithms for basic computational distributed problems (leader election, consensus, etc.); 4) understand the difference between a canonical and a strategic distributed system.
  • The aim is to make the student capable of abstracting models and formal algorithmic problems from real distibuted computational problems, and designing efficient algorithmic solutions.
  • Through the presentation and the comparison of different solutions to a given probelm, students will be guided to learn and to identify independently their most efficient solution.
  • The course will encourage the development of the following skills of the student: capability of formally presenting and modelling concrete problems, focusing on their main features and discarding the inessential ones.
  • The course aims to develop in graduate students competencies and abilities necessary in their future studies, especially with respect to doctoral studies on algorithmic topics.

Module Web Algorithms

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

3. Course Prerequisites

Module Distributed Systems: Knowledge of basic courses of discrete mathematcs and algorithms.
Module Web Algorithms: 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.

4. Teaching methods and language

Module Distributed Systems: Mainly lectures, with only few exercises.
Module Web Algorithms: Lectures and exercises

Language:English[info]

Reference textbooks

Module Distributed Systems

  • P. Ferragina e F. Luccio, Crittografia. Bollati Boringhieri.
  • H. Attiya e J. Welch, Distributed Computing. Wiley.

Module Web Algorithms

  • Vijay V. Vazirani, Approximation Algorithms. Springer. 2001.
  • G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi, Complexity and Approximation. Springer. 1999.
  • Jure Leskovec, Anand Rajaraman and Jeff Ullman, Mining of Massive Datasets. Stanford University. 2011.
  • Soumen Chakrabarti, Mining the Web – Discovering Knowledge from Hypertext Data. Morgan Kaufmann. 2003.
  • David Easley and Jon Kleinberg, Networks, Crowds, and Markets. Cambridge University Press. 2010.

5. Assessment Methods

Module Distributed Systems: Mid-term written examination, followed by a final oral examination, which, for those who performed successfully in the mid-term examination, will be restricted to the second part of the course.
Module Web Algorithms: 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.

Course information last updated on: 14 settembre 2018, 10:08